From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,5cbfcb03a9d3d935 X-Google-Attributes: gid103376,public From: matthew_heaney@acm.org (Matthew Heaney) Subject: Re: Help B* and B+ Trees Date: 1998/05/14 Message-ID: #1/1 X-Deja-AN: 353243013 Content-Transfer-Encoding: 8bit References: <6je5il$ecf$1@news.iinet.net.au> Content-Type: text/plain; charset=ISO-8859-1 Organization: Network Intensive Mime-Version: 1.0 Newsgroups: comp.lang.ada Date: 1998-05-14T00:00:00+00:00 List-Id: In article <6je5il$ecf$1@news.iinet.net.au>, "whizzbang" 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?