Adaptive Radix Tree

When most of a database fits in memory, index performance is no longer dominated by disk I/O. It becomes a CPU problem: cache misses, branch mispredictions, pointer chasing, and memory bandwidth start to matter a lot.

Hash tables are usually very fast for point lookups because they avoid ordered traversal. Given a key, we compute a hash value and jump directly to a bucket. But this speed comes with a trade-off: hash tables scatter keys across the table, so they do not naturally keep data sorted. That makes ordered operations such as range scans, prefix lookups, min, max, and top-N harder or impossible without extra structures.

Comparison-based trees, such as red-black trees or B-trees, solve the ordering problem because they keep keys sorted. But lookups still involve repeated key comparisons, data-dependent branches, and pointer traversal. For random lookups, branch outcomes are hard to predict; and because the next node address is only known after loading the current node, traversal can suffer from cache misses and dependent memory loads.

Radix trees do not remove all of these hardware costs. They are still pointer-based trees. What changes is the work done at each level: instead of repeatedly asking "is the search key less than this stored key?", a radix tree consumes chunks of the key and uses each chunk to select the next child. The problem is the space trade-off: a plain 8-bit radix tree may reserve room for 256 child pointers per internal node. ART keeps the radix-tree traversal model, but uses adaptive node layouts (Node4, Node16, Node48, Node256), lazy expansion, and path compression to keep the tree shallow without paying that full memory cost everywhere.

A radix tree is a trie-based data structure used to store and retrieve keys. Keys can be strings, integers, or custom types, as long as they are encoded into bytes.

Unlike a traditional trie, which often processes one character at each level, a radix tree generalizes this idea by processing a fixed number of bits at each level. This number is called the span $s$ . At each level, the tree extracts the next $s$ bits from the key and uses their value to select a child. Therefore, keys must first be represented as a sequence of bits or bytes (which means that the keys used in radix tree operations must be encoded into bytes).

For example, if we encode the string "CAT" using the ASCII value of each character, we get:

C = 01000011
A = 01000001
T = 01010100

C = 01000011
A = 01000001
T = 01010100

The encoded key is 010000110100000101010100, which contains 24 bits. If we use the span value $s =8$ , then the radix tree processes one byte (8 bits) at each level which is equivalent to one single character at each level.

root
└── 01000011 (C)
    └── 01000001 (A)
        └── 01010100 (T)

root
└── 01000011 (C)
    └── 01000001 (A)
        └── 01010100 (T)

At each level, the radix tree reads the next $s$ bits and uses their value to select a child. Since $s$ bits can represent $2^s$ different values, each node can have up to $2^s$ children.

For example, if $s=8$ each level processes one byte and each node can have up to $256$ children. If $s = 4$ , each level processes four bits and each node can have up to $16$ children.

Therefore:

The height of the tree depends on the encoded key length and the span value $s$ , not on the number of elements in the tree. If the longest key has $k$ bits, the maximum tree height is $\left\lceil \frac{k}{s} \right\rceil$ .

A radix tree contains two main types of nodes:

Internal nodes store pointers to child nodes. Each child corresponds to one possible value of the next $s$ -bit portion of the key.

In practice, the span $s$ is often set to $8$ bits. Therefore, each internal node can have up to: $2^8 = 256$ children

A traditional implementation uses an array with $256$ entries. Each entry stores a pointer to a child node, or null if no child exists for that byte value.

During traversal, the next $8$ -bit portion of the key is interpreted as an unsigned integer between $0$ and $255$ . This value is used directly as the array index.

For example, if the next byte has the numeric value $65$ , the tree follows the pointer value at: children[65]

A leaf stores the value associated with a key. There are several possible implementations:

Single-value leaf: A dedicated leaf object stores one value. The leaf may also store the complete key or a pointer to the corresponding database record.

Radix tree with separate leaf nodes for CAR and CAT

