Subj : Re: Balanced trees vs. B-trees To : comp.programming From : Duck Dodgers Date : Fri Sep 09 2005 03:29 pm Ben Pfaff wrote: > "Duck Dodgers" 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?) Sure. :-) > 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. > 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". 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. I appreciate your work on trees by the way, it's been very informative. .