B-Tree Indexes

The problem, from first principles

02-binary-search finds a key in a sorted array in about twenty comparisons for a million keys. On a database that is not good enough, because the keys live on disk and what costs time is not a comparison but a page read: fetching one block of storage. A binary search over a disk-sized array touches about twenty different blocks, each a separate read. A B-tree fixes this by making each node as wide as a whole page, hundreds of keys, so that the tree is only three or four levels deep and a lookup reads three or four pages. This question builds a static B-tree-style index over sorted keys, level by level, and counts the pages a search and a range scan touch.

From theory to code

Implement build_index(keys, fanout), which builds the levels of the index from sorted keys, then search(levels, key), which finds a key and reports how many pages it read, then range_scan(levels, low, high), which returns every key in a range and counts the pages read, then index_height(num_keys, fanout), the number of levels without building the index. The signatures and docstrings are already in the editor.

Constraints

• keys is a sorted list of distinct integers and fanout >= 2 is the maximum number of entries per page.
• build_index(keys, fanout) returns levels, a list of levels from the leaf level to the root level. A level is a list of pages and a page is a list. The leaf level cuts keys into consecutive pages of up to fanout keys. Each higher level has one page for each group of up to fanout consecutive pages of the level below, holding the smallest key of each child page, in order. The last level has exactly one page, the root. For an empty keys return [[[]]].
• search(levels, key) starts at the root page and at each non-leaf level moves to the child whose page is the last one whose first key is <= key (the first child if key is smaller than every entry). It returns (found, pages_read) where found says whether key is in the leaf page reached, and pages_read is the number of pages visited, one per level.
• range_scan(levels, low, high) finds the leaf page that would contain low as search does, then reads leaf pages left to right until it passes high. It returns (keys_in_range, pages_read) where keys_in_range is the sorted list of keys with low <= key <= high, and pages_read counts the descent from the root plus every leaf page read after the first. A range with no keys still reads the descent.
• index_height(num_keys, fanout) returns the number of levels build_index would produce, computed by repeated division (not by building the pages), as an int. For num_keys <= fanout (including 0) the height is 1.

Hints