Multi-value leaf: If the value can fit into the slot, we can optimize by storing it directly in the slot. This avoids creating many separate leaf objects, but it requires all keys to have the same length. This is because the leaf node only contains the values. If key lengths are variable, Key A could be a prefix of Key B. Since we only store the value in the leaf node and lack pointers to other nodes, we wouldn't be able to traverse further down to Key B. For example:
```
CAR  → value1
CART → value2
```
```
CAR  → value1
CART → value2
```
A multi-value leaf could store the value for CAR, but it would have no pointer to continue traversal for CART.

Radix tree with CAR and CAT values stored directly in child slots

Combined pointer/value slots: This solves the limitation of the multi-value leaf node. Instead of forcing an entire node to store only values, each slot in an internal node can hold either a child pointer or a direct value. One common approach to distinguish between a pointer and a value is to use a tag bit - which is usually the lowest bit of the value held in the slot. Values must be encoded so that the reserved bit is available.
- Tag = 0: The slot holds a Child Pointer (keep traversing deeper).
- Tag = 1: The slot holds a Value Payload.
  Radix tree with combined child-pointer and value slots for CAR, CART, and CARRY

In real-world application, using the single-value leaves is the most general method as it allows keys and values of varying length.

What makes radix trees practical for long keys is that we can reduce both height and memory usage. ART mainly uses two techniques for this: lazy expansion and path compression.

Lazy expansion means that a radix tree creates internal nodes only when they are actually needed. If there is only one key below a path, ART can store the full key in the leaf and delay creating inner nodes until another key shares part of that path.

Suppose we insert only one key:

"FOOD" -> value

"FOOD" -> value

Without lazy expansion, the tree may create a full path:

root
└── F
    └── O
        └── O
            └── D → Leaf("FOOD")

root
└── F
    └── O
        └── O
            └── D → Leaf("FOOD")

But this is unnecessary because there is only one key.

With lazy expansion, the tree stores the leaf directly:

root
└── Leaf("FOOD", value)

root
└── Leaf("FOOD", value)

Later, when another key such as "FOOL" is inserted, as we need to distinguish them, we actually create an internal node.

root
└── F
    └── O
        └── O
            ├── D → Leaf("FOOD")
            └── L → Leaf("FOOL")

root
└── F
    └── O
        └── O
            ├── D → Leaf("FOOD")
            └── L → Leaf("FOOL")

If several nodes form a long chain with only one child at each level, ART compresses that chain into a prefix stored in one node.

Since FOOD and FOOL share the prefix FOO, we can store that shared prefix once and branch only at the differing byte.

root
└── prefix "FOO"
├── D → Leaf("FOOD")
└── L → Leaf("FOOL")

root
└── prefix "FOO"
├── D → Leaf("FOOD")
└── L → Leaf("FOOL")

By doing so, we can save the memory & reduce the height as well.

In the path compression, we have 2 strategies:

In the pessimistic strategy, each internal node stores the actual compressed prefix in a variable-length byte array.

root
└── Internal node
prefix = "FOO"
├── D → Leaf("FOOD")
└── L → Leaf("FOOL")

root
└── Internal node
prefix = "FOO"
├── D → Leaf("FOOD")
└── L → Leaf("FOOL")

In this case, actually in the leaf node, we don’t need to store the entire key, as we can build the key from the path traversal and from the values stored in the compressed nodes.

In this strategy, at the inner node, we don’t store the compressed prefix, but only the length of shared prefix. On searching for key, when encountering compressed inner node with only length, we can just skip that length in the searching key.

root
└── Internal node
shared_prefix_length = "3"
├── D → Leaf("FOOD")
└── L → Leaf("FOOL")

root
└── Internal node
shared_prefix_length = "3"
├── D → Leaf("FOOD")
└── L → Leaf("FOOL")

This strategy requires the leaf node to store the entire key, so that when we reach the leaf, we can compare the search key with the leaf key to check whether it matches or not.

In practice, we usually use hybrid approach, starting the pessimistic but fixed size prefix, when the size exceeds a threshold, we switch to optimistic.

An important property of an index is whether it preserves the natural order of the data. If the data is sorted, it facilitates the implementation of ordered range scan or lookups for min, max, top-N,…

One problem with Radix Tree so far is that keys are ordered bitwise lexicographically. It works well with some data types such as ASCII encoded character strings, but it’s broken with numbers.

