Programming with Judy

The Judy Advantage
Judy Data Structures
Chapter 216
necessary to search a digital tree until you reach the value. The index is
divided into a series of array indexes until a unique index suffix is
obtained.
Figure 2-1 A ten-way digital tree
Judy: a digital tree
hybrid
Pure digital trees, like the one described above, typically exhibit very fast
insertion and retrieval times; however, a digital tree often achieves fast
performance at the cost of large memory use. A computation of 256
4
uses
over four billion indexes, while a computation of 256
3
uses over 16
million indexes or at least 67 MB of storage (4 bytes/index).
Judy is a hybrid 256-way digital tree. Like a pure digital tree, each level
in a Judy tree decodes one or more (8 bit) digits. Unlike a pure digital
tree, each node is not necessarily a 256-way vector of elements.
Judy achieves scalability and excellent memory characteristics by
choosing data structures for each node appropriate for the population
below the node. For example, if you need a small associative array with 6
indexes, you would probably create a linear list to hold them. Judy does
the same. If you need 600 million indexes, you would do something
different. The same goes for Judy. As a Judy tree is populated, each node
gets a data structure appropriate to the population under it.
To be this dynamic, Judy must know the population under any node. To
0 12 3 4 567 8 9
87303
ptr
0 12 3 4 567 8 9
ptr
6503
0 12 3 4 567 8 9
ptr
0 12 3 4 567 8 9
15
23
zip codes = 87303, 92515, 92523, 96503
pointer = ptr
Level 0
Level 1
Level 2
Level 3