Editing B-tree (section)

==History==
While working at [[Boeing|Boeing Research Labs]], [[Rudolf Bayer]] and [[Edward M. McCreight]] invented B-trees to efficiently manage index pages for large random-access files. The basic assumption was that indices would be so voluminous that only small chunks of the tree could fit in main memory. Bayer and McCreight's paper ''Organization and maintenance of large ordered indices''<ref name="bayer-mccreight-1970"/> was first circulated in July 1970 and later published in ''[[Acta Informatica]]''.{{sfn|Bayer|McCreight|1972}}

Bayer and McCreight never explained what, if anything, the ''B'' stands for; ''Boeing'', ''balanced'', ''between'', ''broad'', ''bushy'', and ''Bayer'' have been suggested.{{sfn|Comer|1979|p=123 footnote 1}}<ref name=herrenalb/><ref>{{cite web |url=http://scpd.stanford.edu/knuth/index.jsp |title=Stanford Center for Professional Development |website=scpd.stanford.edu |access-date=2011-01-16 |archive-url=https://web.archive.org/web/20140604193847/http://scpd.stanford.edu/knuth/index.jsp |archive-date=2014-06-04 |url-status=dead}}</ref> McCreight, when asked "I want to know what B in B-Tree stands for," answered<ref name=herrenalb>{{cite web |url=https://vimeo.com/73481096 |title=4- Edward M McCreight |first=Peter G. |last=Weiner |date=30 August 2013 |via=Vimeo}}</ref>:<blockquote>''Everybody does!''

''So you just have no idea what a lunchtime conversation can turn into. So there we were, Rudy and I, at lunch. We had to give the thing a name.... We were working for Boeing at the time, but we couldn't use the name without talking to the lawyers. So there's a B.'' 

''It has to do with '''B'''alance. There's another B.'' 

''Rudy was the senior author. Rudy (Bayer) was several years older than I am, and had ... many more publications than I did. So there's another B.''

''And so at the lunch table, we never did resolve whether there was one of those that made more sense than the rest.'' 

''What Rudy likes to say is, the more you think about what the B in B-Tree means, the better you understand B-Trees!''</blockquote>