The follow list of terms was originally written in May 2000, based on Judy
III and early Judy IV, without reference to outside academic source.
There is no guarantee that our definitions agree with consensus (academic)
Abstract data type (ADT): Any data structure that can hold a
variety of specific "key" datatypes, such as integers or characters. It's
the relationship between the keys, not the type of the keys, that defines
the ADT. We also use ADT to refer to cases in which a data structure
hasvariable parts (nodes) to adapt to the data being stored.
Adjacent (Neighbor): In a data structure (ADT) such as
Judy1/JudyL, Indexes (or keys) are stored in numerically sorted order. The
numerically closest (less and/or greater) to the one specified is the
adjacent or neighbor key. In JudySL, Indexes (null terminated string keys)
are stored in lexicography (dictionary) sorted order. The likelihood of a
neighbor being stored physically close in memory is very high. During
neighbor searches, access times are usually very fast, because the path
leading to them is typically in cache memory (from the previous access).
ADT: See Abstract Data Type.
Amortization: In a tree hierarchy, especially one with a high
fan-out (256 in Judy1/L), it is possible to waste memory to obtain better
performance in the higher levels of the tree. The wasted memory is
"amortized" over the high population in the lower levels. This memory is
normally insignificant relative to the whole tree structure.
API: Application Programming Interface, a specification of
the signatures of a collection of useful methods or functions and possibly
Bitmap branch [node]: A Bitmap Branch is one of the three (3)
types of branches (nodes) used in Judy1 /L. A bitmap branch is a compressed
(memory efficient) structure of a node that has 256 virtual pointers (may or
may not be present). A bitmap of 256 bits is used to mark the expanses that
have a population and thus a pointer to lower levels of the tree. In the
design of Judy, there is only one (1) of these nodes in any path down the
tree to a leaf node and it is the node nearest the leaf. When the
population of Indexes below a bitmap branch reaches a point where the memory
used can be effectively amortized, it is converted to an "Uncompressed
Bitmap leaf [node]: When the expanse of a leaf node is 256, a
bitmap leaf is a very fast structure that does not require searching. It
needs 32 bytes (256 bits) of memory to support up to 256 Indexes. It is
used when the population of that expanse exceeds about 24 Indexes.
Branch [node]: A non-leaf node in a Judy tree other than a
JPM node. This term is used as a noun, although this is a bit weird at first
(but it is used this way in academic papers too), in order to give a more
specific name to this type of node. Note that Judy branches contain more
than just pointers (addresses); they contain JPs (Judy Pointers), which are a
type of "rich pointer" that associates information with the address.
Branch width (fanout): The number of possible (virtual) or
actual pointers in a branch (the number of subtrees) which is related to,
but not identical to, the branch's memory size in words or bytes. A branch
node divides an expanse into a collection of subexpanses, each with one
associated pointer, some of which can be null (if the subexpanse is
unpopulated). A linear orbitmap branch has an actual fanout (width) lower
than its virtual width, whereas a Judy uncompressed branch has virtual fan
out = actual fanout = 256.
By-expanse: Dividing an index set into subsets, as in a
hierarchical data structure, by partitioning the indexes according to a
prearranged series of subexpanses, also referred to in some literature as "a
priori" storage. A digital tree is a by-expanse tree. In practical terms
by-expanse storage means subdividing evenly, and with the same fanout at
each level, in fact using whole numbers of bits (2^N fanout at each branch
node). Judy divides index sets by-expanse with a very wide digit sizeof 8
bits (256 fanout). By-expanse trees are by nature unbalanced, but can also
have predictable depth for fixed-size keys.
By-population: Dividing an index set into subsets, as in a
hierarchical data structure, by partitioning the indexes according to which
indexes are present. A binary storage tree is a by-population tree. The
partitioning rules are prearranged as is true for by-expanse storage, but
tend to be more about tree balancing than about locality of modifications,
meaning the partitioning ofany newly inserted indexes depends more on the
index set already stored than about the value of the new index itself.
Cache fill: See CPU Cache Fill.
Cache line: See CPU Cache Line.
Cascade: During insertion of an index, this is when a leaf
data structure overflows and more nodes must be added to a tree (or in some
cases the leaf's indexes can be compressed into a lower-level leaf under a
narrow pointer). A decascade (coalesce) is when the opposite occurs during
an index deletion. Cascading results from changing an index set into one of
its adjacents -- in the Judy context, by inserting or deleting one index.
Compressed branch: A linear or bitmap branch.
Compressed leaf: A bitmap leaf; also used to refer to index
compression in lower-level leaves, where in the already-decoded (at higher
levels) leading digits are not present.
Counting tree: A tree where each branch node records the
number of indexes stored under it, or equivalently, as in Judy1 and JudyL,
where each pointer in the branch node has associated a count of the indexes
stored under or in the branch or leaf pointed at by the pointer. These
counts can be used to rapidly determine the number of valid indexes in any
range or expanse, that is, between any pair of indexes. They are also useful
internally when inserting, deleting, or searching for previous or next
indexes. Alternatively, each node or pointer could have associated a count
which is a total of the application's values associated with each index in
its index set. This can be useful in certain applications for determining
index value density instead of index density. Note: Wider digital branches,
even if otherwise efficient (meaning few null pointers), cause more work,
and possibly more cache fills, while gathering counts, since every pointer
in the wide branch must be visited.
Cache fill (cache line fill): Needing to go to main memory
(RAM), as the result of a cache miss, for one or more bytes not currently in
any cache line; results in filling a cacheline; takes 30-150 times longer
than a cache hit. Note that sometimes a cache fill results in a disk
(buffer) cache miss and fill (swap in), by reading from mass storage, which
is even more expensive. In this document, "cache" refers to CPU cache lines
and does not even consider diskcache.
Cache line: A block of memory local to a CPU chip that caches
the same-sized block from the 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. Often there are hidden constraints on them, such as they
can only map to certain offsets in memory.
Decascade: See Cascade.
Decoded index bits/bytes/digits: The most-significant
bits/bytes/digits of an index that were already used, while traversing the
tree, to do address calculations in higher-level branch nodes.
Density: A population divided by its expanse.
Digit: A key, or a field, or portion of a key, that is used
to address through a branch node in a digital tree. For Judy each digit is
one byte (eight bits), "very wide" as digital trees go.
Digital tree = trie: A tree data structure in which each node
divides its expanse uniformly into N same-sized subexpanses, each with its
own pointer to a next-lower node. In a pure digital tree the indexes need
not be stored in the tree. They are used (piecemeal, digit-by-digit) to
address into each node's array of pointers. Hence N is typically a power of
2, so integer numbers of bits are "decoded" from the index while traversing
down the tree. An ordinary array can be thought of as a one-level trie where
the entire index is used in a single addressing calculation. Note that N
need not be the same for every node in a trie, if there's a way to determine
the appropriate N for each node. For Judy, N = 256 (8 bits) at every level,
but compressed branches have an actual fanout that is less than their
Dynamic range: The population (size) or population-type
(distribution of keys or indexes) over which an algorithm or data structure
works well (untuned or with tuning). Judy has a wide dynamic range. Most
ADTs work well only overspecific, "tuned" or designed-in (limited) dynamic
Expanse: The range of possible indexes (keys) 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 - 1.
Fanout: See Branch Width.
Fixed-size index: A key to an array-like data structure which
is always the same size, in practice one machine word in size. Judy1 and
JudyL support fixed-size, one-word indexes only. Judy grew out of a need to
solve this problem efficiently, although in the academic literature only
variable-size index problems seem to be considered interesting. Ironically a
meta-trie consisting of JudyL arrays as very-wide branch nodes can be used
to support variable-size keys quite nicely.
Grow-in-place: Allocating memory in chunks that are often
larger than the actual bytes required, by rounding up to a lesser number of
different memory chunk sizes, means there is often somepadding present in a
given node. Thus the node can be modified in place during an insert
operation, and it can also shrink in place during a deletion without having
to be reallocated to a smaller size.
Horizontal compression: See Index Compression.
Hybrid data structures: Using different ADTs at different
levels or for different nodes in a tree data structure. This means switching
to a different ADT while traversing the tree as the expanseand/or population
shrinks, to best represent the population's indexes with the fewest cache
fills and the least amount of memory.
Hysteresis: Leaving a system (in this case a Judy data
structure) in a previous state even when it could be modified to a new
state, with the result that the present state depends on the "direction"
(such as insertion or deletion) from which it was approached. Any
application that deletes indexes is likely to perform a series of insertions
and deletions, often within a relatively small expanse ofindexes. Hence it
might be faster on average to not revise the data structure to the optimal
form for each new index set (after each operation). Especially upon deletion
followed by insertion, it can result in superior performance if decascades
are postponed. The risk with hysteresis is that random or pathological
sequences of insertions and deletions can result in a greatly suboptimal
data structure -- and it's difficult to identify them or rule them out. Judy
presently makes use of limited hysteresis (one index at most) in some cases
Immediate indexes: Similar to how a machine instruction can
contain an immediate (constant) rather than indirect (variable) value, if
the population in a Judy expanse is low enough (perhaps just one index),
depending on the data structure (memory space associated with each pointer
in a branch), the population's indexes can be stored locally in a JP rather
than in a separate leaf node under the JP, saving one indirection and
possibly some memory. This requires encoding into the JP the special case of
Index: A key to an array or to an array-like API.
Index compression = horizontal compression: At any level in a
tree data structure, all indexes in the current population (index set within
the current expanse) might have one or more most-significant bits (MSB) in
common. These common bits can be stored just once in multi-index shortcut
leaves, in a variety of possible "compression schemes", such as: q Storing
the first valid index in full and the others as relative offsets, either
from the first, or from each previous. q Storing the common bits only once,
and for each valid index, only the bits that might differ. This is the same
as relative offsets, all from the first value, which is a base value not
necessarily equal to any one of the indexes. In practice, due to machine
instruction efficiencies, common MSBs are compressed only in units of whole
bytes. For example, in a 32 bit system, there might be 0, 1, 2, or 3 common
bytes, and thus 1, 2, 3, or 4 varying bytes, in the indexes in a leaf. At a
low enough level in the tree, say where 3 bytes were already decoded, only 1
byte can vary. Furthermore, Judy does not bother with the kinds of complex
compression schemes described above because we think the extra CPU time
involved would out weigh the space savings. Judy does have the ability to
compress a collection of indexes to a lower-level leaf, which has a greater
capacity, under a narrow pointer, which skips 1 or more common leading
bytes, if all of the indexes in the expanse are in the narrower leaf's
Index set: Given a data structure capable of holding 0..N
indexes (keys, elements), any one [sub]set of those 0..N indexes is an index
set. For a given expanse, each possible population's set of indexes is one
index set. It must be possible to store and distinguish every unique index
set inthe data structure, regardless of the sequence of insert/delete
operations used to arrive at that indexset, or else the data structure is
not very useful. Of course, Judy arrays pass this test.
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.
Informational pointer: See JP.
Iteration: A procedure where a series of operations is
JP: Judy Pointer, a two-word object that populates branch
nodes, also referred to... as a "rich pointer" or "informational pointer". A
JP contains an address field, except when the JP is null (represents an
unpopulated subexpanse) or contains immediate indexes, plus other
descriptivefields such as Decode bytes, Population count, and
JPM: Judy population/memory node, at most one per tree (Judy
array), used when the array/tree population is too large to fit in a
root-level leaf and hence is large enough to amortize the memory needed for
the JPM. A root pointer points to a JPM which contains a top-level JP which
in turn points to a top-level branch node. The JPM contains additional
fields that make tree management faster and easier.
Judy array: An ADT that acts much like an ordinary array, but
which appears unbounded (exceptby the expanse of the index) and is allocated
by the first store/insert into the array. Judy arrays are hybrid digital
trees consisting of a variety of branch and leaf node ADTs. Judy indexes can
be inserted, retrieved, deleted, and searched in sorted order.
Judy pointer: See JP.
Judy population/memory node: See JPM.
Judy tree: The internal data structure used to implement the
data stored in what is presented externally as a Judy array.
Judy1: Bit array that maps a long word index to Boolean
JudyL: Word array that maps a long word index to a long word
JudySL: Word array with string index; map string index to
long word value. Built as a meta-trie using JudyL arrays as extremely wide
branch nodes. (Includes the use of JLAP_INVALID in JudyL value areas
(subsidiary root pointers) to "escape" to shortcut leaves for unique string
suffixes, a critical though subtle feature.)
Key: A data value (bitstring) used to look up related data
values in a data structure that holds a collection of keys. See also Index.
Level compression = vertical compression: In the academic
sense this means skipping levels in the tree when a branch node would
otherwise have a fanout of 1. Read about Patricia tries for an example. Judy
does this using narrow pointers.
Linear branch [node]: A Judy non-leaf branch node for a
low-fanout population. Linear branches are constrained to one cache line =
16 words, hence hold 1..7 JPs out of a virtual fanoutof 256. Populated
subexpanses are listed by-population (1 byte/digit each), along with a
corresponding list of JPs.
Linear leaf [node]: A multi-index leaf (a terminal node) that
holds a population too large to fit in an immediate index JP but small
enough to fit in 2 cache lines (for JudyL, 4 cache lines including value
areas). By convention a root-level leaf is referred to separately, and a
linear leaf is always below the root level. Note that a linear leaf is never
large enough to be fully populated, that is, tohold 256 indexes.
Locality: Designing a data structure so a single insertion or
deletion has the least wide-ranging effects on average and/or in the worst
case. Ideally, every index set's optimal data structure is very similar to
every adjacent index set's optimal data structure, implying excellent
average and worst-case locality. If this cannot be achieved, at least
instances of poor locality should be relatively rare.
LSB: Least Significant Bytes/Bits.
Memory manager: Any dynamic multi-node data structure like
Judy requires an underlying memory manager from which it can obtain chunks
of memory, and to which it can possibly free(return) them. To minimize
wasted memory and reduce the frequency and cost of pathological cases due to
memory fragmenting into small and non-reusable chunks, the data structure
should use the minimum number of different sizes of memory chunks, maximize
the frequency of reuse of freed memory chunks, and/or the memory manager
itself should be smart and efficient about merging adjacent free chunks into
larger ones for reuse. (The malloc(3C) library is an example of a
Meta-trie: A hybrid digital tree (trie) whose branch nodes
are in turn smaller tries. For example, a variable-size key trie might use
fixed-size key tries like JudyL arrays as its branch nodes, especially given
an "escape" mechanism like JLAP_INVALID to mark a JudyL value area as being
other than a root pointer to a subsidiary JudyL array, such as a shortcut or
multi-index leaf node.
MSB: Most Significant Bytes/Bits.
Multi-index leaf: If the population of an expanse in a trie
is small enough, it can be more efficient to store the population's indexes
in a multi-index leaf object rather than under additional trie nodes leading
to single-index leaves.
Narrow pointer: Suppose that high in a digital tree data
structure there's a large expanse, with apopulation large enough to not fit
in a single leaf node, but whose members are clustered closely enough to have
lots of index compressibility due to common leading bits/bytes/digits. A
narrow pointer is a way of simultaneously skipping levels and unoccupied
expanses in the tree. Associated with the narrow pointer must be the common
index bits being "decoded" via the pointer, unless the whole indexes are
stored in the leaves. Judy1 and JudyL support only fixed-size indexes (1
word each), so Decode bytes in the JPs in the branches describe the
digits skipped by narrow pointers.
Neighbor: In a sorted index set, the neighbor of any index
(element) is the previous or next valid index in the index set. One of Judy's
strengths is its ability to rapidly locate neighbors.
Opaqueness: The property of hiding the internal details of a
data structure or algorithm. Because Judy is very opaque, the application
sees it purely as an array. Users don't need to know the array is implemented
as a tree, or actually as an even more complex hybrid ADT.
Optimal data structure: Given a set of unambiguous criteria,
if they exist, by which to rank different data structures capable of holding
the same index set, there should be exactly one best data structure to
represent each possible index set. Ideally the implementation of each
adjacency operation would then convert an optimal data structure (for one
index set) into another optimal data structure (for its adjacent index set).
It's possible to have no unambiguous criteria for optimizing data structures.
For example, Judy seeks to simultaneously: q Minimize index access (get)
time, both average and worst-case. q Minimize index insert/delete time,
both average and worst-case. q Minimize memory consumed and thus maximize
efficiency. q Be as simple as possible -- but we had to give this up in the
transition from Judy III to Judy IV. We learned that a wide dynamic range
plus high-performance (although still portable) software requires a lot of
different data structures (tree nodes) to pick from, plus maximally in-line
code with minimal functions, loops, etc. The optimal data structure for any
index set depends sensitively on the tradeoffs chosen between conflicting
criteria, and might not even be "computable". (It worries me that whenever
this ambiguity or complexity exists we might overlook better data structures
or algorithms.) Ironically, space and time need not always be in conflict.
Using data compression techniques to save memory, at the cost of some CPU
time to compress/decompress, can reduce the overall size of a data structure,
hence average CPU cache fills, resulting in less overall time to access an
Outlier: An index that falls within a given expanse but not
within a narrow subexpanse of that expanse. For example, given indexes all
beginning with 0x0102... in a leaf under a narrow pointer, an index beginning
with 0x0103... would be an outlier under slot (digit) 0x01 of the top
Parent [node]: A branch that contains a pointer to some other
node (a child node).
Pathology: A pathological index set is one that brings out
the worst-case behavior in a given algorithm and/or data structure. A
pathological case is a sequence of insertions and deletions (or other
adjacency operations) that result in a pathological index set and/or a
suboptimal data structure, and/or which takes much longer to perform than
Population: The number of indexes that are stored in one
expanse, or the indexes them selves (that is, the index set), depending on
Positional lookup: Data, such as pointers in a trie node,
which are located via address calculations rather than by linear, binary, or
any other type of search. Note that a positional lookup results in at most
one cache fill -- so long as each data element itself does not cross cache
line boundaries -- no matter how large the array or node in which the
positional lookup is done.
Recursion: When a function calls itself.
Rich pointer: See JP.
Root pointer: A pointer to the top node of a tree structure.
(Tree data structures are typically drawn upside down, with the root at the
top and the leaves at the bottom.)
Root-level leaf: A simple linear list of whole indexes,
possibly (in JudyL) with associated value areas, used for low-population
Judy arrays (less than or equal to 31 indexes = 2 cache lines). The root
pointer indicates the presence and type of the root-level leaf. A generic
root-level leaf starts with a population count word. Small root-level leaves
have their populations encoded in the root pointer to save memory.
Shortcut leaf: By default, a full trie for a fixed-size index
contains a fixed number of levels. If below a certain point there is only one
index stored, that is, an expanse has a population of 1, it can be
considerably more efficient to store that index in a non-trie leaf object
directly below the last node containing 2 or more indexes in its expanse. A
shortcut leaf must contain all of the remaining undecoded bits of the index
it contains, since they are not encoded positionally in additional trie
nodes. Shortcut leaves are mainly useful for variable-size key trees such as
JudySL arrays, although multi-index leaves can be seen as a type of shortcut
Sibling branch [node]: A branch node with the same parent as
another branch; a peer.
Sorted index set: An index set whose members are uniquely
sorted according to some rule, suchas numerically or lexicographically.
Tree data structure: Most definitions of Binary and
Digital/Tries tree data structures miss the fundamental difference. A
typical Binary tree has nodes (or forks) that cut up the "population" in an
attempt to keep the depth of the tree to a minimum. This requires a
comparison test be done at every node to determine which branch (fork) to
follow. A perfectly balanced binary tree has a very predictable depth
proportional to (log(base 2) of) the population. In contrast, a
Digital/Trie tree the population is cut up by "expanse". That is a portion
of the Index/key is used (8 bits with Judy1/L) is used to determine which of
the 256 nodes in the branch to follow. The maximum depth of a Judy1/L tree
is (in 32 bit version) 32/8=4. In the past, digital trees have not been
popular because of the astronomical amount of memory it takes to implement
them. Judy solves that problem very well. Judy's data structures are
tailored to support the population below an expanse (node) at any given
time -- whether it be 256, 65536, or any possible 256^n expanse.
Trie: See Digital Tree.
Unbounded array: An array maps an index to a value. Normally
an array is defined (at compiletime) or allocated (at run time) with some
fixed size, such as abc, which in C means indexes 0..9 are valid. An
unbounded array is one where the size of the array is only limited by the
size of the index. On a 32-bit system, for Judy1 and JudyL, where the index
is a native machine word,this means 32 bits, or indexes 0..2^32-1. For
JudySL, this means any string you can fit in memory. So unbounded doesn't
mean infinite, it means not arbitrarily bounded at less than the
Uncompressed branch node: A simple array of 256 JPs,
including null JPs for unpopulated subexpanses.
Valid/invalid [index]: A valid index is one that appears in a
index set; that is, it's set or stored in a Judy array. An invalid index is
one that could appear in the index set but does not; that is, it's not
currently stored in a Judy array. There are many synonyms for each word,
such as: present/absent,set/unset, stored/free, full/empty.
Variable-size index: A key to an array-like data structure
that handles a variety of index sizes, or possibly unbounded sizes.
Bitstrings and character strings are examples of variable-size keys.JudySL
is an array-like API implemented as a meta-trie that supports character
Vertical compression: See Level Compression and Digital Tree.
Word: A unit of memory that is the same size as a pointer to
pointer to void, and/or an unsigned long, in native C; typically 32 or 64
bits today. PA-RISC and IPF hardware support both 32-bit and 64-bit programs
depending on compilation options.