view release on metacpan or  search on metacpan

src/judy-1.0.5/doc/int/10minutes.htm  view on Meta::CPAN

A skip-list is roughly equivalent to a degree-4 (4-ary) tree, resulting in more cache-line fills.</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997545">
 </A>
An &quot;expanse&quot;-based digital tree (of which Judy is a variation) never needs balancing as it grows.</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997370">
 </A>
A portion (8 bits) of the key is used to subdivide an expanse into sub-trees. Only the remainder of the key need exist in the sub-trees, if at all, resulting in key compression.</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=997371">
 </A>
The Achilles heel of a simple digital tree is very poor memory utilization, especially when the N in N-ary (the degree or fanout of each branch) increases. The Judy tree design was able to solve this problem. In fact a Judy tree is more memory-effici...
<P CLASS="Body">
<A NAME="pgfId=997372">
 </A>
From a speed point of view Judy is chiefly a 256-ary digital tree or trie (per D. Knuth Volume 3 definitions). A degree of 256-ary is a somewhat &quot;magic&quot; N-ary for a variety of reasons -- mostly because a byte (the least addressable memory u...
<P CLASS="Body">
<A NAME="pgfId=997373">
 </A>
It is interesting to note that an early version of Judy used branch widening (sometimes called a level-compressed trie). Branch widening opportunities occur primarily in the upper level(s) of the tree. Since a tree is a hierarchy, the upper branches ...
<P CLASS="Body">
<A NAME="pgfId=997374">
 </A>
The presence of a CPU cache in modern machines has changed many of the ways to write a performance algorithm. To take advantage of a cache, it is important to leverage as much as possible. In a Judy tree, the presence of a cache results in 1..3 (or m...
<P CLASS="Body">
<A NAME="pgfId=997375">
 </A>
 As a digression, note that a hash method loses the advantages of a cache as the size of the hash table approaches or exceeds the size of the cache. With very large hash tables, the cache is no help at all. Also, hash methods often use a linked list ...
<A HREF="http://www.sourcejudy.com/application/">http://www.sourcejudy.com/application/</A>
 Judy_hashing.</P>
<P CLASS="Body">
<A NAME="pgfId=997376">
 </A>
 With an expanse of 2^32 (or 256^4), a maximum of 4 cache-line fills would be required for a worst-case highly populated 256-ary digital tree access. In an expanse of 2^64 (or 256^8), 8 cache-line fills would be the worst case. In practice, Judy does...
<P CLASS="Body">
<A NAME="pgfId=997377">
 </A>
 Judy adapts efficiently to a wide range of populations and data set densities. Since the Judy data structure is a tree of trees, each sub-tree is a static expanse that is optimized to match the "character" or density of the keys it contains.  To sup...
<P CLASS="Body">
<A NAME="pgfId=997378">
 </A>
From a memory consumption (size) point of view, a Judy tree shares (does not duplicate) common digits of a key in a tree. This form of key compression is a natural outcome from using a digital tree. This would be very awkward to do in trees balanced ...
<P CLASS="Body">
<A NAME="pgfId=997552">
 </A>
 Now let me try to describe the top of a small Judy (JudyL) tree and the bottom of a highly populated Judy1 tree. A Judy tree with a population of zero is simply a NULL pointer. A JudyL tree with a population of one key is a root pointer to a 2-word ...
A JudyL tree with a population of 2 keys, is 4-word object with 2 values and 2 sorted keys. A tree with a population of 3 keys, is an 8-word object with a count word + 3 values and 3 sorted keys.</P>
<P CLASS="Body">
<A NAME="pgfId=997381">
 </A>
This continues until the population grows to 32 keys. At this point an actual tree structure is formed with a &quot;compressed&quot; 256-ary node (branch) that decodes the first byte of each key. The value 32 was chosen because this is where a tree s...
<P CLASS="Body">
<A NAME="pgfId=997382">
 </A>
There are three kinds of branches. Two are 1-cache-line fill objects to traverse, and one is a 2-cache-line fill object to traverse. In every path down the tree and at all populations, a maximum of one of the 2-cache-line fill branches is used. This ...
<P CLASS="Body">
<A NAME="pgfId=997383">
 </A>
On the other extreme, a highly populated Judy1 tree where the key has been decoded down to 1 byte, and the density of a 256-wide sub-expanse of keys grows to greater than 0.094 (25 keys / 256 expanse), a bitmap of 32 bytes (256 bits) is formed from a...
<P CLASS="Body">
<A NAME="pgfId=997579">
 </A>
Notice that to insert or delete a key is almost as simple as setting or clearing a bit. Also notice, the memory consumption is almost the same for both 32- and 64-bit Judy trees. Given the same set of keys, both 32- and 64-bit Judy trees have remarka...
<P CLASS="Body">
<A NAME="pgfId=997580">
 </A>
In this short writeup it wasn't possible to describe all the data structure details such as: Root, JPM, narrow and rich pointers, linear, bitmap and uncompressed branches, value areas, immediate indexes, terminal nodes (leafs), least compressed form,...
<P CLASS="Body">
<A NAME="pgfId=997386">
 </A>
 Well I cannot describe Judy in 10 minutes -- what possessed me? I hope you understand some of what I have said and question me on the rest -- particularly those doubts. I will try to elaborate on parts where I get questions. 
 <BR><BR>
 Doug Baskins
 <BR>
doug@sourcejudy.com</P>
</DIV>
</BODY>
</HTML>