27

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? :)

Adam Stelmaszczyk
  • 19,665
  • 4
  • 70
  • 110
  • interesting perhaps, but not a real question... – Mitch Wheat Feb 15 '10 at 03:03
  • binary tree - as in two choice is what I remember from college. – Shane C. Mason Feb 15 '10 at 03:06
  • 13
    It cannot mean "binary tree". A binary tree has a branching factor of 2. B-trees can have branching factors in the thousands. – finnw Feb 15 '10 at 03:10
  • I always thought it was balanced, binary, or bisection. Makes a lot more sense that Bayer or Boeing. Of course, I like to imagine that there are scholars out there coming up with this stuff that aren't the narcissistic 'stamp my name on everything' types. – Evan Plaice Jul 05 '12 at 22:42

5 Answers5

23

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.

-- http://en.wikipedia.org/wiki/B-Tree#Etymology

Martin Potthast
  • 257
  • 2
  • 8
pioto
  • 2,472
  • 23
  • 37
  • +1. This seems as authoritative as is possible to get, short of contacting the authors and asking them (again) to explain. – ShreevatsaR Feb 15 '10 at 03:14
5

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.

Wipqozn
  • 1,282
  • 2
  • 17
  • 30
  • geniuses are so weird sometimes. to me, "this could've been as simple as why not just say B stands for balanced and we can't call it a balanced tree because it's actually a self-balancing tree so we'll stick with B." then we wouldn't have people forever asking this type of question – dtc Jan 21 '21 at 17:54
4

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. ;)

Steven A. Lowe
  • 60,273
  • 18
  • 132
  • 202
  • You’re trying to explain the name with a paper that was published 9 years before the B-tree was introduced by Bayer and McCreight? – poke Mar 28 '14 at 00:58
  • @poke: Landauer's paper is reference number 3 in Bayer & McCreight's paper. Call it a hunch ;) – Steven A. Lowe Mar 28 '14 at 15:33
2

"Bayer" would be my best guess. I doubt we'll know the answer.

moogs
  • 8,122
  • 8
  • 44
  • 60
1

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."

Commander
  • 311
  • 3
  • 16