Programming with Judy

The Judy Advantage

Judy Data Structures

Chapter 2 17

do this, Judy keeps internal population counts at each node. These

counts are also the reason why you can call Judy1Count or JudyLCount

to find all the indexes between x and y and get an answer back much

faster than you can count a linear array of the same population.

Here is what you might find in an element of a Judy node:

Pointers Like a traditional tree, Judy provides pointers to the

next tree level.

Indexes Because it is based on a digital tree, Judy always stores

indexes in sorted order or infers them from their

position if the node is an M-way vector. The order in

which values are stored is based on numeric value.

Type Judy uses type information to track the kind of

structure being pointed to in the next level.

Count The index population stored below this node element.

Since Judy inherits the advantages of a digital tree structure, a Judy tree

with 32-bit indexes is a maximum of 4 levels deep. A Judy tree with

64-bit indexes is a maximum of 8 levels deep. When you consider that a

64-bit tree could have 1.845 x 10

indexes (if you had enough memory),

this is an efficient search and retrieval storage technique.

With in-memory data structures like the current version of Judy, the

depth of the tree is only an indication the CPU cycles necessary to access

the data. However, the time required to retrieve that data is even more

important. Many search and retrieval algorithms have problems because

memory cache-line fills frequently dominate in memory search and

retrieval times. Modern processors have become so fast that it is

advantageous to trade CPU cycles to avoid cache-line fills whenever

possible. Judy is designed with this trade-off in mind. (See Appendix B,

“Caching and Memory Management,” on page 61.)