B-tree
/bee-tree/ · noun · Development · Origin: 1972
Definitions
A self-balancing tree data structure that maintains sorted data and allows searches, insertions, and deletions in logarithmic time. B-trees and their variant B+ trees are the dominant data structure behind database indexes, file system metadata, and storage engines. Their wide, shallow structure minimizes disk I/O by keeping the tree height low.
In plain English: A tree-shaped data structure that databases use to find records quickly — like the index in the back of a book that tells you which page to turn to.
Example: The query went from 3 seconds to 2 milliseconds after we added a B-tree index on the customer_email column.
Origin Story
The data structure that makes databases fast -- but what does the B stand for?
Rudolf Bayer and Edward McCreight invented the B-tree at Boeing Scientific Research Labs in 1970. They needed a data structure that could efficiently search, insert, and delete records stored on slow disk drives where minimizing disk reads was critical.
The **B** in B-tree is famously undefined. Bayer and McCreight never stated what it stands for. Popular guesses include "balanced," "broad," "bushy," "Bayer," and "Boeing." McCreight has said: "The more you think about what the B in B-trees means, the better you understand B-trees."
B-trees and their variant B+ trees are the backbone of virtually every database and filesystem. When you query a database with millions of rows and get results in milliseconds, B-trees are almost certainly responsible. PostgreSQL, MySQL, SQLite, and NTFS all rely on them.
Coined by: Rudolf Bayer, Edward McCreight
Context: Boeing Scientific Research Labs, 1970
Fun fact: McCreight's deliberate ambiguity about the B has spawned decades of debate. In a 2013 talk, he confirmed that they intentionally left it undefined. It remains one of computer science's most enduring naming mysteries.