Messages in this thread | | | Date | Thu, 14 Nov 2002 17:53:04 -0800 | From | William Lee Irwin III <> | Subject | Re: [BK PATCH 1/2] Remove NGROUPS hardlimit (resend w/o qsort) |
| |
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 - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |