What an Index Actually Is
Last timeWhere the Time Actually Goes
An index is a second copy of a few columns, kept in order, with a pointer back to each row. Everything it can and cannot do follows from that one sentence.
The word index is borrowed from books, and the borrowing is exact. The index at
the back of a book is a second, shorter document, listing terms in alphabetical
order, each followed by a page number. It does not contain the book. It contains
enough to find the book's parts quickly, and it is kept in an order the book
itself is not in.
A database index is the same object. It holds the values of one or a few
columns, sorted, each paired with a pointer to the row it came from. That
sentence contains the whole subject, and everything else in this lesson is a
consequence of it.
Why the depth stays small
The index is not a sorted list, because inserting into the middle of a sorted
list is ruinous. It is a tree. The bottom level holds the sorted entries. Above
it sits a level holding one entry per bottom page, saying what range that page
covers. Above that, the same again, until a single page covers everything.
The fan-out at each level is large, because each page holds hundreds of small
entries. That makes the tree very wide and very shallow.
- the number of levels, which is the number of page reads to reach the bottom
- the number of rows indexed
- the fan-out, or how many entries fit on one page, typically two hundred to five hundred
- grows by one for every multiplication of the table size by the base, which is why n can grow enormously for little effect
| step | level | entries this page covers | pages read so far | microseconds so far | what happened |
|---|---|---|---|---|---|
| 1 | 1 | 40000000 | 1 | 1 | The top page. Always in memory, so this read is effectively free. |
| 2 | 2 | 200000 | 2 | 2 | One comparison narrowed forty million candidates to two hundred thousand. |
| 3 | 3 | 1000 | 3 | 3 | Again. The search is now within a thousand rows. |
| 4 | 4 | 1 | 4 | 110 | The bottom level, and then the row itself, which was not in memory and cost a hundred microseconds on its own. |
The second fetch, and how to avoid it
An index entry knows where a row is. It does not know what is in it. If a query
needs any column not held in the index, the database must go to the table and
fetch the row, and those fetches happen in whatever order the index happened to
produce, which is to say scattered.
For one row this does not matter. For fifty thousand matching rows it is the
whole cost of the query, and it is why an index on a column that matches a
quarter of the table is often not used at all.
The remedy is to put everything the query needs into the index itself. Then the
answer can be assembled from the index without touching the table once, and the
scattered fetches simply do not occur. This is usually worth more than any other
single change available, and it is the reason indexes sometimes carry columns
nobody would ever search on.
The lesson stops here
3 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents