How a B-Tree Index Works

The previous lesson said that a database stores an index as a B-tree, and then moved on. That one structure decides how fast a lookup is, why a range scan is cheap, and why some inserts cost far more than others. It is worth understanding properly.

A B-tree is a sorted tree where every node holds many keys instead of one, and every leaf sits at the same depth. Databases chose it because it is designed around disks, not around memory.

1. Why Not a Sorted Array or a Binary Tree

Two simpler structures almost work, and seeing why they fail explains the whole design.