|
|
< Day Day Up > |
|
Knuth [185], Aho, Hopcroft, and Ullman [5], and Sedgewick [269] give further discussions of balanced-tree schemes and B-trees. Comer [66] provides a comprehensive survey of B-trees. Guibas and Sedgewick [135] discuss the relationships among various kinds of balanced-tree schemes, including red-black trees and 2-3-4 trees.
In 1970, J. E. Hopcroft invented 2-3 trees, a precursor to B-trees and 2-3-4 trees, in which every internal node has either two or three children. B-trees were introduced by Bayer and McCreight in 1972 [32]; they did not explain their choice of name.
Bender, Demaine, and Farach-Colton [37] studied how to make B-trees perform well in the presence of memory-hierarchy effects. Their cache-oblivious algorithms work efficiently without explicitly knowing the data transfer sizes within the memory hierarchy.
|
|
< Day Day Up > |
|