lkml.org 
[lkml]   [2008]   [Oct]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC] B+Tree library
On Sun, Oct 26, 2008 at 01:46:44PM +0100, Jörn Engel wrote:
> The idea of using btrees in the kernel is not exactly new. They have a
> number of advantages over rbtrees and hashtables, but also a number of
> drawbacks. More importantly, logfs already makes use of them and -
> since I don't want any incompatible code to get merged and suffer the
> trouble it creates - I would like to discuss my implementation and where
> it makes sense and where it doesn't.
>
> General advantages of btrees are memory density and efficient use of
> cachelines. Hashtables are either too small and degrade into linked
> list performance, or they are too large and waste memory. With changing
> workloads, both may be true on the same system. Rbtrees have a bad
> fanout of less than 2 (they are not actually balanced binary trees),
> hence reading a fairly large number of cachelines to each lookup.
>
> Main disadvantage of btrees is that they are complicated, come in a
> gazillion subtly different variant that differ mainly in the balance
> between read efficiency and write efficiency. Comparing btrees against
> anything is a bit like comparing apples and random fruits.
>
> This implementation is extremely simple. It splits nodes when they
> overflow. It does not move elements to neighboring nodes. It does not
> try fancy 2:3 splits. It does not even merge nodes when they shrink,
> making degenerate cases possible. And it requires callers to do
> tree-global locking. In effect, it will be hard to find anything less
> sophisticated.
>
> The one aspect where my implementation is actually nice is in allowing
> variable key length. Btree keys are interpreted as an array of unsigned
> long. So by passing the correct geometry to the core functions, it is
> possible to handle 32bit, 64bit or 128bit btrees, which logfs uses. If
> so desired, any other weird data format can be used as well (Zach, are
> you reading this?).
>
> So would something like this be merged once some users are identified?
> Would it be useful for anything but logfs? Or am I plain nuts?

I think a btree library would be useful - there are places where
people are using rb-trees instead of btree simply because it's
easier to use the rbtree than it is to implement a btree library.
I can think of several places I could use such a library for
in-memory extent representation....

That being said, I haven't had a chance to look at that code yet....

Cheers,

Dave.
--
Dave Chinner
david@fromorbit.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2008-10-28 02:29    [W:0.114 / U:0.056 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site