For example, negative two's-complement signed integers are lexicographically greater than positive integers.

Why? Because in two’s-complement encoding, the most significant bit is the sign bit:
```
0 = non-negative
1 = negative
```
```
0 = non-negative
1 = negative
```
Using 8-bit integers:
```
+1 = 00000001
+2 = 00000010
-2 = 11111110
-1 = 11111111
```
```
+1 = 00000001
+2 = 00000010
-2 = 11111110
-1 = 11111111
```
Lexicographic comparison checks from left to right. Since 1 is greater than 0, every negative encoding starts after every positive encoding:
```
00000001  <  11111111
   +1            -1
```
```
00000001  <  11111111
   +1            -1
```
So although numerically: -1 < +1 their raw encodings compare as: 00000001 < 11111111

To resolve this issue, we need to transform the keys to have the correct order by the data type. It’s called transformation binary-comparable keys.

Radix trees require keys where byte-by-byte comparison (memcmp) matches the natural data type's order:

$x < y \iff \operatorname{memcmp}(t(x), t(y)) < 0$
$x > y \iff \operatorname{memcmp}(t(x), t(y)) > 0$
$x = y \iff \operatorname{memcmp}(t(x), t(y)) = 0$

Here are some norm transformation of some data types:

Unsigned Integers: Native order works—just convert to Big-Endian so most-significant bytes come first.
Signed Integers: Flip the sign bit (x XOR 2^(b-1)) so negative numbers sort before positive ones, then store as Big-Endian.
Floating Point: Map sign/class (NaNs, zeroes, infinities) into ordered integer ranks using a few fast bitwise/arithmetic steps.
Strings: Use standard byte encoding (or UCA for Unicode) and append a unique terminator byte (e.g., 0x00) so no key is a prefix of another.
NULLs: Reserve a unique byte sequence (e.g., 0x00...00 mapped to rank before all valid values) by extending key length only where collisions occur.
Compound Keys: Transform each column independently and concatenate the byte arrays sequentially.

One problem with a traditional radix tree is that every internal node allocates a fixed-size array of child pointers. Even when most entries are null, each null entry still occupies one pointer-sized slot, resulting in significant memory waste for sparse nodes.

ART solves this by using four adaptive internal-node layouts:

Node4: Node can stores up to 4 pointers. It uses an array of length 4 for key, and another array of same length for pointers.

Node4 layout with four key bytes and four child pointers

Node16: Used for storing between 5 and 16 child pointers. It uses an array of length 16 for keys, and another array of 16 for pointers.
Node16 layout with sixteen key bytes and sixteen child pointers
Node48: Used for storing between 17 and 48 child pointers. But it uses array of length 256 for keys, and array of 48 for pointers.
- Why? if we use array of 48 for keys, when searching for key, we need to search through up to 48 key bytes for find the matching one. This lookup is acceptable in node4 and node16 as number of keys is small, and especially, for node16, node4 we can use SIMD (Single Instruction, Multiple Data). By using array of 256 for keys, the lookup becomes:
markdown
```
slot = childIndex[nextByte];
child = children[slot];
```
```
slot = childIndex[nextByte];
child = children[slot];
```
Node48 layout with a 256-entry child index and 48 child pointers
Node256: An array of 256 pointers, used for storing between 49 and 256 entries. It’s just like the traditional radix tree.
Node256 layout with direct indexing into 256 child pointers

Based on the number of children we can update the node type to the appropriate one, which can reduce the memory usage.

That’s why we call it “Adaptive Radix Tree”.

A search starts at the root and repeatedly follows the child associated with the next key byte.

Traversal stops when:

a matching leaf is found;
a required child does not exist;
or a compressed prefix does not match.

Adaptive radix tree search flowchart with leaf and compressed-prefix checks

Note that a leaf match should still be verified against the complete key stored in the leaf or retrievable from the database record. Lazy expansion can truncate the path before the leaf, and optimistic path compression may skip prefix bytes instead of storing all of them in internal nodes. Therefore, reaching a leaf only tells us that the traversal followed the available discriminating bytes; before returning the value, ART must confirm that the full search key actually matches the leaf key.

