Eytzinger Layout: Storing a Search Tree in Level Order

A binary search over an array is already an implicit tree: the midpoint of the range is the root, the midpoints of the two halves are its children, and the recursion bottoms out at leaves. The array’s physical order is sorted order, which is in-order traversal order of that tree. That choice is convenient for printing the elements and terrible for searching, because a descent from root to leaf jumps forward and backward through memory in a pattern with no locality at all.

The mapping from tree position to array index

Eytzinger numbering — named for the sixteenth-century genealogist who used it to number ancestors in a family tree — assigns indices in breadth-first order: root at 1, its children at 2 and 3, their children at 4 through 7. The element at index i has children at 2i and 2i + 1 and parent at ⌊i/2⌋. Storing the sorted keys in this order produces a complete binary search tree laid out contiguously, with no pointers.

The index arithmetic replaces the comparison-and-branch of the classic loop. A descent step is:

/* a holds n keys in Eytzinger order at indices 1..n, index 0 unused.
   Returns the node index of the first key >= k, or n+1 if none. */
size_t eytzinger_lower_bound(const int *a, size_t n, int key)
{
    size_t k = 1, cand = n + 1;
    while (k <= n) {
        int small = a[k] < key;   /* 0 or 1, no branch */
        cand = small ? cand : k;  /* left turn: this node is a candidate */
        k = 2 * k + small;
    }
    return cand;
}

Two quantities move through the loop. k follows the descent: a comparison that finds the node’s key smaller than the query means the answer lies in the right subtree, so k becomes 2k + 1; otherwise the answer is this node or something in its left subtree, so k becomes 2k and the node index is recorded in cand. The final cand is the deepest node at which the descent turned left, and by the in-order property that node has the smallest key not less than the query. This is the same answer as the half-open bound search, computed with the same comparison count but no data-dependent jump.

Recovering the answer from the final index bits alone is tempting and does not work once the array is padded to a power of two: the sentinel values produce a descent path that ends deeper than the real tree, and the trailing bits no longer correspond to real nodes. Tracking the candidate explicitly costs one register and one conditional move per level.

The loop body has no unpredictable branch. a[k] < key produces a 0 or 1, which is added to twice the current index. On architectures with conditional moves, compilers emit exactly that; where they do not, the addition still avoids a branch. The cost is that the traversal always runs to the deepest level, even when the key is found early — a small price compared with a mispredicted branch, which on current x86 cores costs on the order of fifteen cycles.

Why breadth-first order helps the cache

The locality argument is about which nodes a descent visits and when. In an in-order array, the root is at index n/2 and the two children are at n/4 and 3n/4 — three distinct cache lines, then four distinct lines at the next level, and so on. Every level touches a disjoint region, and the regions are spread over the whole array.

In Eytzinger order, the first level occupies indices 1–1, the second 2–3, the third 4–7, the fourth 8–15. The first four levels — the top of the tree, visited on every single search — occupy the first 15 elements, which is 60 bytes of a 32-bit key array and fits in one 64-byte cache line. The fifth level occupies indices 16–31, one more 64-byte line. The top of the tree is touched constantly and stays resident; only the deepest levels, visited once per search, incur misses.

That is the entire benefit, and it is a benefit in lines touched, not in comparisons. Both layouts perform the same ⌈log₂(n+1)⌉ comparisons. A search over a million keys visits 20 nodes, which in a sorted array are 20 distinct memory locations spread across the array; in Eytzinger order the same 20 nodes are contiguous near the root, and the top five levels — every node a shallow search touches — span 31 elements, or 124 bytes of a 32-bit key array, a couple of cache lines that stay resident across searches.

A second effect compounds it. Because the next index is known one step ahead of when it is needed — it is either 2k or 2k+1 — the address of the next node is computable before the current comparison resolves, in both branches. Software prefetch can therefore issue both candidate loads, and whichever is used is already in flight. In a pointer-based tree the next address is not known until the current node’s key is compared and the child pointer is loaded, which serialises the misses: each level costs a full memory latency. This is why Eytzinger layouts show their largest gains on large arrays and almost none on arrays that fit in L2.

Building and maintaining the layout

The transformation from sorted order to Eytzinger order is a recursive descent with an output cursor. The middle element goes at the current index; the left half recurses into 2i; the right half into 2i + 1. One pass over the sorted array, O(n) time, O(log n) stack.

static void eytzinger_fill(const int *sorted, int *out, size_t n,
                           size_t i, size_t *cursor)
{
    if (i > n) return;
    eytzinger_fill(sorted, out, n, 2 * i, cursor);       /* left subtree */
    out[i] = sorted[(*cursor)++];                        /* in-order visit */
    eytzinger_fill(sorted, out, n, 2 * i + 1, cursor);   /* right subtree */
}

This works because the recursion is an in-order traversal of the implicit tree of indices — left subtree, node, right subtree — and the in-order sequence of a search tree is exactly sorted order. The sorted keys therefore fill the tree’s in-order positions, which the 2i/2i + 1 mapping stores at breadth-first array indices; the median lands at the root because it is the in-order middle. The recursion depth is ⌈log₂ n⌉, and the array must be sized n + 1 with index 0 unused, or the mapping shifts.

The layout is a snapshot, not a dynamic structure. Insertion requires rebuilding: a new key shifts the position of every subsequent key in sorted order, and in Eytzinger order that shift propagates to a different index entirely. Deletion likewise. For an index that is rebuilt in bulk and then read many times, this is acceptable — the build is linear and the query is faster. For a mutable ordered map, it is disqualifying, and the pointer-based or B-tree structures that support insertion are the right choice.

The variants and their trade-offs

Three refinements appear in practice.

Implicit leaf-only keys. A classic optimisation stores keys only at the leaves and puts separators in internal nodes, so each search descends to a leaf rather than exiting early on a found key. It doubles the array size and complicates the branchless loop, which must distinguish internal from leaf nodes.

Blocked layouts. Instead of one array of keys, store the top k levels in one small array and each subtree’s remainder contiguously in a block. The top levels stay in L1, and the descent into a block is sequential. This is the same idea as a B-tree’s page fanout applied to an in-memory tree, and it degrades more gracefully than pure Eytzinger when the array is much larger than the last-level cache.

Interleaved keys and payloads. When the index stores offsets rather than keys alone, placing the key and its 4-byte payload adjacent doubles the bytes per node and halves the nodes per line. Storing keys in one array and payloads in a parallel array keeps the hot traversal narrow; the payload is fetched once at the end.

Layout	Nodes per line at top	Insert cost	Comparisons
Sorted array	1	O(n) memmove	⌈log₂(n+1)⌉
Eytzinger	16 (32-bit keys)	O(n) rebuild	⌈log₂(n+1)⌉
Pointer tree	1	O(log n)	⌈log₂(n+1)⌉

The comparison count is identical across all three, which is the point: on modern hardware the count is not the cost. The cost is the number of dependent memory accesses, and only the layout changes that.

Limits of the technique

Eytzinger order helps when the array is large enough that cache misses dominate and small enough that a rebuild is affordable. Below a few thousand elements everything fits in L1 and the classic loop is as fast or faster, because the branch predictor learns the pattern. Above the size where a rebuild is impractical, the structure cannot be updated in place.

There is also a correctness trap in the fully unrolled form of the loop. Compilers cannot flatten while (k <= n) into a fixed sequence of steps, because the depth depends on n; hand-unrolled versions therefore drop the bounds check and run a fixed ⌈log₂(n+1)⌉ levels. That version reads a[2k] and a[2k+1] for leaves whose children do not exist, so the array must be padded to the next power of two with a sentinel larger than every real key. The padded tree also gives every search exactly the same depth, which removes the last data-dependent iteration count. The padding costs up to a factor of two in memory — the same factor a hash table pays for its load factor — and is invisible in the query time. The bounded loop above needs no padding, at the cost of one comparison against n per level.

For keys that are compared through a comparator rather than a primitive type, the branchless form loses its advantage: the comparison is a function call, and the compiler cannot turn it into a conditional move. The layout still improves locality, but the branch remains, and the gain shrinks to the cache effect alone. That is still worth having, and it is the reason the technique appears in ordered containers that store small primitive keys and in the sorted-array indexes that back read-mostly workloads, including the block-structured lookups described in fanout arithmetic for disk indexes.