Re: Help B* and B+ Trees

[matthew_heaney@acm.org (Matthew Heaney)]

In article <6je5il$ecf$1@news.iinet.net.au>, "whizzbang" <none@present.com>
wrote:
(start of quote)
Can anyone please help me on information regarding B-Plus & B-Star Trees. I
am not after code, but I am after documentation on how they work. I f anyone
has any interesting information I will be more than greatfull.
(end of quote)

The best book I've found is

File Structures, 2nd ed
Michael J. Folk, Bill Zoellick
Addison-Wesley, 1992
ISBN 0-201-55713-4
QA76.9.F5F65

This is the best book I've read on all aspects of files and disks, and it
served as the basis for the B-trees I wrote in Ada95.

As a starting point, I also used the B-tree code in 

Algorithms + Data Structures = Programs
Niklaus Wirth
Prentice-Hall, 1976

Although I haven't read it, you can try

File Structures with Ada
Nancy E. Miller and Charles G. Petersen
Benjamin/Cummings, 1990

There's an appendix in Chris Date's database book that discusses B-trees
and indexed sequential files; he cites Knuth.  There's also a chapter in
Algorithms, by Cormen, Leiserson, and Rivest.

Of course, you may want to read the original papers by Bayer and McCreight,
Bayer, and the survey article by Comer.

By the way, even though Bayer didn't explicitly say what the B was for, it
seems it stands for "Bayer."  He cited the literature on "AVL" trees in the
original paper, so he was probably continuing in tradition of naming a tree
using the initial from one's last name.  Perhaps the confusion about the
meaning of the "B" came about because the trees weren't named BM-Trees,
since McCreight shared authorship in the paper most frequently cited.  Who
knows?