When finding for the child, based on the node type, the lookup strategy can be different.

Node type	Lookup strategy
`Node4`	Scan up to four key bytes
`Node16`	Compare all key bytes with SIMD, or use binary search
`Node48`	Use the key byte in `childIndex`, then access `children`
`Node256`	Use the key byte directly as the array index

Adaptive radix tree insertion flowchart for null slots, existing leaves, and internal nodes

Case 1: Empty position

If the current pointer is null, ART stores the new leaf there.

Before:

root
└── null

Before:

root
└── null

After inserting "CAT":

root
└── Leaf("CAT")

After inserting "CAT":

root
└── Leaf("CAT")

Case 2: Existing leaf - lazy expansion

Suppose "FOOD" already exists:

root
└── Leaf("FOOD")

root
└── Leaf("FOOD")

Now insert "FOOL".

ART compares both keys and finds the shared prefix "FOO":

FOOD
FOOL
^^^

FOOD
FOOL
^^^

It replaces the existing leaf with a new internal node:

root
└── prefix "FOO"
    ├── D → Leaf("FOOD")
    └── L → Leaf("FOOL")

root
└── prefix "FOO"
    ├── D → Leaf("FOOD")
    └── L → Leaf("FOOL")

This is how insertion handles lazy expansion.

Case 3: Compressed-prefix mismatch

Suppose the tree contains:

prefix "FOO"
├── D → Leaf("FOOD")
└── L → Leaf("FOOL")

prefix "FOO"
├── D → Leaf("FOOD")
└── L → Leaf("FOOL")

Now insert "FAR".

Compare the compressed prefix with the new key:

Stored prefix: F O O
New key:       F A R
                 ^
             mismatch

Stored prefix: F O O
New key:       F A R
                 ^
             mismatch

ART creates a new internal node above the existing node:

root
└── prefix "F"
    ├── A → Leaf("FAR")
    └── O → existing subtree
            ├── D → Leaf("FOOD")
            └── L → Leaf("FOOL")

root
└── prefix "F"
    ├── A → Leaf("FAR")
    └── O → existing subtree
            ├── D → Leaf("FOOD")
            └── L → Leaf("FOOL")

The old compressed prefix is shortened because part of it is moved into the new parent.

Case 4: Full internal node

If the matching child does not exist, ART adds a new child.

However, the current node may already be full:

Node4 with 4 children
+ one new child

Node4 with 4 children
+ one new child

ART grows it into the next node type:

Node4   → Node16
Node16  → Node48
Node48  → Node256

Node4   → Node16
Node16  → Node48
Node48  → Node256

The existing entries are copied into the new representation, and then the new child is added.

Deletion is roughly the reverse of insertion. ART first finds and removes the leaf. It may then shrink or remove internal nodes.

Adaptive radix tree deletion flowchart showing node shrinking and parent removal

A node may shrink through the reverse sequence:

Node256 → Node48 → Node16 → Node4

Node256 → Node48 → Node16 → Node4

If deletion leaves an internal node with only one child, that node is unnecessary.

For example:

Before deletion:

prefix "FOO"
├── D → Leaf("FOOD")
└── L → Leaf("FOOL")

Before deletion:

prefix "FOO"
├── D → Leaf("FOOD")
└── L → Leaf("FOOL")

Delete "FOOL":

prefix "FOO"
└── D → Leaf("FOOD")

prefix "FOO"
└── D → Leaf("FOOD")

Because the internal node now has only one child, ART can remove it and merge the path:

Leaf("FOOD")

Leaf("FOOD")

or merge its compressed prefix into the next internal node, depending on the remaining subtree.

ART was originally designed as an in-memory index, not as a concurrent data structure. Once multiple threads can read and update the tree at the same time, we need a synchronization strategy. In this section, we look at two approaches: Optimistic Lock Coupling and ROWEX.

Lock coupling (aka hand-over-hand lock) holds at most 2 locks at a time during traversal. It’s the standard method for synchronizing B-tree.

Below is a visualization of how lock coupling works. Basically, we hold 2 locks on parent and child. On traversal, we unlock parent, and lock the grandchild, so on and so on.

Lock coupling traversal that acquires a child lock before releasing the parent lock

Why do we sometimes need two locks? A modification can touch both the current node and its parent. For example, if a node grows/shrinks, we may create a new node and update the parent’s child pointer to point to it. Lock coupling protects this by locking the parent edge and the current node together while the change is made.

But this locking mechanism has drawback, it performs very badly on modern multi-core CPUs even if there’s no conflict at all, i.e in read-only workloads. Why?

In multi-core CPUs, cores cache some data in their L1/L2 caches to avoid RAM fetch. When the data is updated by one core, the data cached in other cores’ must be invalidated.
To acquire a “read” lock, a thread (core) must physically write to the lock field(s) of the node. If this field is cached in cache layers of multiple cores, all those cache data must be invalidated. Thing gets worse if multiple cores update the lock field at the same time, causing the cache line to be invalidated multiple times. This makes the root node and other nodes close to it become content points, as every operation must start from root node.

The basic idea of optimistic lock coupling is that it assumes that there will be no concurrent modification. Only write operations acquire locks, reads do not.

Internally, an optimistic lock consist of a lock and a version counter.

Write operation: “Fight” for the lock, increase the version when finishing its modification.
Read operation: Do not acquire any lock at all. On reading path, before examining node, it checks whether its parent version is updated or not. If yes, we restart the read operation from the beginning. Let’s take this as an example, for simplicity, I’ll draw a very simple trie here
Optimistic lock coupling example with versioned nodes A, C, and E
The read process can be simplified by following steps:
1. Read A → record version v5
2. Examine A
3. Read C → record version v3
4. Recheck A to ensure that the version is still v5, if not, restart the process from step 1.
5. Examine C
6. Read E → record version is v6
7. Recheck C to ensure that the version is still v3, if not, restart the process from step 1.
8. Examine E In the examine step we do some actions: Matching check, leaf node check, nullish check… after each check, before returning we also check node’s version again. An optimistic read records a node’s version instead of acquiring a read lock. Before dereferencing a child pointer, and before returning a result, it checks that the version is unchanged and the node was not locked or marked obsolete. If validation fails, the operation restarts from the root.

One drawback of Optimistic Lock Coupling is that reads may restart. In read-heavy workloads, repeated restarts can waste work. ROWEX takes a different approach: writers still synchronize, but readers traverse without locks or version checks. It’s called Read-Optimized Write Exclusion (ROWEX)

The core philosophy of ROWEX is simple: Writers must ensure that all the updates are in a safe, consistent state which allows every reads to traverse the tree without any lock intervention at all.

For small changes such as updating the child pointer, node metadata, it uses atomic instructions at the CPU level. As the changes are atomic, the readers never read half-written memory state.

When a node needs to grow or shrink, the writer can not modify it in place as it would break the node for active readers. Instead, ROWEX uses following approach:

Lock the current node and its parent.
Build a brand-new, larger node in a separate area of memory and fully initialize it.
Swap the parent's pointer atomically so it now points to the new node.
Mark the old node as "obsolete" and release the locks.

This is a tricky one, let’s take a look at following example:

We have a key: “WATER”, as the path compression, we don’t have 5 nodes W, A, T, E, R , instead just 2 nodes: W and ATER

Compressed ART path for WATER represented as W then ATER

Now, we need to insert another key: WASH, as WATER and WASH share the same prefix WA , we need to create another node A , and update the current ATER to TER only. The final state looks like:

ROWEX path-compression split after inserting WASH beside WATER

So we need to do 2 things:

Insert a new node A
Update the prefix of ATER to TER

Unfortunately, these 2 actions can’t be done atomically. So if the reader traverse the tree in the middle of update, we run into problem.

For example, let’s call the node with prefix ATER is X a reader is searching for WATER at exactly right after the moment we update ATER to TER, but before linking the node A to W and TER , we have following states:

The reader is at the Root, sees the pointer for W, and jumps to node X.
By the time it lands on Node X, the writer has already updated the prefix to TER.
The reader knows it just match W (byte index 1). It looks at Node X and sees a 3-letter prefix (TER). As we use relative math, it compares the next 3 letters of its search word (ATE from W - ATE - R) against the node’s prefix TER
As the ATE does not match TER, the reader thinks the word WATER doesn’t exist and return Not Found error.

To resolve this without locking, ROWEX adds an immutable level field to every node’s metadata upon creation. Rather than tracking where a node starts, the level measures where the node ends—specifically, the absolute byte index in the key where the node branches to its children. Before making any string comparisons, the reader checks if its current byte index matches the node’s calculated start position:

$\text{Expected Start Index} = \text{node.level} - \text{node.prefix\_length}$

If they match: The path is consistent. The reader safely compares the bytes.
If they do not match: The reader has reached a node whose prefix was shortened by a concurrent split. The reader must not blindly compare only the remaining suffix and return success. It can continue only if the missing prefix bytes are validated later, for example by comparing the search key with the full key stored in or retrievable from the leaf/database record.

Let’s get back to the above example:

Node X original prefix is ATER (length 4). Because it handles bytes 1 through 4, its children branch at Byte 5. Node X’s level is set permanently to 5.
The writer inserts WASH and shrinks Node X's prefix to TER (length 3). Node X’s level remains 5.
A reader arrives at Node X expecting to look at byte index 1. It calculates: $\text{Expected Start Index} = 5 - 3 = 2$ . Since $2 \neq 1$ , the reader detects a gap. It knows that byte index 1 was skipped by the path it observed. Therefore, a suffix match against TER is not enough; before returning a value, the lookup must validate the complete key, including the missing A, against the full key stored in or retrievable from the leaf/database record.

The original ART paper compares ART with other in-memory index structures using both microbenchmarks and the TPC-C benchmark inside HyPer. The useful takeaway is not that ART removes every hardware cost, but that it gets close to hash-table lookup performance while still preserving ordered-index operations.

Some concrete numbers:

Space bound: ART has a worst-case space bound of 52 bytes per key, even for arbitrarily long keys.
Practical space usage: In the TPC-C experiment, dense integer indexes used about 8.1 bytes per key. A string-heavy customer index used 32.6 bytes per key, still below the worst-case bound.
Lookup cost: With 16M keys, ART lookup took about 188 cycles for dense keys and 352 cycles for sparse keys. The hash table took about 191 cycles, while FAST took about 461 cycles.
Cache behavior: With dense keys, ART had about 1.2 L3 cache misses per lookup, compared with 2.4 for both FAST and the hash table.
End-to-end result: In HyPer running TPC-C, ART was almost 2x faster than the hash-table + red-black-tree setup and almost 4x faster than using a red-black tree alone.

So the trade-off is clear: a hash table is still an excellent choice for pure point lookups, but ART is compelling when we need point lookups, inserts, deletes, ordered scans, and predictable memory usage in the same index structure.

ART is a good fit for in-memory indexes that need more than exact-match lookup. It is especially attractive when:

keys can be transformed into byte-comparable form;
point lookups are important, but we also need ordered operations such as range scan, prefix lookup, min, or max;
the key distribution is sparse enough that a fixed 256-pointer radix node would waste too much memory;
predictable memory usage matters more than the absolute simplest implementation.

ART is usually not the first choice when the workload is only exact-match lookup and ordering does not matter. In that case, a well-engineered hash table is simpler and can be faster. It is also not ideal for large scan-heavy workloads where a B-tree or columnar scan can walk contiguous data more efficiently.

Some real-world uses:

HyPer: ART was originally evaluated as a main-memory database index in HyPer, where it performed very well on TPC-C while still supporting ordered index operations.
PostgreSQL: PostgreSQL 17 added an ART-based radix tree template and uses it internally for TidStore, which stores large sets of tuple IDs during VACUUM. This is an internal storage structure, not a replacement for PostgreSQL's normal user-facing B-tree indexes.
DuckDB: DuckDB uses ART indexes for primary key, foreign key, and unique constraints, and can also use ART indexes for highly selective queries.