Adaptive radix tree (ART)

Deep dive

How it works

In: a binary-comparable key (bytes) · Out: the value, or none · State: the tree of Node4/16/48/256 nodes (persists between calls) · Cost: O(k) for k-byte keys, one cache miss per level

Node4:   keys[4]  | child*[4]          linear scan (sorted)
Node16:  keys[16] | child*[16]         SIMD compare of 16 bytes
Node48:  index[256] -> slot | child*[48]   index byte 0 = absent
Node256: child*[256]                   direct index

1. Convert the key to binary-comparable bytes (u64::to_be_bytes, flip the sign bit of signed ints, IEEE floats: flip sign bit if positive, all bits if negative).
2. Lookup: at depth d, find the child for byte key[d] in the node's layout; descend. A leaf stores the full key; compare it (lazy expansion means a leaf can sit above full depth).
3. Insert: descend; at an empty child, store a leaf. At a leaf with a different key, replace it by a Node4 that splits on the first differing byte. A full node grows to the next layout (4→16→48→256) by copying.
4. Path compression: each inner node stores a prefix of up to ~8 bytes that all keys below share; on mismatch, split the prefix. Optimistic variant stores only the prefix length and verifies at the leaf.
5. Delete: remove the leaf; shrink nodes with hysteresis (e.g. Node16→Node4 at 3 children) to avoid grow/shrink thrash.

Code

// ART over u64 keys (big-endian bytes). Lazy expansion, node growth; path compression omitted for brevity.
#[derive(Default)]
enum Node {
    #[default] Empty,
    Leaf(Box<(u64, u64)>),
    N4(Box<Small<4>>),
    N16(Box<Small<16>>),
    N48(Box<N48>),
    N256(Box<[Node; 256]>),
}
struct Small<const C: usize> { n: usize, keys: [u8; C], kids: [Node; C] }
struct N48 { n: usize, index: [u8; 256], kids: [Node; 48] } // index[b] = slot + 1, 0 = absent

impl<const C: usize> Small<C> {
    fn new() -> Self { Small { n: 0, keys: [0; C], kids: std::array::from_fn(|_| Node::Empty) } }
    fn pos(&self, b: u8) -> Option<usize> { self.keys[..self.n].iter().position(|&k| k == b) } // N16: SSE2 cmpeq + movemask
    fn add(&mut self, b: u8, child: Node) { // caller guarantees n < C; keys kept sorted for range scans
        let i = self.keys[..self.n].iter().position(|&k| k > b).unwrap_or(self.n);
        self.keys.copy_within(i..self.n, i + 1);
        self.kids[i..=self.n].rotate_right(1);
        self.keys[i] = b;
        self.kids[i] = child;
        self.n += 1;
    }
}

impl Node {
    fn slot(&self, b: u8) -> Option<usize> {
        match self {
            Node::N4(s) => s.pos(b),
            Node::N16(s) => s.pos(b),
            Node::N48(s) => (s.index[b as usize] as usize).checked_sub(1),
            Node::N256(_) => Some(b as usize),
            _ => None,
        }
    }
    fn kids(&self) -> &[Node] {
        match self { Node::N4(s) => &s.kids, Node::N16(s) => &s.kids, Node::N48(s) => &s.kids, Node::N256(k) => &k[..], _ => &[] }
    }
    fn kids_mut(&mut self) -> &mut [Node] {
        match self { Node::N4(s) => &mut s.kids, Node::N16(s) => &mut s.kids, Node::N48(s) => &mut s.kids, Node::N256(k) => &mut k[..], _ => &mut [] }
    }
    fn child(&self, b: u8) -> Option<&Node> {
        self.slot(b).map(|i| &self.kids()[i]).filter(|c| !matches!(c, Node::Empty))
    }
    fn add_child(&mut self, b: u8, child: Node) {
        let full = match self { Node::N4(s) => s.n == 4, Node::N16(s) => s.n == 16, Node::N48(s) => s.n == 48, _ => false };
        if full { self.grow(); }
        match self {
            Node::N4(s) => s.add(b, child),
            Node::N16(s) => s.add(b, child),
            Node::N48(s) => { s.kids[s.n] = child; s.n += 1; s.index[b as usize] = s.n as u8; }
            Node::N256(k) => k[b as usize] = child,
            _ => unreachable!(),
        }
    }
    fn grow(&mut self) {
        *self = match std::mem::take(self) {
            Node::N4(mut s) => {
                let mut t = Small::<16>::new();
                for i in 0..4 { t.add(s.keys[i], std::mem::take(&mut s.kids[i])); }
                Node::N16(Box::new(t))
            }
            Node::N16(mut s) => {
                let mut t = Box::new(N48 { n: 16, index: [0; 256], kids: std::array::from_fn(|_| Node::Empty) });
                for i in 0..16 { t.index[s.keys[i] as usize] = i as u8 + 1; t.kids[i] = std::mem::take(&mut s.kids[i]); }
                Node::N48(t)
            }
            Node::N48(mut s) => {
                let mut k: Box<[Node; 256]> = Box::new(std::array::from_fn(|_| Node::Empty));
                for b in 0..256 {
                    if let Some(i) = (s.index[b] as usize).checked_sub(1) { k[b] = std::mem::take(&mut s.kids[i]); }
                }
                Node::N256(k)
            }
            n => n,
        };
    }
}

#[derive(Default)]
pub struct Art { root: Node }
impl Art {
    pub fn get(&self, key: u64) -> Option<u64> {
        let kb = key.to_be_bytes();
        let (mut node, mut depth) = (&self.root, 0);
        loop {
            match node {
                Node::Empty => return None,
                Node::Leaf(l) => return (l.0 == key).then_some(l.1), // lazy expansion: verify full key
                _ => { node = node.child(kb[depth])?; depth += 1; }
            }
        }
    }
    pub fn insert(&mut self, key: u64, val: u64) { insert(&mut self.root, key, val, 0) }
}

fn insert(node: &mut Node, key: u64, val: u64, depth: usize) {
    match node {
        Node::Empty => *node = Node::Leaf(Box::new((key, val))),
        Node::Leaf(l) if l.0 == key => l.1 = val,
        Node::Leaf(l) => { // two keys meet: split on the byte at `depth`, then retry
            let ob = l.0.to_be_bytes()[depth];
            let old = std::mem::replace(node, Node::N4(Box::new(Small::new())));
            node.add_child(ob, old);
            insert(node, key, val, depth);
        }
        _ => {
            let b = key.to_be_bytes()[depth];
            match node.slot(b) {
                Some(i) if !matches!(node.kids()[i], Node::Empty) => insert(&mut node.kids_mut()[i], key, val, depth + 1),
                _ => node.add_child(b, Node::Leaf(Box::new((key, val)))),
            }
        }
    }
}

Complexity and constants

• Per level: Node4 scan ≤ 4 byte compares; Node16 one SSE2 compare + tzcnt; Node48 two dependent loads; Node256 one load. Cost is dominated by the cache miss per level (order of 80-100 ns from DRAM).
• Height for 8-byte keys ≤ 8; with path compression and random keys, about log256(n) + 1: 3-4 levels at 10^7 keys.
• Dense sequential keys fill Node256s: about 8 bytes per key plus leaves; sparse random keys mostly use Node4/Node16.
• Lookup throughput in the paper is in the same range as hash tables for dense keys and well ahead of comparison-based trees; range scans are an in-order walk.

Efficiency

• Cost: a lookup is one dependent cache miss per level, order of 80-100 ns each from DRAM, 3-4 levels at 10^7 random 8-byte keys. Memory is at most 52 bytes per key (Leis et al. 2013), about 8 bytes per key plus leaf for dense keys. Bound: memory latency.
• Levers:
  • SIMD compare in Node16 — one compare and tzcnt instead of up to 16 byte compares (ICDE 2013) — fan-out 5-16
  • path compression and lazy expansion — fewer levels and nodes for long shared prefixes (ICDE 2013) — string or sparse keys
  • tagged pointers with values in slots — no enum indirection, one pointer chase fewer — any production implementation
  • values stored in child slots — one pointer chase fewer per lookup — values of 8 bytes or less
  • optimistic lock coupling — readers take no locks and write no shared memory (DaMoN 2016) — concurrent reads
• Naive → standard → state of the art:
  • comparison-based balanced tree · about log2(n) misses (order of 20+ at 10^7 keys)
  • 256-way radix nodes · 3-4 misses but 2 KB per node, memory explodes on sparse keys
  • ART with adaptive nodes, path compression and OLC · same 3-4 misses at 52 bytes per key worst case

Implementation notes

• Use tagged pointers (low 3 bits = node type, or a "leaf bit" so leaves are just a pointer to a tuple or the value itself for ≤ 8-byte values). This removes the enum indirection used above.
• Store values directly in child slots when a key fits ("single-value leaves") to save a pointer chase per lookup.
• Node16 SIMD: _mm_movemask_epi8(_mm_cmpeq_epi8(_mm_set1_epi8(b), keys)) & ((1 << n) - 1). For ordered insert, flip the sign bit of bytes so signed SSE compares order unsigned bytes.
• Prefix: keep up to 8 bytes inline (pessimistic) plus the full length (optimistic beyond 8); verify at the leaf.
• Concurrency: optimistic lock coupling (version counter per node, readers validate, writers lock) or ROWEX; both from Leis et al. 2016.

Pitfalls

• Non-binary-comparable keys: little-endian ints or signed ints without flipping the sign bit give a wrong order.
• Keys that are prefixes of other keys ("ab" and "abc"): append a terminator byte or store a value slot in inner nodes.
• Shrinking a node immediately below the grow threshold causes thrash on alternating insert/delete.
• Path-compressed prefix mismatch handling is the usual source of bugs; fuzz against a BTreeMap.
• Enum-per-node designs in safe Rust add an extra indirection per level; benchmark against tagged pointers.

Variants and alternatives

In production

• Databases: HyPer and Umbra (TU Munich main-memory systems), DuckDB (indexes for PRIMARY KEY/UNIQUE and CREATE INDEX; DuckDB blog).
• Libraries: libart (C), congee (Rust, concurrent), blart and rart (Rust), go-adaptive-radix-tree (Go).
• Only database uses are sourced here; no verified ART use in networking or search engines was found (the Linux kernel and Redis use other radix-tree variants).

Implementations

Sources

• Viktor Leis, Alfons Kemper, Thomas Neumann, The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases, ICDE 2013. paper · pdf
• Viktor Leis, Florian Scheibner, Alfons Kemper, Thomas Neumann, The ART of Practical Synchronization, DaMoN 2016. paper
• Robert Binna, Eva Zangerle, Martin Pichl, Günther Specht, Viktor Leis, HOT: A Height Optimized Trie Index for Main-Memory Database Systems, SIGMOD 2018. paper
• DuckDB, Persistent Storage of Adaptive Radix Trees (ART) in DuckDB, 2022. blog