Re: [fuse-devel] Experience b-tree?

[Anatol P. <ana...@gm...>]

Hi

On Sun, May 5, 2013 at 11:02 AM, Stef Bon <st...@gm...> wrote:

> Hi,
>
> I'm looking for a way to program the contents of a directory.
> Now I'm using a big hashtable, but using a btree would be much more
> flexible.
>
> I know there are different pages on the internet about it, but I need
> some extra hints. Search, insert, delete and balance should be
> supported. Anyone some experience?
>

It seems nowdays developers biased to red-black trees. Linux kernel,
FreeBSD kernel use them for "map" implementation.
They are quite simple and more important they have guaranteed worst time
O(ln N).

GPL code from linux
https://github.com/torvalds/linux/blob/master/include/linux/rbtree.h  (and
rbtree.c)
BSD version from FreeBSD http://fxr.watson.org/fxr/source/sys/tree.h#L295