I m reading CLRS and studying the B-Tree now.
CLRS claims that B-Tree naming is not clear yet: [Bayer, McCreight, 1972] doesn t offer the reason why B-Tree is named "B-Tree".
I haven t investigated this issue any further... but does anyone know the reason? :)
This seems to be the closest I can find to an answer:
The origin of "B-tree" has never been explained by the authors. As we shall see, "balanced," "broad," or "bushy" might apply. Others suggest that the "B" stands for Boeing. Because of his contributions, however, it seems appropriate to think of B-trees as "Bayer"-trees.
I stumbled across this Quora post, and it turns out that Edward M McCreight actually answered this question 6 years ago, at CPM 2013. In this video from the conference, starting at the 16 minute mark, someone asks him what the "B" stands for.
The tl;dr is that the B doesn t really stand for anything, and that team that worked on the B-Tree just came up with the name B-Tree over lunch.
Based on his answer, it sounds like they either came up the name "B-Tree" and then tried to figure out what the "B" stood for afterwards, or they came up with a few possible names(Boeing, Balance or Bayer (the senior author)), but they never decided on which one to go with. Since each of the name ideas started with "B", they then went with the name "B-Tree".
The quora answer provides a written transcript of his answer, for those not wishing to watch the video (or should the video ever be removed):
You just have no idea what a lunchtime conversation can turn into. So there we were, [indistinct] and I, at lunch , we had to give the thing a name. And we were, so, B, we were thinking… B is, you know… We were working for Boeing at the time, we couldn t use the name without talking to the lawyers. So, there is a B. It has to do with balance, another B. Bayer was the senior author, who did have several years older than I am and had many more publications than I did. So there is 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 really lies to say is: the more you think about what the B in B-trees means, the better you understand B-trees.
Landauer, W. I. The Balanced Tree and Its Utilization in Information Retrieval. IEEE Trans. on Electronic Computers, Vol. EC-12, No. 6, December 1963.
Just a hunch, since this prior paper is reference #3 in Bayer and McCreight s paper. I ve always been told the B stood for balanced , did not know it was an Internet Mystery. ;)
"Bayer" would be my best guess. I doubt we ll know the answer.
In Wikipedia you can find the following:
Bayer and McCreight never explained what, if anything, the B stands for: Boeing, balanced, broad, bushy, and Bayer have been suggested. McCreight has said that "the more you think about what the B in B-trees means, the better you understand B-trees."
If I have an algorithm which is comprised of (let s say) three sub-algorithms, all with different O() characteristics, e.g.: algorithm A: O(n) algorithm B: O(log(n)) algorithm C: O(n log(n)) How do ...
I m using Electro in Lua for some 3D simulations, and I m running in to something of a mathematical/algorithmic/physics snag. I m trying to figure out how I would find the "spin" of a sphere of a ...
There s a (relatively) new sort on the block called Timsort. It s been used as Python s list.sort, and is now going to be the new Array.sort in Java 7. There s some documentation and a tiny Wikipedia ...
As a learning experience I recently tried implementing Quicksort with 3 way partitioning in C#. Apart from needing to add an extra range check on the left/right variables before the recursive call, ...
Given a 10 digit Telephone Number, we have to print all possible strings created from that. The mapping of the numbers is the one as exactly on a phone s keypad. i.e. for 1,0-> No Letter for 2->...
I have a directed graph and my problem is to enumerate all the minimal (cycles that cannot be constructed as the union of other cycles) directed cycles of this graph. This is different from what the ...
Given an array of integers arr = [5, 6, 1]. When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child. Now if our input is ...
I was trying to speed up a certain routine in an application, and my profiler, AQTime, identified one method in particular as a bottleneck. The method has been with us for years, and is part of a "...
