Programming with Judy

65
the tree as the expanse and/or
population shrinks to best
represent the population's indexes
with the fewest cache-line fills and
the least amount of memory.
I
index A key value to an ADT that
appears array-like at the
application interface. Since Judy
appears array-like, keys into Judy
ADTs are referred to as indexes.
J
Judy array An ADT that acts
much like an ordinary array, but
which appears unbounded (except
by the available RAM and word
size of the machine) and is
allocated by the first store/insert
into the array. Judy indexes can be
inserted, retrieved, deleted, and
searched in sorted order.
Judy tree The internal data
structure used to implement the
data stored in what is presented
externally as a Judy array.
L
leaf node In tree structures, a
node that has no nodes under it.
level compression Widening the
nodes of a tree (branches of a Judy
digital tree) in order to have fewer
indirections (address calculations)
and possible cache-line fills to
access data.
linear list A simple, packed
sequence of data items that are
usually the same size and in some
order (such as sorted
numerically). For example, a
linear list could be a list of valid
indexes of one word each.
N
node (1) A unit of reference in a
data structure. Also called a
vertex in graphs and trees. (2) A
collection of information which
must be kept at a single memory
location. (NIST)
O
O notation See big-O notation.
ordinal The sequence in which
something is in relation to others
of its kind. Examples of ordinal
numbers are first, third, 11th, and
123rd. Contrast with cardinal
numbers.
P
population The number of
indexes that have been assigned
or used.
S
scalability (1) The ability of a
computer application or product
(hardware or software) to continue
to function well as it (or its
context) is changed in size or
volume in order to meet a user