Subj : Re: Balanced trees vs. B-trees
To   : comp.programming
From : Ben Pfaff
Date : Fri Sep 09 2005 01:42 pm

"Duck Dodgers" <mordock32@hotmail.com> writes:

> I like to think that I know my way around trees, but I was flipping
> through C Unleashed and noticed Ben Pfaff say this in reference to 2-3
> trees, splay trees, and multiway trees: "These methods all have
> disadvantages that make them less suitable than balanced trees in
> general situations". I know about the locality of reference for splay
> trees, but what about multiway trees? For the sake of argument, let's
> compare B-trees of order 4 with red-black and AVL trees. What are the
> disadvantages to the B-tree that make it less suitable than a balanced
> tree?

(Boy, that sentence was terribly vague.  Can I blame it on my
editor?)

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.

For what it's worth, I now have empirical results comparing
unbalanced BSTs, red-black trees, AVL trees, and splay trees.
You can read them at
        http://benpfaff.org/papers
Look at "Performance Analysis of BSTs in System Software".
-- 
"Let others praise ancient times; I am glad I was born in these."
--Ovid (43 BC-18 AD)

.