Radix Trees over Fixed-Width Integer Keys

A trie over byte strings has a height equal to the key length, and for a dictionary that height is the length of the longest key. When the keys are machine integers, the same structure takes a different character entirely: the height is fixed by the width of the integer, not by any property of the data, and it is small enough to be treated as a constant. This is the structure behind page-cache indexes, file-descriptor tables, and several in-memory maps, and its behaviour under insertion and under concurrent readers differs from a balanced tree in ways that follow directly from that fixed height.

Chunking the key

The key is a 64-bit integer, viewed as a sequence of bit fields. With a fan-out of 64, each level consumes six bits: ten levels cover 60 bits and a top level covers the remaining four, so a full 64-bit key space needs at most eleven levels. With a fan-out of 16, each level consumes four bits and the tree has at most sixteen levels. In general the height is at least ceil(w / k) for key width w and chunk width k, with equality when the top level is allowed to be partial. Implementations that fix a uniform chunk width anyway accept the extra level; the Linux kernel’s radix tree instead stores a shift value in each node, so a node covers a variable number of address bits and the height grows only as keys require it.

A node at one level is an array of 2^k child pointers. With k = 6 that is 64 pointers, 512 bytes on a 64-bit machine — eight cache lines, but allocated once per non-empty node rather than once per key. A sparse level of the tree can be represented by a smaller node type, and whether it is depends on the implementation; the pure form uses full arrays and accepts the waste at low occupancy.

The index into the array at level d is bits [d·k, (d+1)·k) of the key, counting from the most significant end. Descending is then a shift, a mask, and an array load — no comparisons, no key material examined beyond the bits at the current level. The lookup examines k bits per level and therefore reads the whole key exactly once, in pieces.

#define SHIFT 6                 /* log2 of the fan-out */
#define FANOUT (1u << SHIFT)

struct radix_node {
    void *slot[FANOUT];
};

/* Descends `levels` steps; the caller passes the height of the tree.
   Requires levels * SHIFT <= 64; a tree that covers fewer bits starts
   with a shift below 64 at the root and needs the same adjustment here. */
void *find(struct radix_node *root, uint64_t key, unsigned levels)
{
    struct radix_node *n = root;
    for (unsigned d = 0; d < levels; d++) {
        /* Consume chunks from the most significant end downward. */
        unsigned shift = 64 - SHIFT * (d + 1);
        uint32_t idx = (uint32_t)((key >> shift) & (FANOUT - 1));
        if (n->slot[idx] == NULL)
            return NULL;
        n = n->slot[idx];
    }
    return n;                   /* leaf payload lives behind this pointer */
}

The loop has no data-dependent branch except the null test, and the shift amount decreases monotonically, so the address bits are consumed in the same order in which a comparison would examine them. That last property is what makes the enumeration order of the structure match numeric order; a loop that consumed chunks from the least significant end would still find every key but would order results by reversed bit fields.

Why there are no rotations

A balanced binary tree maintains its height through rotations, and each rotation rewrites parent and child pointers at several nodes. A radix tree over fixed-width keys does not maintain its height, because the height cannot change: it is determined by the key width, and a path to a key is exactly the sequence of its bit fields. Insertion allocates the nodes along a missing path and links them; no existing node is moved, and no pointer above the insertion point changes except the one that connects the new path.

That property is worth stating precisely because it is what makes the structure usable under a read-mostly concurrency model. A reader that has descended from the root holds a pointer to a node; an insertion below that node adds children to it but does not relocate it. A reader cannot observe an inconsistent tree because the only structural change is the appearance of a new subtree, which either is visible or is not. Deletion is the asymmetric case — it removes nodes, and a reader may be traversing a node that is being freed — which is why implementations pair the structure with a deferred-reclamation discipline rather than with a lock. The details are in concurrent updates to prefix trees.

The fixed height also makes the worst case predictable. A balanced tree gives O(log n) with a logarithm over the key count; a radix tree gives O(w/k), a constant with respect to n. For a hundred million keys the balanced tree needs on the order of 27 comparisons. For a 64-bit key with 6-bit chunks the radix tree needs 11 levels, and its height would be the same for a thousand keys or a billion.

Tagging and multi-index entries

The structure as described maps one integer to one pointer. Several uses need more: the page cache needs to find every entry whose index falls in a range, and it needs to know which entries are dirty without walking the tree. The mechanism for both is metadata stored per node rather than per entry.

