Introduction

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)O(k) lookup for a key of length kk — independent of how many keys the tree holds.

Watch Nodes Change Shape

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.

<!-- ART demo — shows the node type (Node4/16/48/256) for the root node as keys are added/removed -->
<div class="art-demo">
  <p class="hint">Type a word and click <b>Insert</b>. The circle shows the current ART node type and how many slots are filled. Watch it grow when you add more children than the current type can hold.</p>
  <div class="input-row">
    <input id="key-input" type="text" placeholder="Type a key..." maxlength="12" autocomplete="off" />
    <button id="btn-insert" type="button">Insert</button>
    <button id="btn-delete" type="button" class="ghost">Delete</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <div id="node-vis" class="node-vis" aria-label="ART node visualisation"></div>
  <div id="status" class="status"></div>
  <div class="key-list-label">Keys in the tree:</div>
  <div id="key-list" class="key-list"></div>
</div>

/* Styles for the ART node-type demo */
* { 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; }
/* Node visualisation 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; }
/* One accent color per node type */
.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; }
/* Slot grid showing used vs free child 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; }

// Adaptive Radix Tree node-type simulator
// ART node-type thresholds (from the 2013 Leis et al. paper):
// Node4:  up to 4 children   (grow to Node16 at 5)
// Node16: up to 16 children  (grow to Node48 at 17, shrink to Node4 below 4)
// Node48: up to 48 children  (grow to Node256 at 49, shrink to Node16 below 13)
// Node256: up to 256 children (shrink to Node48 below 37)

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Node type descriptors: name, max children, shrink threshold, grow threshold, approx. size in bytes
const TYPES = [
  { name: 'Node4',   max: 4,   shrinkAt: 0,  growAt: 5,   size: 56   },
  { name: 'Node16',  max: 16,  shrinkAt: 4,  growAt: 17,  size: 160  },
  { name: 'Node48',  max: 48,  shrinkAt: 13, growAt: 49,  size: 656  },
  { name: 'Node256', max: 256, shrinkAt: 37, growAt: 257, size: 2064 },
];
const CSS_CLASS = ['type-n4','type-n16','type-n48','type-n256'];

// Tree state — we track only unique string keys and derive the node type from the count
const keys = new Set();
let typeIdx = 0; // index into TYPES array

function nodeTypeForCount(n) {
  // choose the smallest node type that fits n children
  if (n <= 4)   return 0;
  if (n <= 16)  return 1;
  if (n <= 48)  return 2;
  return 3;
}

function setStatus(msg, cls) {
  const el = document.getElementById('status');
  el.textContent = msg;
  el.className = 'status ' + cls;
}

function render() {
  const n = keys.size;
  typeIdx = nodeTypeForCount(n);
  const t = TYPES[typeIdx];

  // Draw the node circle and metadata
  const vis = document.getElementById('node-vis');
  vis.innerHTML = '';

  const box = document.createElement('div');
  box.className = 'node-box';

  const diameter = Math.max(64, Math.min(120, 60 + n * 2));
  const ring = document.createElement('div');
  ring.className = 'node-ring ' + CSS_CLASS[typeIdx];
  ring.style.width = diameter + 'px';
  ring.style.height = diameter + 'px';
  ring.textContent = n;

  const label = document.createElement('div');
  label.className = 'node-label ' + CSS_CLASS[typeIdx];
  label.textContent = t.name;

  const cap = document.createElement('div');
  cap.className = 'node-cap';
  cap.textContent = i18nFmt('%n% / %max% children · ~%bytes% bytes', { n: n, max: t.max, bytes: t.size });

  // Draw the slot grid (one square per slot in the current node type)
  const slots = document.createElement('div');
  slots.className = 'slots';
  const displaySlots = Math.min(t.max, 48); // cap displayed slots at 48 for visual clarity even when in Node256
  for (let i = 0; i < displaySlots; i++) {
    const s = document.createElement('div');
    s.className = 'slot ' + (i < n ? 'used' : 'free');
    slots.appendChild(s);
  }

  box.appendChild(ring);
  box.appendChild(label);
  box.appendChild(cap);
  box.appendChild(slots);
  vis.appendChild(box);

  // Draw sorted key tags below the node
  const kl = document.getElementById('key-list');
  kl.innerHTML = '';
  for (const k of [...keys].sort()) {
    const tag = document.createElement('span');
    tag.className = 'key-tag';
    tag.textContent = k;
    kl.appendChild(tag);
  }
}

function insert() {
  const input = document.getElementById('key-input');
  const raw = input.value.trim();
  if (!raw) { setStatus('Type a key first.', 'bad'); return; }
  if (keys.size >= 256) { setStatus('Node256 is full (256 children).', 'bad'); return; }
  if (keys.has(raw)) { setStatus(i18nFmt('%key% is already in the tree.', { key: raw }), 'info'); input.value = ''; return; }
  const before = nodeTypeForCount(keys.size);
  keys.add(raw);
  const after = nodeTypeForCount(keys.size);
  render();
  if (after > before) {
    setStatus(i18nFmt('Node grew: %from% → %to%!', { from: TYPES[before].name, to: TYPES[after].name }), 'ok');
  } else {
    setStatus(i18nFmt('Inserted "%key%" — still a %type%.', { key: raw, type: TYPES[after].name }), 'ok');
  }
  input.value = '';
  input.focus();
}

function deleteKey() {
  const input = document.getElementById('key-input');
  const raw = input.value.trim();
  if (!raw) { setStatus('Type a key first.', 'bad'); return; }
  if (!keys.has(raw)) { setStatus(i18nFmt('%key% is not in the tree.', { key: raw }), 'bad'); return; }
  const before = nodeTypeForCount(keys.size);
  keys.delete(raw);
  const after = nodeTypeForCount(keys.size);
  render();
  if (after < before) {
    setStatus(i18nFmt('Node shrank: %from% → %to%.', { from: TYPES[before].name, to: TYPES[after].name }), 'info');
  } else {
    setStatus(i18nFmt('Deleted "%key%" — still a %type%.', { key: raw, type: TYPES[after].name }), 'info');
  }
  input.value = '';
  input.focus();
}

function reset() {
  keys.clear();
  render();
  setStatus('Tree cleared.', 'info');
  document.getElementById('key-input').value = '';
}

document.getElementById('btn-insert').addEventListener('click', insert);
document.getElementById('btn-delete').addEventListener('click', deleteKey);
document.getElementById('btn-reset').addEventListener('click', reset);
document.getElementById('key-input').addEventListener('keydown', (e) => {
  if (e.key === 'Enter') insert();
});

// Pre-load 8 sample keys so the demo opens in an interesting state
['cat','car','card','cart','cap','cow','dog','dot'].forEach(k => keys.add(k));
render();
setStatus('8 keys pre-loaded — node type is Node16.', 'ok');
Result
Console

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.

The Real Complexity

How does ART compare to the structures it competes with?

  • Lookup is O(k)O(k), where kk is the key length in bytes — completely independent of the number of keys nn. A hash table also offers O(1)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)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)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][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.

Where It Matters

ART's combination of O(k)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.

Conclusion

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)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/adaptive-radix-tree/Content licensed under CC BY-NC 4.0.