Re: [PATCH] add b+tree library

["Jörn Engel" <joern@logfs.org>]

On Sat, 10 January 2009 12:37:08 +0100, Johannes Berg wrote:
> On Sat, 2009-01-10 at 20:02 +0900, KOSAKI Motohiro wrote:
> 
> > > This adds a b+tree library. The API and memory layout is documented in
> > > the header file lib/btree.h. There are tree versions for 32, 64 and
> > > 128 bit keys as well as unsigned long (32/64 depending on platform).
> > 
> > Can this library remove the btree code in some btree based filesystem?
> 
> Joern is going to use it for logfs, that's the point. Not sure about
> other filesystems.

Err...

While true, this is decidedly _not_ a disk-based btree.  Logfs uses it
for in-memory data structures.  So the short answer is no.

There are several differences between this implementation and one used
for disk data.

- The value is a pointer, 32/64bit depending on architecture.  Won't be
  suited for a 64bit filesystem on a 32bit host, f.e.

- Lookups are a simple loop and don't use binary search.  With a 4KiB
  btree node and 64B cacheline, binary search will only load 7 out of 64
  cachelines - making a big difference.  This implementation uses 128B
  (or cacheline size, whichever is bigger) nodes, so binary search buy
  almost nothing, but cause branch mispredictions, bigger code, etc.

There may be more.  So if you plan to replace disk-based btree code with
this, it will certainly be some amount of work.  Not sure if it is a
good idea or if one should rather have a seperate library.

Jörn

-- 
The cost of changing business rules is much more expensive for software
than for a secretaty.
-- unknown