Re: Red/black trees
:
: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@backplane.com>
討論串 (同標題文章)
完整討論串 (本文為第 7 之 11 篇)：