> Christoph Hellwig <hch@xxxxxxxxxxxxx> wrote:
> On Wed, Oct 21, 2009 at 12:12:33PM -0500, Alex Elder wrote:
> > - I accept that this uses less memory for sparsely populated
> > key space than radix trees; but it would be nice if that
> > could be characterized a bit more precisely (i.e., what
> > will the range of values that'll be represented be, just
> > how sparse is it, and at what point does this really
> > pay off?).
> > - Related to the previous one--it would be good to have
> > a little info about why the value 7 was chosen as the
> > number of keys per node. Perhaps I just don't know
> > enough of the history (or content of the upcoming
> > patches).
> Maybe Barry still remembers some of this. I've added his current
> personal address to the Cc list.
Radix tree was instantly dismissed as during my early testing, it actually used
more memory than the original flat array on a large filesystem!
I experimented with different values for the key, it didn't make a huge
difference. A short node involves less memory copying and more node splitting
and merging and tree traversals. Bigger nodes, a lot more memory copying when
inserting and deleting entries. No clear winner - can tune it for specific
workloads though (and what Dave Chinner said is correct too and started as my