Search within a Page

Publisher Website
Google Scholar
Abstract
Three famdies of strategies for orgamzmg an index of ordered keys are investigated It ~s assumed either that the index is small enough to fit m mam memory or that some superstrategy orgamzes 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 d,scussed and conjectured on Considering time and space costs and complexity of programming, it Is concluded that a Binary Search strategy is generally In this paper we provide a theoretical framework allowing comparison of various strategies for indexing a data base. We investigate three famdles of strategies for orgamzmg an index of ordered keys. Each strategy considered must support random accesses, inserts, and deletes, as well as order-dependent operations such as

This publication has 4 references indexed in Scilit: