//
When you create an index in a database, the DBMS must choose a data structure to store that index. While standard Binary Search Trees (BSTs) are great for data sitting in RAM, they are disastrously slow for data stored on a hard disk.
Because disk reads happen in massive chunks (blocks/pages of 4KB to 8KB), we need a tree structure that is short, wide, and perfectly optimized for block-based storage. The industry standard solution is the B+ Tree.
In a Binary Search Tree, every node has at most 2 children. If you have 1 billion records, a perfectly balanced BST will have a height of about $\log_2(1,000,000,000) \approx 30$.
If the tree is stored on a hard disk, traversing from the root to a leaf requires visiting 30 different nodes. Because these nodes are scattered randomly across the disk platter, this requires 30 separate mechanical disk seeks. This is unacceptably slow.
The B-Tree (Balanced Tree) was invented to solve this exact problem. Instead of a node holding 1 value and having 2 children, a B-Tree node is designed to perfectly fit inside a single 4KB disk block.
A single node might hold 100 values and have 101 children!
The B+ Tree is an improvement over the standard B-Tree and is the default indexing structure used by MySQL, PostgreSQL, Oracle, and SQL Server.
SELECT * FROM Users WHERE Age BETWEEN 20 AND 30, the DBMS traverses down the tree once to find Age 20, and then simply walks horizontally across the linked list at the bottom until it hits Age 30. A standard B-Tree would require a costly full tree traversal for every single number.Self-Balancing Guarantee: B+ Trees are fully self-balancing. No matter how many millions of rows you insert or delete, the distance from the root to every single leaf node is always exactly the same. Every query is guaranteed to perform consistently.