Discussion on External Memory Searching

Additional notes

The external memory model of computation was introduced by Aggarwal and VitterA. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116– 1127, 1988.. It is sometimes also called the I/O model or the disk access model.

B-Trees are to external memory searching what binary search trees are to internal memory searching. B-trees were introduced by Bayer and McCreightR. Bayer and E. M. McCreight. Organization and maintenance of large ordered indexes. In SIGFIDET Workshop, pages 107–141. ACM, 1970. in 1970 and, less than ten years later, the title of Comer’s ACM Computing Surveys articleD. Comer. The ubiquitous B-tree. ACM Computing Surveys, 11(2):121–137, 1979. referred to them as ubiquitous.

Like binary search trees, there are many variants of B-trees, including $B^+$–trees, $B^∗$–trees, and counted B-trees. B-trees are indeed ubiquitous and are the primary data structure in many file systems, including Apple’s HFS+, Microsoft’s NTFS, and Linux’s Ext4; every major database system; and key-value stores used in cloud computing. Graefe’s recent surveyG. Graefe. Modern B-tree techniques. Foundations and Trends in Databases, 3(4):203–402, 2010. provides a $200+$ page overview of the many modern applications, variants, and optimizations of B-trees.

B-trees implement the SSet interface. If only the USet interface is needed, then external memory hashing could be used as an alternative to B-trees. External memory hashing schemes do exist; see, for example, Jensen and PaghM. S. Jensen and R. Pagh. Optimality in external memory hashing. Algorithmica, 52(3):403–411, 2008.. These schemes implement the USet operations in $O(1)$ expected time in the external memory model. However, for a variety of reasons, many applications still use B-trees even though they only require USet operations.