Next: 5.4.1 Definition of B-Trees
Up: 5. Balanced Trees
Previous: 5.3.2 2-3 Trees: Deletion
- Generalization of 2-3 Trees
- Multi-way search tree, very well suited for external storage
- Standard organization for indices in database systems
- Balanced tree, which achieves minimization of disk accesses in database
- R. Bayer. Symmetric binary B-trees: Data Structures and maintenance
algorithms. Acta Informatica, Volume 1, pp.290-306, 1972.
- R. Bayer and E.M. McCreight. Organization and maintenance of large
ordered indexes. Acta Informatica, Volume 1, Number 3,
pp. 173-189, 1972.
- D. Comer. The ubiquitous B-tree.
ACM Computing Surveys, Volume 11, Number 2, pp 121-137, 1979.