File BTree.h

↰ Parent directory (ADS/tree)

The B-tree of Bayer and McCreight, beyond the book [see File BPlusTree.h for the B+-tree of chapter 6, which has no removal]: a search tree whose nodes hold from t - 1 to 2 t - 1 keys (the root from 1), a node of j keys having j + 1 children, and all the leaves at the same depth, so that the height is at most :math:` log_t ( ( n + 1 ) / 2 ) ` and a node fills a block of the disk.

Definition (ADS/tree/BTree.h)

Detailed Description

insert() goes down from the root splitting each full node it meets, so that the leaf reached has room; remove() goes down making sure that each node it enters has at least t keys, by borrowing a key from a sibling or by merging with it, so that a key can always be taken out of a leaf (a key of an internal node is replaced by its predecessor or successor, or the two children around it are merged); both in one pass, :math:` O( t log_t n ) ` time. It is a DICTIONARY [see File ADT.h], and forEach() visits the pairs by increasing keys.

The contracts [see File Contract.h]: t >= 2; insert() ensures that the key is there and remove() that it is not; the invariant is the order of the keys, their number in each node and the depth of the leaves, an O( n ) check at the level 3. The operations are defined in BTree.tpp.

  1. Bayer, E. M. McCreight, Organization and maintenance of large ordered indexes, Acta Informatica 1(3), 173-189, 1972, doi:10.1007/BF00288683

    1. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009, chapter 18

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 6.2.4

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes