Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/doc/int/10minutes.htm view on Meta::CPAN
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML EXPERIMENTAL 970324//EN">
<HTML>
<HEAD>
<META NAME="GENERATOR" CONTENT="Adobe FrameMaker 5.5/HTML Export Filter">
<LINK REL="STYLESHEET" HREF="10minutes.css">
<TITLE> A 10-MINUTE DESCRIPTION OF HOW JUDY ARRAYS WORK AND WHY THEY ARE SO FAST</TITLE></HEAD>
<BODY BGCOLOR="#ffffff">
<DIV>
<H1 CLASS="Title">
<A NAME="pgfId=997347">
</A>
A 10-MINUTE DESCRIPTION OF HOW JUDY ARRAYS WORK AND WHY THEY ARE SO FAST</H1>
<P CLASS="Body">
<A NAME="pgfId=997353">
</A>
By Doug Baskins, doug@sourcejudy.com</P>
<P CLASS="Body">
<A NAME="pgfId=997395">
</A>
October 16, 2001, Revised July 2002</P>
<P CLASS="Body">
<A NAME="pgfId=997492">
</A>
As the inventor of the Judy algorithm I've been asked repeatedly, "What makes Judy so fast?" The answer is not simple, but finally I can share all of the details. (In June 2002, Judy was opened sourced with a LGPL license and hosted at
<A HREF="http://sourceforge.net/projects/judy">http://sourceforge.net/projects/judy</A>
Let's see if I can give you a good understanding in 10 minutes. (The Judy data structures are very well described in another paper, the
<A HREF="http://www.sourcejudy.com/application/shop_interm.pdf">Judy Shop Manual</A>
, but it took me about three hours to read!)</P>
<P CLASS="Body">
<A NAME="pgfId=997354">
</A>
A Judy tree is generally faster than and uses less memory than contemporary forms of trees such as binary (AVL) trees, b-trees, and skip-lists. When used in the "Judy Scalable Hashing" configuration, Judy is generally faster then a hashing...
<A HREF="http://www.sourcejudy.com/application/">http://www.sourcejudy.com/application/</A>
Judy_hashing.</P>
<P CLASS="Body">
<A NAME="pgfId=997488">
</A>
<EM CLASS="bold">
Expanse</EM>
, <EM CLASS="bold">
population</EM>
, and <EM CLASS="bold">
density</EM>
are not commonly used terms in tree search literature, so let's define them here:</P>
<UL>
<LI CLASS="Bulleted">
<A NAME="pgfId=997357">
</A>
<EM CLASS="bold">
Expanse</EM>
is a range of possible keys, such as: 256..511</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997358">
</A>
<EM CLASS="bold">
Population</EM>
is the count of keys contained in an expanse, such as, 260, 300, 499, 500 = 4.</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997359">
</A>
<EM CLASS="bold">
( run in 0.664 second using v1.01-cache-2.11-cpan-e1769b4cff6 )