Re: radix tree implementation for quota ?

[David Laight <david%l8s.co.uk@localhost>]

On Sun, Nov 28, 2010 at 06:27:07PM +0100, Manuel Bouyer wrote:
> > Wouldn't a hash table work?
> 
> I think it's too dependant on uid distribution, or even how much uid you
> have. a tree scales and adapts better.

I agree, hash tables often degenerate into a linear search.
This means that it is still linear, just 'n' times faster that a
simple linear search.

It might be worth using a simple hash to cache recent lookups into
the tree.

OTOH it is worth remembering that there is already a 'per uid' structure
(IIRC currently hashed % MAXUSERS) used for counting processes per user.
Would seem relevant to hang the per-mount data of this structure.
(and maybe use a better lookup than the current hash - it is one of the
few uses of MXUSERS).

On disk, I'm not sure.
Once you've read a disk block, you might as well do a linear search!
This probably only happens at user login time.

More problematical is some kind of log so that you don't need to scan
the entire fs after a system crash...

        David

-- 
David Laight: david%l8s.co.uk@localhost