Subj : Re: Balanced trees vs. B-trees
To   : comp.programming
From : A. Bolmarcich
Date : Sat Sep 10 2005 12:26 am

On 2005-09-09, Ben Pfaff <blp@cs.stanford.edu> wrote:
> "Duck Dodgers" <mordock32@hotmail.com> writes:
>
>> Ben Pfaff wrote:
>>> "Duck Dodgers" <mordock32@hotmail.com> 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.

Elegance may be in the eye of the beholder.  To me the rebalancing
algorithm of binary B-trees is more elegant than that of AVL trees
which is are more elegant than that of Red-Black trees.

This may be affected by the algorithm description that I have used:

  binary B-trees: R. Bayer, "Symmetric B-Trees: Data Structures and
  Maintenance Algorithms", Acta Informatica, 1(4), 290-306, (1972)

  AVL trees: Niklaus Wirth, Algorithms and Data Structures,
  Prentice-Hall, 1986

  Red-Black trees: Thomas H. Cormen, Charles E. Leiserson, and Ronald
  L. Rivest, Introduction to Algorithms, McGraw-Hill, 1990

> 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?

I have my own source for them, which I am unable to share.  And I do
mean source.  They are written as C macros that generate data and
function declarations and function implementations based on the presence
of C preprocessor variables.

For example, if a LINKTO_PARENT preprocessor variable is defined, then
each node contains a pointer to its parent node.  In this case the
function implementations use iteration rather than recursion and
functions are defined that return the node immediately before and
immediately after a node.

My general conclusions are that AVL trees have the best performance and
least average node depth.  Red-Black trees have slightly lower
performance than AVL tress and slightly greater average node depth.
trees.  Binary B-Trees have slightly lower performance than Red-Black
trees and even greater average node depth.  However, when parent
pointers are not present the performance of the insert node function
of Red-Black trees is much worse than that of AVL trees and Binary
B-Trees.
[snip]

.