Re: Balanced trees vs. B-trees

"Duck Dodgers" <mordock32@xxxxxxxxxxx> writes:

> Ben Pfaff wrote:
>> "Duck Dodgers" <mordock32@xxxxxxxxxxx> writes:
>> Mainly, I'd suggest that B-trees are more complicated than
>> red-black or AVL trees and don't offer any speed advantage that
>> I am aware of.
>
> I'm not so sure about being more complicated. Compared to a decent
> non-recursive AVL or red-black tree, a non-disk oriented B-tree seems
> less complicated.

To me, that seems like a surprising statement. However, I have
not actually implemented a memory-only B-tree, so I may not have
a good basis for comparison.

I would be interested in seeing, say, a B-tree and an AVL tree
implemented in a similar manner, to be able to do the
comparison. I am not aware of a library that includes both. Is
anyone else?

> Been there, read that (as well as everything else you've written on
> trees). :-) I like to think I have a strong understanding of binary
> trees and their balanced variants, but what I'm really looking for is a
> good comparison of B-trees and balanced trees. Especially after that
> terribly vague sentence due to your editor. ;-) I'm sure if I don't
> find one, and probably even if I do, I'll make my own.

If you do so, would you mind passing it along? I have never
seriously considered the possibility that a B-tree would be
simpler, so I would consider looking it over a good learning
experience.
--
"I didn't say it was your fault.
I said I was going to blame it on you."
.

Relevant Pages

  • RE: Generic B-tree implementation
    ... Red-black trees in particular have ... That means that the kernel might ... I liked your B-tree implementation, ... handy C algorithm implementations. ...
    (Linux-Kernel)
  • Re: Balanced trees vs. B-trees
    ... which is are more elegant than that of Red-Black trees. ... AVL trees: Niklaus Wirth, Algorithms and Data Structures, ... performance than AVL tress and slightly greater average node depth. ...
    (comp.programming)
  • Re: Conversion between RB tree Binary search tree and AVL tree
    ... > tree AVL tree and a Binary search tree? ... Both AVL and Red-black trees are binary ... AVL trees in 1999 because the height of a node is not memorized in ...
    (comp.theory)
  • Re: searching through a set of values
    ... Other things to consider are B-trees, hash tables, binary trees, ... AVL trees, red-black trees. ...
    (comp.programming)
  • Re: searching through a set of values
    ... Other things to consider are B-trees, hash tables, binary trees, ... AVL trees, red-black trees. ...
    (comp.lang.c)