Adaptive Radix Tree

A trie (or prefix tree) stores strings character by character, sharing prefixes so that "apple" and "apricot" split only after the "apr" they both carry. Every node holds an array of child pointers, one slot per possible byte value — up to 256 slots for a full byte alphabet.

That sounds fine until you notice the waste. A node holding a single child still allocates 255 empty slots. Real datasets are sparse: IP routing tables, dictionary lookups and database indexes almost always have far fewer children per node than the alphabet allows. The empty slots burn cache lines and RAM for nothing.

Viktor Leis and colleagues solved this in their 2013 paper by introducing four node sizes — Node4, Node16, Node48, Node256 — each tuned to a different child count. A node grows when it fills up and shrinks when keys are deleted. The result is a trie that stays as compact as the data requires while still delivering $O(k)$ lookup for a key of length $k$ — independent of how many keys the tree holds.

Insert keys one by one and watch the root node move through the four ART node types. Each type is labeled with its current child count and capacity.

<!-- {{c_html_intro}} -->
<div class="art-demo">
  <p class="hint">{{hint_para}}</p>
  <div class="input-row">
    <input id="key-input" type="text" placeholder="{{input_placeholder}}" maxlength="12" autocomplete="off" />
    <button id="btn-insert" type="button">{{btn_insert}}</button>
    <button id="btn-delete" type="button" class="ghost">{{btn_delete}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div id="node-vis" class="node-vis" aria-label="{{vis_aria}}"></div>
  <div id="status" class="status"></div>
  <div class="key-list-label">{{keys_label}}</div>
  <div id="key-list" class="key-list"></div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.art-demo { max-width: 560px; margin: 0 auto; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .75rem; line-height: 1.45; }
.input-row { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .75rem; }
input { font: 14px system-ui, sans-serif; padding: .4rem .6rem; border: 1px solid #b0b8c2;
        border-radius: 7px; flex: 1 1 120px; min-width: 0; }
input:focus { outline: 2px solid #3a6dad; outline-offset: 1px; border-color: #3a6dad; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border-radius: 7px;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; cursor: pointer; white-space: nowrap; }
button.ghost { background: #fff; color: #1d3557; }
/* {{c_css_node_box}} */
.node-vis { display: flex; flex-direction: column; align-items: center; gap: .5rem;
            margin: .5rem 0 .75rem; min-height: 90px; }
.node-box { display: flex; flex-direction: column; align-items: center; gap: .3rem; }
.node-ring { border-radius: 50%; display: flex; align-items: center; justify-content: center;
             font: 700 14px system-ui, sans-serif; border: 3px solid; transition: all .35s; }
.node-label { font-size: .8rem; font-weight: 600; text-align: center; }
.node-cap { font-size: .72rem; color: #666; text-align: center; }
/* {{c_css_node_colors}} */
.type-n4  { border-color: #2a9d8f; color: #2a9d8f; }
.type-n16 { border-color: #3a6dad; color: #3a6dad; }
.type-n48 { border-color: #e76f51; color: #e76f51; }
.type-n256{ border-color: #8338ec; color: #8338ec; }
.type-empty { border-color: #ccc; color: #999; }
/* {{c_css_slots}} */
.slots { display: flex; flex-wrap: wrap; gap: 3px; justify-content: center; max-width: 320px; }
.slot { width: 14px; height: 14px; border-radius: 3px; }
.slot.used { background: currentColor; }
.slot.free { background: #e8e8e8; }
.status { font-size: .93rem; font-weight: 600; min-height: 1.4em; margin-bottom: .4rem; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info{ color: #3a6dad; }
.key-list-label { font-size: .8rem; color: #666; margin-bottom: .2rem; }
.key-list { display: flex; flex-wrap: wrap; gap: .3rem; min-height: 1.5em; }
.key-tag { background: #e8eef3; border: 1px solid #c8d5e0; border-radius: 5px;
           font: 13px ui-monospace, monospace; padding: .15rem .4rem; }

// Code not found

Notice how the node type changes automatically: Node4 handles up to 4 children, Node16 up to 16, Node48 up to 48, and Node256 up to 256. Deletion triggers the reverse — a node shrinks when it falls below the lower threshold of the next smaller type. The tree never wastes more space than the data demands.

How does ART compare to the structures it competes with?

• Lookup is $O(k)$, where $k$ is the key length in bytes — completely independent of the number of keys $n$. A hash table also offers $O(1)$ average lookup but must compute a hash and handle collisions; ART's traversal is a tight loop over key bytes.
• Node transitions are amortized $O(1)$. Growing from Node4 to Node16 copies at most 4 pointers; growing from Node48 to Node256 copies at most 48. Because the thresholds are fixed constants, the total work across all inserts is $O(n)$.
• Cache behavior is excellent. Node4 (at most 32 bytes on a 64-bit system) and Node16 both fit in a single cache line. Node256 is 2 KB but is only used when a node is nearly full — at that density a full 256-entry array is actually the most efficient representation.
• Range queries work naturally. Unlike hash tables, a trie preserves lexicographic order, so iterating all keys in $[a, b]$ is a simple in-order traversal — no sorting needed after the fact.
• The only cost: path compression ("lazy expansion") is needed to avoid long chains of single-child nodes on sparse datasets. ART uses two techniques — path compression (skip common prefixes) and lazy expansion (don't expand a leaf until a second key forces a split) — both standard in radix-tree literature.

In the original benchmark by Leis et al., ART outperformed red-black trees and B$^{+}$-trees on random integer keys by a factor of 2–4×, and matched or beat hash tables while supporting ordered operations they cannot provide.

ART's combination of $O(k)$ lookup, cache efficiency, and natural prefix ordering makes it the right index for several domains:

• Main-memory databases: the HyPer database (TU Munich) used ART as its primary index structure. Modern systems like DuckDB and Umbra draw on the same ideas. When data fits in RAM, cache misses dominate — ART's compact nodes minimize them.
• IP routing: longest-prefix matching in routers is a trie problem. ART's Node256 at the root (all 256 first-byte values are possible) and Node4/Node16 deeper in the tree match the real sparsity of routing tables.
• Auto-complete and spell-checking: tries support prefix enumeration natively; ART does it with less memory than a naïve trie while beating a sorted array on insertion cost.
• Key-value stores: systems that need ordered iteration alongside point lookup benefit from ART over a hash table. See also B-trees for the disk-based counterpart.

The core insight — that a single node format cannot be optimal for all fanout values — generalizes. Whenever you build a data structure over a byte-addressed key space, asking "how sparse is each node?" is the right first question.

The Adaptive Radix Tree makes one small conceptual leap beyond an ordinary trie: instead of committing to a single internal node format, it carries four of them and switches automatically. Node4 for sparse nodes, Node256 for dense ones, and two sizes in between — each transition triggered by a fixed threshold that costs only a constant amount of copying.

The payoff is a lookup structure that matches the real shape of the data. Sparse keys stay compact; dense keys get the direct-indexed speed of a full 256-array. Range queries come for free, cache-line usage stays low, and the $O(k)$ bound holds regardless of how many keys the tree holds.

It is a reminder that data structures need not be monolithic. The right shape for a node depends on how full it is, and there is no reason a tree cannot decide that for itself.