Indexes: B-Trees and the Cost of a Lookup
An index is a second structure that makes some lookups cheap and every write more expensive. Most are B-trees, whose wide nodes suit a disk that reads a page at a time, and whose ordering also serves ranges and sorts.
What a learner can do afterwards
- Say which of several queries an index on a given column would help
- Explain why B-tree nodes are wide rather than binary
- Name the costs an index adds to inserts, updates and storage
1 · Read
Like the binary search tree that kept smaller values left and larger values right, an index is a second structure beside the table that keeps one column in order. It lists the values with pointers to the rows. A query that filters or sorts on that column can use the list instead of reading the whole table.
Most indexes are B-trees, which generalize the binary search tree you just met: each node holds about one disk page of keys, so a single read brings many keys. Wide nodes keep the tree shallow, and the stored order also speeds up ranges and sorting.
A shop table has an index on email. A lookup of one email address uses the index. A filter on age ignores it, because no index covers age.
Every insert, update, and delete must update each index as well, and each index needs storage. Index the columns your frequent queries use, and leave the rest alone.
An index buys cheap lookups on one column and charges you on every write.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.