Adaptive Radix Tree Node Layouts

The two obvious byte-trie layouts both lose. A full 256-way node spends 2 KB per prefix and most of it is empty. A single-width compact node saves space but pays a search loop on every child access, and the loop’s cost grows with degree. The adaptive radix tree, introduced by Leis, Kemper, and Neumann in 2013, refuses the choice: it allocates a node whose width matches the number of children the node actually has, and it makes every width’s lookup branch-free or nearly so. The result keeps lookup at one node touch per key byte while shrinking the average node to tens of bytes.

Four widths and the growth path

A node exists in one of four forms, distinguished by a type tag in its header.

A 4-node holds up to four (key byte, child pointer) pairs as two parallel arrays, and finds the child by comparing all four keys at once. The comparison is the point: four byte comparisons can be done with a single 32-bit load and a bit-manipulation sequence, or with a SIMD compare against a broadcast byte on machines that have wider registers, producing a mask whose set bits identify matches. The cost is one branch on whether the mask is zero, not four branches.

A 16-node holds up to sixteen pairs, again with a SIMD comparison — sixteen key bytes fit in one 128-bit register, but the child pointers that must come back are 64-bit, so the match mask is converted to an index with a bit scan and used to select from a parallel pointer array. Beyond sixteen children the mask no longer fits in one register, and a different structure takes over.

A 48-node holds a 256-byte array mapping each possible key byte to a slot index 0–47, plus 48 child pointers. Lookup is one indexed load to get the slot, then another to get the pointer: two dependent loads, but no comparison and no branch beyond a null check. The 256-byte table is the reason the width is capped at 48 — the table’s size is fixed by the alphabet, and a byte of slot index can address only 256 slots, of which the null value takes one.

A 256-node is the full array, one pointer per byte value, 2 KB. It is used only when a node genuinely has more than 48 children, which for natural-language keys is rare and for binary keys is not.

Nodes grow by reallocation: a 4-node that receives a fifth child is copied into a fresh 16-node, and the parent’s pointer is updated. Growth is one-way in the common case, and the copy is bounded by 2 KB, so insertion cost stays constant per level. Shrinking on deletion is optional; implementations that skip it accept the memory.

Node type	Children	Key storage	Approximate size
4	1–4	4 key bytes	~48 bytes
16	5–16	16 key bytes	~160 bytes
48	17–48	256-byte index table	~660 bytes
256	49–256	none	~2 KB

Path compression inside the header

ART compresses single-child chains, but not by storing edge labels. Instead the bytes that a node would otherwise have spent on chain nodes are absorbed into that node’s parent — or, for a chain above the root, into the root itself — as a prefix: a length plus up to eight bytes of the compressed path, stored inline in the parent’s header. A lookup compares those bytes against the query at the current depth, advances by the length, and only then descends to a child.

#include <stdint.h>
#include <string.h>

enum node_type { N4, N16, N48, N256 };

typedef struct {
    uint8_t type;        /* enum node_type */
    uint8_t count;       /* number of children present */
    uint8_t prefix_len;  /* length of the compressed path, may exceed 8 */
    uint8_t prefix[8];   /* first eight bytes of that path, inline */
} header;

/* Compares the query against the stored prefix. Returns 1 on a match. */
static int match_prefix(const header *h, const unsigned char *key,
                        unsigned depth, unsigned klen)
{
    unsigned n = h->prefix_len < 8 ? h->prefix_len : 8;
    if (depth + n > klen) return 0;
    return memcmp(h->prefix, key + depth, n) == 0;
}

The truncation to eight bytes is why prefix_len is stored separately from the compared length: the header records the true length, but only the first eight bytes are kept inline, and the remaining bytes beyond the eighth are not stored a second time — they are the key bytes that the child’s own prefix also begins with, so the path continues across the chain of nodes. A lookup that trusted prefix_len as a comparison length would read past the array; one that trusted only the eight stored bytes would accept keys that differ beyond the eighth byte unless the depth were advanced by the full length rather than by the compared length.

