tech-kern archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: radix tree implementation for quota ?

On 28 Nov 2010, at 13:47 , David Holland wrote:
> (Also, why a radix tree? Radix trees are generally not very efficient.
> If you're going to, though, you might want to reuse the direct,
> indirect, double indirect, etc. method FFS uses for block mapping.)

I think generalizations are generally likely to be wrong, recursively
speaking.  Radix trees can be quite efficient if your application for
them needs the data to be sorted in the way a radix tree inherently
does it (this is why they can make very good route lookup data structures,
though the one in the BSD kernel might not be a stellar example of the
art), and they can be even better if you want a structure which can be
modified while lookups are concurrently in progress so you can avoid
expensive locking strategies and primitives.

I doubt that the first property is an advantage in this case but the
second might be.

Dennis Ferguson

Home | Main Index | Thread Index | Old Index