dillon at apollo.backplane.com
Sun Apr 17 23:29:51 PDT 2005
: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.
<dillon at xxxxxxxxxxxxx>
More information about the Kernel