Adaptive Radix Tree, one line at a time

Each slide is one executed line of insert, search or a range scan. The tree, the key bytes and the locals show the state right after that line runs.

Operation

Source

Key bytes

Tree

node in this frame on the call path on the iterator stack created, changed or found mismatch in range already returned range end rom implied by path ␀ TERM

Detached nodes

built, not yet linked from root

Locals

dot = changed this line

Call stack

    Why an ART?

    • Compact, two ways. Vertically, path compression and lazy expansion skip chains of single-child nodes. Horizontally, a node is only as wide as its fanout needs: Node4, 16, 48, 256 as children arrive. That is closer to right-sizing an allocation than to compressing it.
    • Cache-friendly. The inner nodes are small, so the hot ones fit in CPU caches.
    • Fast point queries. A lookup costs O(k) in the key length, whatever the number of keys.
    • No rehash cliff. An insert may grow one node (Node4 → Node16), which is cheap. Many hash tables must rebuild everything at some size.
    • Range scans work. Unlike a hash table, an ART keeps keys in order. It is slower than a B+ tree, which walks sibling links between leaves, because it must climb and descend. One structure then serves constraint checks and range queries.

    Pessimistic or optimistic prefixes

    Pessimistic (this code): each inner node stores its prefix bytes, so a lookup compares them on the way down and stops at the first wrong byte. The cost is variable-length storage per node.

    Optimistic: store only the prefix length, skip those bytes without comparing, and verify the whole key once at the leaf. Nodes are smaller, but a wrong path is only noticed at the leaf.

    For a range scan the difference shows up in the seek. With stored bytes, node.content != part tells which side of lo a whole subtree is on. With skipped bytes, the seek would have to load a leaf key from the subtree to find out. The upper bound needs no jumping: a second seek finds the first word past hi.

    After DuckDB: Indexes in DuckDB (ART storage) and the ART paper by Leis et al.