Programming with Judy

The Judy Advantage
Judy Data Structures
Chapter 2 15
2The Judy Advantage
The Judy advantage is a measurable performance benefit that can be
demonstrated by benchmarking Judy against hash tables, skip lists, tree
structures, stacks, and queues. The chapter describes how Judy uses the
digital tree data structure in a new and unique way to provide enhanced
performance. This chapter also contains real-time performance
measurements that show Judy compared with a hash algorithm.
Judy Data Structures
Digital tree (trie)
data structures
A digital tree or trie (pronounced try) is a multi-way or M-way tree whose
nodes are vectors of M elements. Each element in a node is either a
pointer to another node or to a leaf value. The tree is populated (and
searched) using each digit of a key as an index into the nodes as they are
traversed. A digit is determined by M. If M is 16, each digit is 4 bits. If M
is 256 (as in Judy), each digit is 8 bits.
For example, assume we are storing a set of zip codes in 10-way digital
tree. The zip codes are 87303, 92515, 92523, and 96503. Each level of the
tree decodes one base-10 digit until a unique suffix remains. Zip code
87303 is stored at the top level of the tree hierarchy because the leading
digit 8 is unique. Its position in the root node is node[8], as shown in
Figure 2-1.
Since more than one zip code starts with 9, root node[9] points to a
second level node. The second level node[6] contains a unique suffix 6503
(the leading 9 is decoded in the root level). The second level node[2]
points to the third level.
The third level node[5] points to the last level with the remaining
suffixes. Therefore, zip code 92515 is represented in the array by
level0[9]->level1[2]->level2[5] and level 3 contains the unique suffix 15.
Zip code 92523 is represented in the array by
level0[9]->level1[2]->level2[5] and level 3 contains the unique suffix 23.
Unlike an analog tree (B-tree, binary tree, etc.) no comparisons are