Re: [PATCH] add b+tree library

[Andrew Morton <akpm@linux-foundation.org>]

On Sat, 10 Jan 2009 23:01:35 +0100 J__rn Engel <joern@logfs.org> wrote:

> One key difference is that rbtrees maintain the tree within objects and
> btrees maintain the tree externally.  So btrees have to allocate memory
> on insertion, where rbtrees have the necessary memory as part of the
> object.

This is a major disadvantage of the btrees.

See all the hoops we ended up jumping through with things like
radix_tree_preload() and idr_pre_get().

The IDR code there wasn't very well designed and still has holes.  The
radix-tree code afaik is solid, but look at all the stuff it does!

>  With mempools the memory allocation should be reasonably safe,
> so maybe this is a bit of a red herring now.

No, mempools won't help, particularly if items are being added from
atomic contexts.

This is a major major shortcoming which greatly limits the usefulness
of btrees and which greatly reduces the chances of anyone migrating any
rbtree users over to btrees.