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

Discussion on External Memory Searching

Explore how external memory searching works using B-trees, a fundamental structure for managing large data sets efficiently on disk. This lesson explains B-trees’ importance in file systems and databases, their variants, and why they optimize search operations by balancing depth and minimizing disk access. Understand how caching internal nodes can speed up searches and learn about alternative external memory hashing methods for specific operations.

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.

BB-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 ...