Search within a Page
Abstract
Three families of strategies for organizing an index of ordered keys are investigated. It is assumed either that the index is small enough to fit in main memory or that some superstrategy organizes the index into pages and that search within a page is being studied. Examples of strategies within the three families are B-tree Search, Binary Search, and Square Root Search. The expected access times of these and other strategies are compared, and their relative merits in different indexing situations are discussed and conjectured on. Considering time and space costs and complexity of programming, it is concluded that a Binary Search strategy is generally preferable.
Recommended Citation
H. R. Strong et al., "Search within a Page," Journal of the ACM (JACM), vol. 26, no. 3, pp. 457 - 482, Association for Computing Machinery (ACM), Jul 1979.
The definitive version is available at https://doi.org/10.1145/322139.322146
Department(s)
Computer Science
Keywords and Phrases
Data Processing - Data Structures; Information Retrieval Systems; access method; B-tree; binary search; index; searching; square root search
International Standard Serial Number (ISSN)
0004-5411
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 1979 Association for Computing Machinery (ACM), All rights reserved.
Publication Date
01 Jul 1979
