Messages in this thread | | | Subject | Re: [RFC] B+Tree library | From | Johannes Berg <> | Date | Fri, 31 Oct 2008 11:35:14 +0100 |
| |
[looks like this hitting LWN means everyone suddenly found it...]
> 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?
> 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.
> 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.
johannes [unhandled content-type:application/pgp-signature] | |