Child Representation and the Branching Factor Problem in Tries

A trie is usually described by its edges: one edge per character, a path from the root spelling each key. That description fixes the lookup cost at one child transition per byte of the key, and it says nothing about where the cost actually lands. Every trie implementation answers a single question differently — given a node and a character, how the child is found — and that answer determines memory consumption, lookup speed, and whether the structure can be updated at all. Two tries with identical shape can differ by a factor of a hundred in size depending on this choice alone.

The node that is mostly empty

Consider keys drawn from printable ASCII. At a node three levels deep, the number of children is the number of distinct characters that continue some key at that position. For a natural-language dictionary this is usually one or two; a node with ten children is unusual. The branching factor of the alphabet is 128 or 256, but the branching factor of any actual node is near one.

That gap is the whole design problem. A representation sized for the alphabet pays for 256 slots to hold an average of one. A representation sized for the actual children pays a search cost per lookup. Which of the two dominates depends on how many nodes exist, and a trie has one node per distinct prefix, so the node count is roughly the total number of key bytes. A dictionary holding a million keys of ten bytes each has on the order of ten million nodes before any compression of single-child chains. At eight bytes per pointer, a dense 256-way node is 2048 bytes; multiplying by ten million gives twenty gigabytes before any key text is stored. The same dictionary with four bytes of child storage per node fits in tens of megabytes. The alphabet is not the thing to size for.

There is a second, subtler constraint: a lookup touches one node per byte, and each touch is a dependent load — the address of the next node comes from the contents of the current one. On a modern processor a cache miss costs on the order of a hundred cycles and cannot be overlapped with the next step, because the next step does not exist yet. A trie therefore has a latency profile set by the number of levels, and no amount of cleverness inside a node removes that. What a node layout can do is keep the per-level work to a single cache line and avoid allocating a separate object for every prefix.

Dense arrays, and when they are correct

The dense layout stores an array of σ child pointers and indexes it with the character value. Lookup is one load. Insert is one store. There is no search, no comparison, and no branch beyond the bounds check that a language runtime may insert.

This layout wins when σ is small or when the alphabet is small relative to the branching that actually occurs. DNA needs four symbols, so a node is four pointers — 32 bytes on a 64-bit machine, half a cache line. A dense node over a four-symbol alphabet wastes at most 75 percent of its slots and still beats any sparse structure on lookup, because the alternative requires a loop.

The rule of thumb: a dense node is defensible while σ × sizeof(pointer) stays within one or two cache lines, that is, while σ is at most 8 or 16. Above that the arithmetic in the previous section takes over. Compilers that implement tries over byte alphabets almost always use something sparser, which is why the textbook picture of a 26-way node rarely appears in working code.

Sparse children: lists, sorted arrays, hash maps

The simplest sparse node is a linked list of (label, child) pairs. Lookup scans until the label matches, so the cost is the node’s degree — small in practice, and the scan touches contiguous memory if the pairs are stored in one allocation. Keeping the label in the low bits of the child pointer, which a node pointer leaves unused because nodes are aligned, makes an entry two words; a separate label field in a padded struct makes it sixteen bytes. Insertion at the head is constant time and never moves anything, which makes this the cheapest mutable layout to implement. The cost is that the list order is insertion order, so sibling iteration is not lexicographic, and any operation needing ordered traversal must sort first.

A sorted array of labels with a parallel array of children gives ordered iteration for free and reduces lookup to a binary search: about log₂ d comparisons for degree d. For d = 4 that is two comparisons, no better than a linear scan, and binary search on four elements has unpredictable branches. Insertion shifts up to d entries. This layout is what an implementation reaches for when keys must be visited in order and degrees are moderate.

A hash map per node is the layout to avoid. A small open-addressed map needs a control array, a key array, and a value array, and its minimum footprint is several cache lines regardless of how many entries it holds. When the node itself would otherwise be 24 bytes, the map is the entire cost. Hash maps per node make sense only when degrees are genuinely large and the alphabet is large — a trie over Unicode code points, where a single node can have hundreds of children.

Bitmap plus rank: dense information, sparse storage

A middle path stores presence information densely and children sparsely. A 256-bit bitmap marks which labels have children; a packed array holds the child pointers in increasing label order. To find the child for character c, test the bit, then count the set bits below it to get the array index. Both steps are constant time with a popcount instruction, which the mainstream 64-bit architectures have had for over a decade, and which compilers provide as a builtin on the others.

#include <stdint.h>

struct node;

typedef struct {
    uint64_t bits[4];          /* one bit per label, 0..255 */
    struct node *child[];      /* packed, in increasing label order */
} sparse_node;

/* Returns the packed index for label c, or -1 when absent. */
static inline int child_index(const sparse_node *n, unsigned char c)
{
    if (!(n->bits[c >> 6] & (1ULL << (c & 63))))
        return -1;
    unsigned below = 0;
    for (int w = 0; w < (c >> 6); w++)
        below += __builtin_popcountll(n->bits[w]);
    below += __builtin_popcountll(n->bits[c >> 6] & ((1ULL << (c & 63)) - 1));
    return (int)below;
}

The bitmap is 32 bytes; each present child adds one pointer. A node with two children occupies 32 + 16 = 48 bytes and fits in a single cache line, and the lookup is two loads plus a popcount with no data-dependent branch other than the presence test. The catch is insertion: adding a child in the middle of the label order shifts the packed array, which is O(d) memmove, and adding a child at either end is free. For tries built once and queried many times this is irrelevant; for tries under heavy insertion the shifting shows up.

A narrower variant exists for alphabets below 64 symbols: a single 64-bit word holds the bitmap, and the index is a mask-and-popcount with no loop. The same trick appears in the adaptive radix tree’s 48-child node, discussed in adaptive radix tree node layouts, where a 256-byte indirection table replaces the popcount.

Flat arrays and the double-array trie

Everything above allocates a node object per prefix. The double-array trie removes the objects entirely. Two integer arrays, base and check, hold every node of the trie. A transition from state s on character c goes to state base[s] + c, and that transition is valid exactly when check[base[s] + c] == s. Both arrays are 32-bit integers, so a state costs eight bytes and a lookup is two loads and one comparison, with no pointer chasing at all — the whole structure can be one contiguous allocation, which makes it a candidate for memory mapping from a file.

Construction is where the cost moves. Choosing base[s] means finding a region where every child of s lands on a free slot whose check field is unset, and different children’s regions must not overlap. A greedy first-fit strategy over the free slots works and is what the original formulation describes; the search for a suitable base can be expensive for nodes with many children, and the resulting array can be noticeably larger than the number of states because of gaps. Once built, though, the structure is static in the ordinary case: inserting a key can require relocating a whole family of states, which is why double-array tries are used for read-only dictionaries and why libraries built on them separate a build step from a lookup step.

Choosing under mutation

The representations form a rough ordering along two axes: how much per-node space is spent to make lookup branch-free, and how much work an insertion does.

Representation	Space per node	Lookup	Insert
Dense 256-way array	2048 bytes	one indexed load	O(1)
Sorted array	8d bytes (one label byte per child, in a padded slot)	O(log d)	O(d) shift
Linked list	16d bytes (next pointer plus child pointer per entry; label stored in low bits of the pointer)	O(d)	O(1) at head
Bitmap + packed array	32 + 8d bytes	two loads, popcount	O(d) shift
Double array	8 bytes per state	two loads, one compare	rebuild or relocation

The mutable choices all degrade gracefully as degree grows, and the static choices do not. A workload that inserts a million keys into a bitmap node layout pays the shifting cost at every internal node it passes; a workload that only reads never notices. Conversely, a double-array trie has the smallest constant per state and the worst insertion story of the set.

One more axis deserves mention because it is invisible in the table: allocation count. A pointer-based node is a separate heap object, so a trie of ten million nodes performs ten million allocations and scatters them across the address space. A flat array performs one. Traversal order in a trie is not random — sibling subtrees are visited together — so an allocator that hands out adjacent blocks for adjacent nodes preserves locality by accident. The double-array layout preserves it by construction. That difference shows up as a change in cache miss rate per level rather than in any asymptotic measure, and for large key sets it usually dominates the constant factors inside the node.

Which representation to use also depends on how key boundaries are recorded, since a terminal marker consumes either a child slot, a bit, or a pointer depending on the layout. That interaction is the subject of marking key boundaries in a trie.