Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
B-tree
In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for nodes with more than two children.
By allowing more children under one node than a regular self-balancing binary search tree, the B-tree reduces the height of the tree, hence putting the data in fewer separate blocks. This is especially important for trees stored in secondary storage (e.g. disk drives), as these systems have relatively high latency and work with relatively large blocks of data, hence the B-tree's use in databases and file systems. This remains a major benefit when the tree is stored in memory, as modern computer systems heavily rely on CPU caches: compared to reading from the cache, reading from memory in the event of a cache miss also takes a long time.
While working at 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 the main memory. Bayer and McCreight's paper Organization and maintenance of large ordered indices was first circulated in July 1970 and later published in Acta Informatica.
Bayer and McCreight never explained what, if anything, the B stands for; Boeing, balanced, between, broad, bushy, and Bayer have been suggested. When asked "I want to know what B in B-Tree stands for," McCreight answered:
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 Balance. 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.
Hub AI
B-tree AI simulator
(@B-tree_simulator)
B-tree
In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for nodes with more than two children.
By allowing more children under one node than a regular self-balancing binary search tree, the B-tree reduces the height of the tree, hence putting the data in fewer separate blocks. This is especially important for trees stored in secondary storage (e.g. disk drives), as these systems have relatively high latency and work with relatively large blocks of data, hence the B-tree's use in databases and file systems. This remains a major benefit when the tree is stored in memory, as modern computer systems heavily rely on CPU caches: compared to reading from the cache, reading from memory in the event of a cache miss also takes a long time.
While working at 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 the main memory. Bayer and McCreight's paper Organization and maintenance of large ordered indices was first circulated in July 1970 and later published in Acta Informatica.
Bayer and McCreight never explained what, if anything, the B stands for; Boeing, balanced, between, broad, bushy, and Bayer have been suggested. When asked "I want to know what B in B-Tree stands for," McCreight answered:
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 Balance. 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.