File BPlusTree.h

↰ Parent directory (ADS/tree)

The B+-tree of order m of the reality check of chapter 6, the search tree of the file systems and of the databases, whose nodes are pages of the secondary memory.

Definition (ADS/tree/BPlusTree.h)

Detailed Description

An internal node has f children, :math:` lceil m / 2 rceil leq f leq m ` (the root at least 2), and f - 1 keys k[ 0 ] , … , k[ f - 2 ]: the child p[ i ] holds the keys in ( k[ i - 1 ] , k[ i ] ], p[ 0 ] those up to k[ 0 ] and p[ f - 1 ] those larger than k[ f - 2 ]. The values are only in the leaves, which hold up to m keys each, are all on the same level and are linked in a list in the order of the keys, so that the keys in an interval are read in O( log n + k ) time [see range()]. The height is :math:` O( log_{lceil m / 2 rceil} n ) `: with pages of 4 KB and m = 256 a few levels index billions of keys.

The search goes down to the first child whose key is not smaller than the one looked for. The insertion goes into the leaf of the key; a leaf with m keys already splits its m + 1 keys between a new leaf on its left, with the first :math:` lceil ( m + 1 ) / 2 rceil `, and itself, and the largest key of the new leaf goes into the parent next to it; a parent with m + 1 children splits in the same way, the middle key going one level up, up to the root, which may split and give a new root with two children. The book describes the removal only as “a series of similar cases” and so it is not here.

The contracts [see File Contract.h]: the order is m > 2, as the book requires, and the invariant is the shape of the tree, checked after each insertion [see shaped()]. The operations are defined in BPlusTree.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 6.3, https://algoritmicamente.it/materiali/libro/capitoli/cap06.pdf

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

  1. Comer, The ubiquitous B-tree, ACM Computing Surveys 11(2), 121-137, 1979, doi:10.1145/356770.356776

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes