Re: radix tree implementation for quota ?

[Manuel Bouyer <bouyer%antioche.eu.org@localhost>]

On Sun, Nov 28, 2010 at 05:40:15PM +0000, Sad Clouds wrote:
> On Sun, 28 Nov 2010 18:27:07 +0100
> Manuel Bouyer <bouyer%antioche.eu.org@localhost> 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'm not sure I follow, if you size the hash table correctly and pick a good 
> hash function, it will give you very good results.
> 
> You say that current implementation uses an simple array, indexed by uid. 
> This would be ideal for a hash table. How would a tree scale better?

the current implementation is really not ideal.
A radix tree scales better because it autiomatically adapts when the
range of index, or distribution of index, changes.
using a hash table or a tree, you end up with a linked list of quota
descritors (the difference is how they are linked, but that's not
a big difference) so the complexity is the same.

-- 
Manuel Bouyer <bouyer%antioche.eu.org@localhost>
     NetBSD: 26 ans d'experience feront toujours la difference
--