Messages in this thread | | | Date | Tue, 18 Jul 2006 11:22:05 -0400 | From | "Vishal Patil" <> | Subject | Re: Generic B-tree implementation |
| |
B-trees are good for parellel updates as well. Anyway it would be great to have inputs from other folks about how B-trees could help inside the kernel (if at all)
- Vishal
On 7/18/06, Gary Funck <gary@intrepid.com> wrote: > > Vishal Patil wrote: > > I said B-Tree and not binary tree, please read the explaination about > > B-tree at http://en.wikipedia.org/wiki/B-tree. Also I am aware of AVL > > trees. > > > > I never claimed that my implementation is better or anything like > > that. I posted the code so that someone in need of the data structure > > might use it. Also I would be willing them to help with their project. > > My reason for pointing out the other data strucutres is to note that there > might be search tree representations that are more appropriate for > implementation inside the kernel, and to perhaps encourage you to have > a look at implementing them as well. Red-black trees in particular have > the property that they're reasonably well-balanced, and that the balancing > algorithm makes use of local information. That means that the kernel might > be able to limit the level of locking required to update the tree. > > I liked your B-tree implementation, and have saved a copy. Too bad there > isn't the C/C++ equivalent of CPAN (comp.unix.sources is so passe`). Your > B-tree implementation would make a nice addition to an archive of > handy C algorithm implementations. >
-- Motivation will almost always beat mere talent. - 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/
| |