File BTreeMap.h

↰ Parent directory (ADS/tree)

An ordered map on a B+-tree in main memory, beyond the book: the engineered ordered DICTIONARY of Namespace ADS [see File ADT.h], the one that the benchmark of the ordered dictionaries compares with std::map, absl::btree_map and tlx::btree_map, while BPlusTree [see File BPlusTree.h] stays the tree of section 6.3 and BTree [see File BTree.h] that of Bayer and McCreight.

Definition (ADS/tree/BTreeMap.h)

Detailed Description

The pairs are in the leaves, which hold up to L of them, the keys in an array and the values in another one, so that a search reads the keys alone, and which are linked in a list in both directions; an internal node holds up to I keys and I + 1 children, the child c[ i ] having the keys in ( k[ i - 1 ] , k[ i ] ], i.e., k[ i ] is not smaller than the keys below c[ i ] and smaller than those below c[ i + 1 ]. L and I come from the bytes B of a node (512 by default, 8 lines of cache), L = B / ( sizeof( K ) + sizeof( V ) ) and I = B / ( sizeof( K ) + sizeof( void * ) ), each between 4 and 255. The nodes keep no parent and no height: the height is that of the tree, and an operation that climbs back keeps the path of its descent.

The place of a key in a node is the number of the keys smaller than it. On the arithmetic keys under std::less, the unused places of a node hold the largest value of the type (its infinity for the floating types), so that the count runs on all the places at once, with no branch and no dependence on the count of the node, as a few comparisons of vectors [see File CountLess.h] (four of AVX-512 for 32 keys of 64 bits), which beats a binary search on a few lines of cache, whose branches are mispredicted half of the times. On the other keys the place is a binary search. On the way down, the lines of the keys of the next node are all prefetched at once, so that their misses overlap instead of following one another, as in the prefetching B+-trees of Chen, Gibbons and Mowry; a search of a value prefetches the values of the leaf too, whose line is read right after the keys. The nodes come from two pools [see File ObjectPool.h] on huge pages, so that a descent misses the TLB once per 2 MB rather than once per node, and the internal nodes of a level are linked in a list, as the leaves are.

An insertion into a full node splits it in two halves, the largest key of the left one going up into the parent, which may split in turn, up to the root. An insertion past the largest key of the tree, or before the smallest one, splits the node so that the old one stays full and the new one gets the new key alone (the trick of the B-trees of Abseil and of the bulk loaders): the keys inserted in increasing order fill all the nodes, instead of half of them; and a key larger than all the others goes into the last leaf, if it has room, with no descent, since no bound of an internal node lies above the largest key. A removal that leaves a node with fewer than half of its places full either merges it with a sibling, if the two fit in one node, or takes from the sibling half of the difference, so that the two end up balanced; a merge may leave the parent short in turn, and a root with a single child gives way to it. Hence every node but those of the leftmost and of the rightmost paths, and those the removals have not touched since a split, is at least half full, so that, but for the two nodes of each level on those paths, a level of internal nodes has at least :math:` lceil I / 2 rceil + 1 ` times the nodes of the level above and the leaves hold at least :math:` lceil L / 2 rceil ` pairs each: the height of a tree of n pairs is about :math:` 1 + log_{lceil I / 2 rceil + 1} ( n / lceil L / 2 rceil ) ` at worst (5 levels for a million pairs of 64 bits, L = I = 32), and all the operations take :math:` O( ( L + I ) log n ) ` time, a few lines of cache per level. build() loads a sorted sequence bottom up in O( n ), all the nodes full.

With R, each internal node keeps the number of the pairs below each of its children, :math:` mathit{cnt}[ j ] = | { mbox{pairs below } c[ j ] } | , which an insertion or a removal adds or takes one to along its way and a split, a merge or a loan counts again on the nodes it touches ( :math: O( I ) ` children each); then rank( k ), the number of the keys smaller than k, is the sum of the counts of the children before the way down plus the place in the leaf, and select( i ), the pair of rank i, goes down to the child whose counts pass i, both in :math:` O( ( L + I ) log n ) ` time (the order-statistic tree of Cormen et al. on a B-tree).

The iterators are a leaf, a place in it and the parent of the leaf, bidirectional, on constant pairs of references ( key , value ); find() gives a value to change in place. An iterator steps to the next leaf through the children of the parent (and through the list of the parents), so that it prefetches the leaf 4 places ahead with no chase of the links between the leaves, whose misses would otherwise follow one another in a scan of a tree larger than the cache. An insertion or a removal invalidates all the iterators. Keys and values must be default constructible, the places of a node being built with the node, and a tree that shrinks keeps the memory of its pools until it is cleared.

The contracts [see File Contract.h]: after insert() the key is there and after remove() it is not; build() needs strictly increasing keys, an audit; the invariant is the order of the keys in the tree and their bounds, the depth of the leaves, the list of the leaves, the count and the padding of the unused places, an O( n ) check at the level 3 on the trees of up to 4096 pairs. The operations are defined in BTreeMap.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. Comer, The ubiquitous B-tree, ACM Computing Surveys 11(2), 121-137, 1979, doi:10.1145/356770.356776

  1. Chen, P. B. Gibbons, T. C. Mowry, Improving index performance through prefetching, Proceedings of SIGMOD 2001, 235-246, 2001, doi:10.1145/375663.375688

    1. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, chapter 17 (augmenting data structures)

  1. Graefe, Modern B-tree techniques, Foundations and Trends in Databases 3(4), 203-402, 2011, doi:10.1561/1900000028

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes