Judy array
In computer science and software engineering, a Judy array is a data structure implementing a type of associative array with high performance and low memory usage. Unlike most other key-value stores, Judy arrays use no hashing, leverage compression on their keys (which may be integers or strings) and can efficiently represent sparse data, that is, they may have large ranges of unassigned indices without greatly increasing memory usage or processing time. They are designed to remain efficient even on structures with sizes in the peta-element range, with performance scaling on the order of O(log256n).[1]
Roughly speaking, Judy arrays are highly optimized 256-ary radix trees.[2] Judy arrays use over 20 different compression techniques on trie nodes to reduce memory usage.
Judy trees are usually faster than AVL trees, B-trees, hash tables and skip lists because they are highly optimized to maximize usage of the CPU cache. In addition, they require no tree balancing and no hashing algorithm is used.[3]
The Judy array was invented by Douglas Baskins and named after his sister.[4]
Benefits
Memory allocation
Judy arrays are dynamic and can grow or shrink as elements are added to, or removed from, the array. The memory used by Judy arrays is nearly proportional to the number of elements in the Judy array.
Speed
Judy arrays are designed to keep the number of processor cache-line fills as low as possible, and the algorithm is internally complex in an attempt to satisfy this goal as often as possible. Due to these cache optimizations, Judy arrays are fast, especially for very large datasets. On data sets that are sequential or nearly sequential, Judy arrays can even outperform hash tables.[5] Lastly, because a Judy array is a tree, it is possible to do an ordered sequential traversal of keys, which is not possible in hash tables.
Drawbacks
Judy arrays are extremely complicated. The smallest implementations are thousands of lines of code.[4] In addition, Judy arrays are optimized for machines with 64 byte cache lines, making them essentially unportable without a significant rewrite.[5]