Here is a table with 27 rows, stored in the order they were inserted. Real tables have millions, but 27 fit on screen. We want the row where id is 59.
For years my answer was "because it's a tree". That is true and explains nothing. This is the version I can actually draw.
Scroll to advance. From step 5 you can pick any key and watch the search.
Here is a table with 27 rows, stored in the order they were inserted. Real tables have millions, but 27 fit on screen. We want the row where id is 59.
The database has no idea where 59 is, so it reads every row and checks each one. That's a sequential scan. The cost grows with the table: twice the rows, twice the work.
Sorted data allows binary search: look in the middle, throw away half, repeat. Five probes instead of 27. But keeping the whole table sorted means moving rows around on every insert, which nobody can afford.
So the table stays as it is, and the index keeps the sorting somewhere else. A B-tree holds the keys in pages. Each page points to the pages below it. The leaves at the bottom point back to rows in the table.
Start at the root. 59 is between 39 and 75, so go to the middle child. 59 is between 51 and 63, so take the middle pointer. The leaf has it. Three page reads, then one jump to the row.
Move the slider above. Every key takes three reads.
My pages hold three keys. A real 8 KB page holds a few hundred. With 500 pointers per page, three levels reach 125 million rows, and a fourth reaches 62 billion. The tree gets wider much faster than it gets taller.
This was the part I was missing. Being a tree matters less than being a very flat tree.
Insert 57. It belongs in the leaf with 51, 55 and 59, which is full. The page splits in two, and its parent gets one more pointer. Only one leaf and one parent change. Everything else stays put.
The leaves are in order and linked to each other. For id BETWEEN 59 AND 75, find 59 once and walk right. The same holds for ORDER BY and prefix matches. A hash index can't do any of this.
Each index is another tree that every insert, update and delete has to keep in order. On one write-heavy table we had eleven of them. Dropping the four that no query used made inserts about 40% faster.