The eight-byte cap is deliberate: eight bytes is one machine word, so a comparison that fits is a single load and compare. A long chain therefore becomes a chain of nodes each holding eight prefix bytes — far fewer than one node per byte, but not the single node or two a full Patricia edge would give. The design accepts partial compression in exchange for a fixed-size header that never needs an external allocation.

Insertion under this scheme is where the difficulty lies. When a new key diverges inside an existing node’s prefix, the node must be split: the common part stays in the parent, the differing byte becomes a branch with two children, and the two tails become the children’s prefixes. This is the Patricia split, expressed in a fixed header. An implementation must compare all prefix_len bytes, restoring the ones past the eighth from the chain, before it can know where the divergence lies; getting that wrong produces a lookup that descends to the wrong leaf.

Lazy expansion and leaf types

ART distinguishes two leaf kinds. A single-value leaf stores a pointer to the record; a multi-value leaf stores a list of records that share the full key. The distinction matters for non-unique indexes, where several rows map to the same key, and it avoids allocating a subtree for a key that has no children.

The more consequential decision is lazy expansion: a node is created only when a second key needs it. A key that shares no prefix with anything else sits directly under its parent’s child pointer as a leaf, with no intermediate node at all. When a second key arrives that diverges from it, the leaf is replaced by an internal node with two children. This keeps the node count close to the key count for sparse tries, and it makes the common case of a random key set — where most keys diverge in their first few bytes — very compact.

The cost is that the leaf must allow a mismatch to be detected. With a single-value leaf holding only a record pointer, the lookup that reaches it must compare the record’s key with the query, which is an extra dependent load on the last step; storing the minimum key of the leaf’s subtree in the header, or checking the whole key against the record anyway, are the two ways implementations resolve it.

What the header costs and what it buys

Packing type, child count, prefix length, and prefix bytes into a fixed header makes every node’s first cache line contain everything needed to decide the next step. A lookup touches one cache line per level, and the level count is the key length divided by the average compressed path, which is far below one per byte for realistic keys.

The trade is against the double-array layout, which has no header at all and costs eight bytes per state. ART’s smallest node is roughly forty bytes, so it is five times larger per node than a double-array state. It wins when the trie must be mutated, because the double array cannot insert without relocating families of states, and it wins when key lengths vary enough that a fixed two-array layout wastes space on gaps. It loses on purely static data, where the double array’s smaller footprint and single-allocation locality are strictly better.

The second trade is against a plain compressed trie. ART’s partial prefix means a long shared prefix costs several nodes rather than one, so a key set with very long common prefixes — URLs, file paths — pays more nodes than a Patricia trie would. In exchange, every node is a fixed size, allocated from a pool, and can be freed individually without touching label buffers.

Where the fan-out assumption breaks

ART’s node choice is driven by degree, and its performance claim rests on degrees being small. That holds for text keys with a moderate alphabet and for keys whose early bytes are diverse. It does not hold for keys that are nearly identical in their first bytes — a key set with a shared 32-byte prefix and one differing byte at the end puts every key through a long compressed path and then a single high-degree node, which is the case ART handles least well.

It also does not hold for adversarial key sets that force 256-way nodes throughout, where the memory reverts to the dense-array cost the structure was designed to avoid. A hash of the key before indexing, or a byte order chosen so that the discriminating bytes come first, restores the assumption — the same observation that makes radix trees over fixed-width integer keys choose their chunk order deliberately.

Finally, ART’s original form assumes a single writer. Node growth reallocates a node and updates its parent, which a lock-free reader tolerates only if the swap is published as a single aligned store and the old node is reclaimed later; the techniques for making that safe belong to concurrent updates to prefix trees. The structure’s speed comes partly from the assumption that the read path is not synchronizing, and that assumption is a design constraint, not an implementation detail.