[WIP] lazy revlog index parsing

Isaac Jurado diptongo at gmail.com
Wed Mar 21 16:40:15 CDT 2012


On Wed, Mar 21, 2012 at 7:34 PM, Matt Mackall <mpm at selenic.com> wrote:
>
> For the record, Wikipedia's idea of what a radix tree is is completely
> different than mine. Mine is more like this:
>
> https://lwn.net/Articles/175432/
>
> In other words, take a binary tree and make it 16-way. Then given a
> hash prefix like "abcde", we do at most 5 steps before we find a tree
> leaf node, discover it's not present, or discover it's ambiguous.

Also for the record.  If I understood correctly, those are called tries:

    http://en.wikipedia.org/wiki/Trie

Radix trees (or PATRICIA tries) are an space optimization of tries.  The
structure mentioned in the LWN article is just a trie with a 64 symbol
alphabet.

Cheers.

-- 
Isaac Jurado

"The noblest pleasure is the joy of understanding"
Leonardo da Vinci


More information about the Mercurial-devel mailing list