Re: Generic B-tree implementation

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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 <[email protected]> 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 [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[Index of Archives]     [Kernel Newbies]     [Netfilter]     [Bugtraq]     [Photo]     [Stuff]     [Gimp]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Video 4 Linux]     [Linux for the blind]     [Linux Resources]
  Powered by Linux