Re: [RFC] B+Tree library

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

On Fri, 31 October 2008 11:35:14 +0100, Johannes Berg wrote:
> 
> [looks like this hitting LWN means everyone suddenly found it...]

It did?

> > 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?).
> 
> Would there be an easy way to use 48-bit keys? Or variable length keys?

Variable as in one implementation for several trees with different
sizes, yes.  Variable as in one tree with differently sized keys, no.

With the existing code, 48bit keys would need to be expressed as an
array of longs, thereby growing to 64bit.  Alternatively one could
replace the longset/longcmp/longcpy with memset/memcmp/memcpy.

> > 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 could imagine using it instead of the hash-table for stations and APs
> in the wireless code, stations are identified by the MAC address (48
> bit) and APs (BSSs) are identified by their BSSID+SSID (or mesh ID), so
> variable length. Currently we use a hash table with 256 slots which is
> quite large for the typical case of mostly less than a hundred entries.

MAC address wouldn't be a problem.  For BSSID+SSID one could just keep
the hashing and use the btree as an 'implementation detail' of the
'hashtable'.  Beware that I don't allow two identical keys.  The
implications of that make my toenails curl up.

> > 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.
> 
> I think the wireless case would probably want to have real shrinking
> because it's well possible that you're moving, with your laptop, from an
> area with a large number of APs to say your home out in the countryside
> that only has your single AP.

Indeed.

Jörn

-- 
Joern's library part 7:
http://www.usenix.org/publications/library/proceedings/neworl/full_papers/mckusick.a