Programming with Judy

The Judy Advantage
Compared with Other Search and Retrieval Methods
Chapter 2 19
Skip Lists O(log n)
• Simplify the tree-balancing
problem by using a
probabilistic method instead of
a strictly enforced balancing
method.
• Their modest improvement in
performance (over binary
trees) is primarily due to the
quaternary, rather than
binary, nature of the data
structure.
Digital Trees
(Trie)
O (log
m
n) Fast access
• Memory inefficient.
• Requires access times
proportional to the number of
significant digits of the index
value. The access time for
storing an index that has a
large number of significant
digits can be lengthy.
Judy Less than
O(log
256
n)
• Fast access times.
• Grows dynamically on
demand.
• Adjusts in size to the amount
of stored data.
• Minimal number of memory
accesses.
• Depth of tree does not increase
significantly with the
population of the tree.
• Very fast lookup times for
large sparse arrays.
• Fast insertion, both average
and worst case.
• Requires no tree rebalancing.
• External interface is similar to
that of a sorted array.
• Count available.
Table 2-1
Search and
Retrieval
method (data
structure)
O number
for lookup
Advantages Disadvantages