A tag is a bit per node recording whether any entry in that subtree carries the corresponding mark. Setting a mark on one entry sets the bit on every node on its path to the root; clearing it requires checking siblings, which is why clearing is more expensive than setting. A range query then prunes: a subtree whose tag bit is clear is skipped entirely, so scanning for marked entries costs the number of marked entries times the height, not the size of the index space. This is the trie equivalent of an interval tree’s augmentation, and it is the reason the structure can serve as a dirty-page index rather than only as a lookup table.

Range queries over keys, as opposed to tags, use the same descent. To enumerate indices in [lo, hi], the walk compares the current level’s chunk against the corresponding chunks of the bounds and visits only children whose index falls inside the interval at that level. Because the key order is the tree order — most significant bits decide first — the enumeration is in ascending index order with no sorting.

Sparse keys and the height question

A fixed height is only an advantage if the keys occupy the space it covers. A 64-bit key space is enormous, and a structure that allocates eleven levels for a thousand keys wastes most of its nodes on paths that lead to a single leaf. Implementations handle this in two ways.

The first is to choose the root height from the actual key distribution: the tree is created at a level such that all keys fall within the covered range, and it grows a level above the root when a key outside the current range arrives. A structure holding small integers therefore starts at one or two levels and gains height only when a large key forces it. The height remains bounded by the key width, so the worst case is unchanged, while the common case avoids the empty upper levels.

The second is to compress single-child paths, which reintroduces the machinery of a Patricia trie and its split-on-insert cost. Most integer radix trees do not do this, preferring the constant-height invariant and accepting some empty levels, because the concurrency benefit of never relocating nodes is worth more than the memory.

The cost of a sparse full-fan-out node is real: a node with one child still occupies 2^k pointers. For k = 6 that is 512 bytes for each node at that level, so a thousand distinct 40-bit prefixes that share no ancestor below the root cost a thousand of those nodes, about half a megabyte, before any pointer is filled in. Shrinking the fan-out to k = 4 cuts the per-node cost to 128 bytes at the price of four more levels for the same key width. The trade is between height and per-node slack, and it is the same trade as the child-representation question in a byte trie, expressed in bits instead of characters.

Comparison with a hash table

A hash table gives O(1) expected lookup with a smaller constant and a simpler node, so why use a radix tree at all? Three properties.

Order. A radix tree enumerates keys in numeric order and answers range queries by descent; a hash table answers neither without a separate ordered structure. Any index that must support “next key after x” or “all keys in this interval” is out of reach for hashing.

Growth without rehashing. A hash table that exceeds its load factor rehashes every entry, which is an O(n) pause and, under a concurrent reader, a window in which the table is being rebuilt. A radix tree grows one node at a time, and the work per insertion is bounded by the height. The absence of a global rebuild is why the structure fits read-mostly kernel paths where a rehash pause would be unacceptable.

Stable node addresses. Because nodes are never relocated, a pointer obtained during a traversal remains valid as long as the node is not freed, which permits lock-free readers. A hash table’s rehash moves every entry, invalidating every pointer a reader holds.

The price is memory. A hash table stores one entry per key with a load factor near 0.75, so its space is proportional to the key count times a constant. A radix tree stores nodes for every distinct prefix of the bit-expanded keys, which for sparse key spaces can exceed the key count by a large factor. When keys are dense — array indices, sequential identifiers — the two are close, and the radix tree wins on the ordering property. When keys are sparse random 64-bit values, the radix tree is mostly empty nodes and a hash table is the better structure.

Where the constant height stops helping

Fixed height bounds the worst case but not the constant. Each level is a dependent load, so a lookup is ceil(w/k) dependent loads in the worst case, whereas a hash table with a good load factor resolves a key in about one probe on average. For a single lookup the hash table has the smaller constant; for a lookup followed by ordered traversal, the radix tree amortizes the descent across the traversal.

This is the same tension the adaptive node layouts address from the byte-trie side: adaptive radix tree node layouts keep the fan-out high where the data justifies it and shrink the node where it does not, which is a compromise between the fixed full-array node and the sparse byte trie. The integer radix tree chooses the fixed end of that spectrum deliberately, and the choice is justified by the concurrency and ordering requirements of the indexes it serves rather than by lookup speed alone.