On Sun, Nov 28, 2010 at 05:40:15PM +0000, Sad Clouds wrote: > On Sun, 28 Nov 2010 18:27:07 +0100 > Manuel Bouyer <[email protected]> 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 <[email protected]> NetBSD: 26 ans d'experience feront toujours la difference --
