In computer science, a Judy array is an early-2000s Hewlett-Packard hand-optimized implementation of a 256-ary radix tree that uses many situational node types to reduce latency from CPU cache-line fills. As a compressed radix tree, a Judy array can store potentially sparse integer- or string-indexed data with comparatively low memory usage and low read latency, without relying on hashing or tree balancing, and without sacrificing in-order traversal. Per-operation latency scales as
O
(
log
n
)
{\displaystyle O(\log n)}
—as expected of a tree—and the leading constant factor is small enough that Judy arrays are suitable even to the peta-element range. When applicable, they can be faster than implementations of AVL trees, B-trees, hash tables, or skip lists from the same time period.