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^+$ ...