File AdaptiveRadixTree.h

↰ Parent directory (ADS/dictionary)

The adaptive radix tree of Leis, Kemper and Neumann on strings, beyond the book: the engineered ordered DICTIONARY of Namespace ADS [see File ADT.h] whose keys are strings, the one that the benchmark of the tries compares with the HAT-trie of tsl, with libart and with the B-trees of strings, while Trie and RadixTree [see File Trie.h] stay the tries of Fredkin and of Morrison.

Definition (ADS/dictionary/AdaptiveRadixTree.h)

Detailed Description

A node at depth d stands for the prefixes of d bytes of its keys and branches on their byte d, and it adapts its layout to the number of its children, so that a node is never much larger than its pointers:

  • Node4 and Node16 keep up to 4 and 16 bytes sorted beside the pointers to the children of the same places; a Node16 is searched by one comparison of vectors of SSE2 (or NEON), the 16 bytes against the byte of the key at once;

  • Node48 keeps an index of 256 bytes, the place of the child of each byte among its 48 pointers (0 for none);

  • Node256 keeps the 256 pointers, the byte of the key being the place.

A node grows to the next layout when it is full and shrinks to the previous one when it holds fewer than a quarter of its places (3 in a Node16, 12 in a Node48, 37 in a Node256), with a slack against the repeated changes of layout on an insertion and a removal. A chain of nodes with a single child is compressed into the prefix of the first node that branches (the path compression): the prefix is the length of the chain and its first 8 bytes, a search skipping the bytes past 8 (the optimistic compression of the paper, the hybrid of its section III.E) and comparing the whole key at the leaf, where every search ends. A leaf holds the whole key, in one allocation with its value; the key that ends at a node, a prefix of all the keys below it, hangs from the node apart from the children, so that any string, null bytes included, can be a key. A search, an insertion and a removal take :math:` O( k ) ` time for a key of k bytes, whatever the number of the keys, with a branch of :math:` O( 1 ) ` per node; since every node but the root has at least two things below it among its children and its own key, the nodes are at most n - 1 for n keys, and the leaves n, :math:` lceil ( 16 + k ) / 16 rceil ` slots of 16 bytes for a key of k bytes and a value of 8.

A search descends with the byte of the key that follows each node, and prefetches the lines of the next node that it reads for that byte whatever the layout of the node (its header and the keys of a Node16, the place of the byte in the index of a Node48 or among the children of a Node256) while the first line is on its way. An insertion first descends as a search; if no prefix on the way was longer than its 8 bytes, the way is the one of the key, and the key goes where the search stopped, in one pass; otherwise the search ends at a leaf l below the last node that the key reaches, and a second pass goes down again to the node or the leaf whose prefix parts from the key at the first byte c where the key and l differ, the whole prefixes of the nodes on the way being those of l, with no search of a leaf below each node.

The iterators visit the pairs ( key , value ) by increasing keys (a key before the longer ones that begin with it, the children of a node by their bytes), as a string_view on the key of the leaf and a constant reference to its value, with a stack of the nodes on the way; forEach() and forPrefix() visit all the pairs, and those whose key begins with a prefix, by a recursion with no stack, and find() gives a value to change in place; the visits prefetch the children of a Node4 or of a Node16, and the iterators those of the next sibling too, so that the leaves of a subtree are on their way while the one before is visited. An insertion or a removal invalidates the iterators. The internal nodes come from pools [see File ObjectPool.h] on huge pages, the leaves from slabs of 16 to 512 bytes in steps of 16, each size with the list of its free slots, cut from blocks that double up to 2 MB (the larger leaves come from the allocator), so that a leaf costs no call to the allocator.

The contracts [see File Contract.h]: after insert() the key is there and after remove() it is not; the invariant is that the keys of the leaves extend the paths that lead to them, that every node but the root branches or ends a key, that the bytes of a node are sorted and its layout the one of its count, and that the leaves are size(), an O( n ) check at the level 3 on the trees of up to 2048 keys. The operations are defined in AdaptiveRadixTree.tpp.

  1. Leis, A. Kemper, T. Neumann, The adaptive radix tree: ARTful indexing for main-memory databases, Proceedings of ICDE 2013, 38-49, 2013, doi:10.1109/ICDE.2013.6544812

  1. Bonwick, The slab allocator: an object-caching kernel memory allocator, Proceedings of the USENIX Summer 1994 Technical Conference, 87-98, 1994

    1. Morrison, PATRICIA: practical algorithm to retrieve information coded in alphanumeric, Journal of the ACM 15(4), 514-534, 1968, doi:10.1145/321479.321481

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes