Judy Array: The Cache-Conscious Adaptive Trie

The 256-Way Radix Trie Foundation

A Judy array is fundamentally a *digital trie*, sometimes called a radix tree, built over the raw bytes of a key rather than over comparisons between whole keys. For a 32-bit integer key, the trie has up to four levels, one per byte, and at each level a node can branch in up to 256 directions, since a byte holds 256 distinct values. Walking from the root to a leaf therefore takes a bounded number of steps, at most four for a 32-bit key or eight for a 64-bit key, completely independent of how many keys are actually stored in the array. This is a critical structural difference from comparison-based trees such as red-black trees or B-trees, where the path length grows with *log* of the number of keys. In a Judy array the path length is fixed by the key width, not by the population, so lookup cost does not degrade as the array grows. The naive way to implement a 256-way branch at every level is a plain array of 256 pointers per node. That is fast, a single indexed memory access per level, but it is also wildly wasteful: a node with only two or three children still reserves slots for 256, burning kilobytes of memory for a handful of real entries. Because Judy arrays are explicitly designed to handle *sparse* keyspaces, such as a set of a few thousand 64-bit identifiers scattered across an enormous range, this naive layout would defeat the entire purpose. A structure meant to be memory-frugal cannot allocate uniformly for the densest possible case at every node. This tension, wanting the *O(1)*-per-level speed of direct indexing but the memory footprint of a structure that only pays for children that exist, is exactly what motivates Judy's core design decision. Rather than pick one node format and accept its trade-off everywhere, the structure lets each node's format vary independently, chosen to match the actual number of children below it. A node near the root, which may have hundreds of descendants, can afford a large dense representation. A node deep in a sparse branch, which may have only one or two children, uses a tiny format that costs almost nothing. This per-node adaptivity, applied recursively throughout the trie, is the mechanism explored in the next section.

Adaptive Node Representations: List, Bitmap, and Full Array

The heart of a Judy array is a small family of node representations, each tuned for a different population range, with the implementation automatically converting a node from one representation to another as children are inserted or removed. Although the exact thresholds and formats vary across the Judy1, JudyL, and JudySL variants, the underlying strategy is consistent and can be understood as three broad tiers. *Linear list nodes* are used when a node has only a small number of children, typically fewer than roughly a dozen. Here the node stores a short sorted array of the actual key-byte values present, paired with a matching array of child pointers, and finding a child means a short linear or binary scan rather than a direct index. This is deliberately simple: with so few elements, a compact list beats a sparse bitmap or a 256-entry array on every axis that matters, memory, and, because the whole list fits in one or two cache lines, speed as well. *Bitmap nodes* take over once the child count grows past the list's comfortable range but is still well short of full density. Instead of storing key bytes explicitly, a bitmap node uses a 256-bit vector, 32 bytes, with one bit set for every byte value that has a child, plus a compacted array of pointers only for the children that actually exist. Locating a child becomes a matter of testing one bit and then counting the set bits before it, a *population count*, to find the pointer's index in the compacted array. This representation is far denser than a list once dozens of children are present, yet still avoids reserving space for absent children. *Full array nodes* are reserved for nodes where most or all of the 256 possible byte values actually lead to a child. Here Judy falls back to the naive direct-indexed array of 256 pointers, because at that density the bitmap's population-count overhead no longer pays for itself, and a single indexed load is simply the fastest and most memory-efficient option available. As insertions and deletions shift a node's population across these thresholds, Judy transparently morphs the node between representations, so the structure as a whole always uses whichever format is locally appropriate, never paying densely for sparsity or sparsely for density.

Why Cache-Line Awareness Is Inseparable From the Design

Choosing the right representation for a node's population is only half of Judy's engineering story; the other half is that every representation is deliberately sized and laid out with CPU cache-line behavior in mind, typically the common 64-byte cache line found on most processors of the era Judy was designed for. A trie traversal that is nominally *O(1)* per level in an asymptotic sense can still be slow in practice if each level's node access triggers a cache miss, since a miss to main memory can cost roughly a hundred times more cycles than an access that hits in L1 or L2 cache. Judy's designers treated minimizing cache misses per key lookup as a primary objective, on par with minimizing memory footprint, and shaped the list, bitmap, and array node formats so that a single node, or a small constant number of them, tends to fit within one or two cache lines. This has concrete consequences for the implementation. The bitmap representation's 256-bit vector is exactly four 64-bit words, small enough to be tested and population-counted using just a few machine instructions without spilling across many cache lines. Small list nodes are kept compact enough that the key bytes and their sibling pointers for the whole node often live in a single line, so a linear scan through a handful of entries costs one memory fetch rather than several. Judy also uses techniques such as storing narrow key fragments directly rather than full pointers where possible, and packing metadata into unused bits of aligned pointers, to squeeze more useful information into each fetched cache line. The payoff is that even though a Judy array may perform several node accesses to resolve one key, each access is engineered to be cheap, frequently a cached, sequential, or predictable memory reference, rather than an unpredictable pointer chase into cold memory. This is a sharp contrast with naive linked structures like unbalanced binary search trees, where every level typically means an unpredictable jump to a new heap allocation. It is this combination, structurally bounded trie depth plus cache-conscious node internals, that lets Judy compete with hash tables, which do only one or two memory accesses on average but scatter those accesses unpredictably across memory too, particularly once a hash table's load factor rises or it must resize.

Sorted Order, Range Queries, and Ordered Traversal

A hash table achieves its average constant-time lookup by deliberately destroying any relationship between key value and storage location, a good hash function scatters similar keys to unrelated buckets. That scattering is precisely why hash tables cannot efficiently answer questions like *find the smallest key greater than X* or *iterate all keys between A and B in order*, doing so would require sorting the entire table from scratch. A Judy array pays no such price, because it is a trie organized directly by the byte values of the key, in the exact structure that a sorted representation of the keys would require anyway. Because each internal node's children, whether stored as a list, a bitmap, or a full array, are always logically ordered by byte value, an in-order traversal of a Judy trie visits keys in strictly ascending order for free, no separate sort step and no auxiliary ordering metadata is needed. This makes operations like *first*, *last*, *next*, and *previous* natural and efficient, walking sideways and downward through the trie following the byte order already encoded in the node structure. Range queries, retrieving every key between two bounds, become a bounded trie walk that only visits nodes and leaves actually inside the requested range, rather than a full scan of the structure. This ordered-traversal capability is not a minor bonus feature bolted onto Judy after the fact; it falls directly out of using a radix trie as the base structure rather than a hash table. The practical implications are significant for many real workloads: database index structures, IP routing tables that need longest-prefix matching, and sparse bitmap or set implementations that must support ordered enumeration or nearest-neighbor style queries such as *next set bit after position N* all benefit from this property. A hash table can be augmented with an auxiliary sorted index to support such queries, but that means maintaining two structures and paying two sets of memory and update costs. Judy provides ordered access as an intrinsic, essentially free property of its adaptive trie design, one of the clearest ways in which it occupies a design point that neither hash tables nor plain balanced trees reach on their own.

Performance Trade-offs Against Hash Tables and B-Trees

Judy arrays are frequently benchmarked against three alternatives, hash tables, balanced binary search trees, and B-trees, and the comparison clarifies exactly what niche the design occupies. Against a well-tuned hash table, Judy typically achieves comparable or sometimes superior lookup throughput for large datasets, primarily because Judy's cache-conscious node layouts keep the *working set* touched per lookup small and often already resident in cache, whereas hash tables suffer unpredictable cache misses on collision chains or open-addressing probes, and must periodically pay an expensive full-table rehash as they grow. Judy's memory usage per key is also frequently lower than a hash table's, since hash tables generally must keep their load factor below some threshold, commonly under seventy or eighty percent, to preserve speed, wasting the remaining capacity, while Judy's adaptive representations size themselves to the actual population rather than reserving slack capacity. Against classic balanced binary search trees, such as red-black or AVL trees, Judy wins decisively on both speed and memory for large key counts, since a binary tree's *O(log n)* comparison-based descent involves many unpredictable pointer chases, one per comparison, and per-node overhead for balance metadata, whereas Judy's descent is bounded by key width and its nodes are compact and cache-friendly. Against B-trees, the comparison is closer, since B-trees were themselves designed with block or cache-line efficiency in mind, especially for disk-backed storage. Judy generally still edges ahead for in-memory workloads because its node representations are more finely adapted to actual density than a B-tree's fixed fan-out, and it avoids the overhead of key comparisons entirely, using direct byte indexing instead. The trade-offs are real, however. Judy's implementation complexity is substantial, with numerous node types, conversion thresholds, and careful bit-packing, making it far harder to implement and maintain correctly than a hash table or B-tree, which is one reason production-quality Judy implementations remain relatively rare compared to ubiquitous hash table libraries. Judy also performs best on integer or fixed-structure keys, where the byte-trie decomposition is natural, and requires more care to apply efficiently to arbitrary variable-length string keys.

Frequently asked questions

Try it live

Everything above runs in your browser — open Judy Array: The Cache-Conscious Adaptive Trie and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.