Derive the structures a database uses to find a row without reading every row, well enough to say which index a given query will use, why one you added did nothing, and what each one costs on every write

How an Index Actually Works

An index is not a hint, it is a data structure with a shape. This course builds the main ones by hand, from a sorted file to a balanced tree to a hash, and derives exactly which queries each one can answer.

8 lessons, written and corrected before you arrived. Reading them here needs no account. The first reads the whole way through; the others open and then stop, because a page nobody owns cannot tell who is reading it. Starting the course gives you your own copy, where every idea has problems standing under it and you can ask about any sentence.

Start reading

01The Database Never Reads a RowA scan costs what it costs because of pages, not rows. Work out the number of pages and the answer falls out, along with the case where scanning is correct.
02Eighteen Reads Instead of a Quarter of a Millionopening onlySorting a file turns finding a row from a quarter of a million reads into eighteen. Then somebody inserts a row, and the whole of the rest of the course follows.
03Three Reads, and Two of Them Were Already in Memoryopening onlyPut the keys in sorted pages and build pages of signposts above them. The depth is tiny because a page holds hundreds of keys, and the top of it never leaves memory.
04The Page Is Full, So Cut It in Halfopening onlyMost inserts touch one page. Occasionally a page is full, it splits, and the split can travel all the way to the top. That rare event is what indexes cost on a write.
05A Phone Book Sorted by Surname Then First Nameopening onlyAn index on two columns sorts by the first and breaks ties with the second. Every rule about which queries it serves follows from that one sentence.
06The Index Already Knew the Answeropening onlyA lookup ends by fetching the row, and that fetch is most of the cost. If every column the query mentions is in the index, the fetch never happens.
07One Is Faster and Cannot Do Ranges, the Other Is for Writingopening onlyTwo structures exist alongside the tree. A hash is unbeatable on exact lookups and useless on ranges; a write-ordered log is for data arriving faster than a tree can take it.
08The Index Is Right There and the Database Will Not Use Itopening onlyFive reasons cover almost every case, and in two of them the database is right to refuse. Here is how to tell which one you have, in the order worth checking.