Re: Red/black trees

[Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>]

:
:On Sunday 17 April 2005 03:16, Matthew Dillon wrote:
:>     The previous data structure was a doubly linked list with a bunch of
:>     hacks to try to make insertions go faster.  The red-black tree should
:>     be just as fast, and not require any hacks.  Plus we can simplify
:>     the clustering and fsyncing code, and make other optimizations.
:
:
:What about ternary trees or Patricia trees ?

    There are thousands of data structures for arranging things, guys, 
    I'm not going to analyze each and every one.

    Generally speaking data structures are designed for particular desireable
    trade-offs depending on the situation.  This is why you generally find
    B+Tree's used when locality of reference is important (database indexes),
    radix trees used when variable-length prefixes need to be arranged,
    and more binary-like trees used for in-memory storage of sortable
    bounded data sets where code compactness can be almost as important as
    the O()rder of the search.

					-Matt
					Matthew Dillon 
					<dillon@xxxxxxxxxxxxx>