Three Reads, and Two of Them Were Already in Memory
Last timeSorted Means Searchable
Put 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.
The previous lesson ended with the design: leave the rows alone and build a
separate structure holding the keys in order. This lesson builds it, and the
whole of it follows from one observation about page sizes.
A page of pointers
The sorted file halved the search on every read because a page told you one
thing: is the target above or below this page. That is a waste of a page. An
eight kilobyte page can hold far more than one signpost.
Fill a page with key-and-pointer pairs instead. Each pair says: everything from
this key onwards lives under this page. Now one read does not eliminate half
the remaining file, it eliminates all but a few hundredth of it.
- branching factor, the number of children one page points at
- usable bytes in a page, about 8000 after the header
- bytes in a key
- bytes in a pointer to a child page, usually 4 or 8
Depth from branching
With a branching factor of three hundred, count what each level can hold. The
bottom level holds the keys themselves, three hundred to a page. One level up,
each page points at three hundred bottom pages, so it covers ninety thousand
keys. One level above that covers twenty-seven million.
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