Re: [BK PATCH 1/2] Remove NGROUPS hardlimit (resend w/o qsort)

[William Lee Irwin III <wli@holomorphy.com>]

On Thu, Nov 14, 2002 at 08:45:39PM -0500, Pete Zaitcev wrote:
> This sounds intriguing.
> Bill, if I may borrow from your data structure expertise,
> what would you do if you wanted gid_t's indexed by two criteria?
> Obviously, we want them them indexed by value (to look them up
> for access checking), but NFS also needs them sorted by usage,
> to fit the last 3 into the RPC parameters. This looks like
> something requiring two overlaying trees who share leafs,
> and every leaf being a single gid_t, with nightmarish overhead.
> Before Tim came to the scene, the hope was that lookups would
> do exhaustive search of arrays, sorted by LRU, while RPC
> picked N leading elements of said sorted array. Tim busts
> this scheme to pieces, because he sorts arrays by value
> (if I read it right).

B+ trees separate metadata from data entirely, so two distinct
B+ tree "indices" attached will work just fine for this overlaying
of trees that share leaves.


Bill