Re: [PATCH] add b+tree library

[Theodore Tso <tytso@mit.edu>]

On Sat, Jan 10, 2009 at 09:23:16PM +0100, Jörn Engel wrote:
> 
> Key difference is the number of cachelines you need to find a particular
> entry.  rbtrees have a fanout of sqrt(3), so for a million elements (to
> pick a random example) you need about 25 cachelines with rbtrees and
> about 5-16 with btrees.  Closer to 5 if keys and pointers are small and
> cachelines are large, closer to 16 if keys and pointers are large and
> cachelines are small.

Three questions....  is the number of cachelines in use going to make a
measurable difference for your use case in the filesystem?  If the
operation is going to involve disk access, trying to optimize for to
improve cacheline utilization may not be the higher priority thing to
worry about.

If you have a million elements, and assuming each element is but 4
bytes (which seems unlikely; very likely you'd be indexing at least
8-12 bytes of data, right?) we're talking about 4 megabytes of
non-swappable kernel memory.  Is that likely to be happen in your use
case?

Finally, are b+tree so much better than rbtrees that it would be
worthwhile to just *replace* rbtrees with b+trees?  Or is the problem
the overhead issue if the number of entries in an rbtree is relatively
small?

Regards,

						- Ted