Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in C++

Discussion on External Memory Searching

Explore how B-trees optimize searching in external memory by minimizing disk accesses and managing large dynamic datasets efficiently. Understand their role in major file systems and databases, and compare their performance with external memory hashing methods.

We'll cover the following...

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