Programming with Judy

64
computer's main memory. This is
analogous to using a buffer cache
to minimize disk I/O, but is
implemented in hardware. Cache
lines are size-aligned and typically
16 words in size in modern
processors.
cache-line fill Filling a cache line
by accessing main memory as the
result of a cache miss for one or
more bytes not currently in any
cache line. A cache-line fill takes
~30 times longer than a cache hit.
cardinal number A basic or
primary value. Examples of
cardinal numbers are 1, 7, 9, and
123. Contrast with ordinal
number.
count In the Judy technology, the
number of indexes between any
two indexes, inclusive of the two
indexes.
D
data structure An organization
of information, usually in memory,
for better algorithm efficiency,
such as queue, stack, linked list,
heap, dictionary, and tree. It may
include redundant information,
such as length of the list or
number of nodes in a subtree.
(NIST) See also abstract data
type.
density A population divided by
its expanse.
digital tree A tree in which the
key is decoded one digit or byte at
a time.
dynamic array An array whose
size may change over time. Items
are not only added or removed, but
memory used changes, too. (NIST)
E
expanse The range of possible
indexes that can be stored under
one pointer (root or lower) in a tree
structure. For example, a root
pointer to a 32-bit Judy array has
an expanse of 0... 2
32
.
H
hash function A function which
maps keys to integers, hopefully to
get a more even distribution on a
smaller set of values. (NIST)
hash table A dictionary in which
keys are mapped to array positions
by a hash function. Having more
than one key map to the same
position is called a collision. There
are many ways to resolve
collisions, but they may be divided
into open addressing, in which all
elements are kept within the table,
and chaining, in which external
data structures are used. (NIST)
hybrid data structures Using
different abstract data types
(ADTs) at different levels in a tree
structure. This means switching to
a different ADT while traversing