Expand description
A B+tree over the buffer pool.
Leaves hold every key and value; interior pages hold separator keys and child page numbers and are wholly derivable from the leaves. That derivability is what makes Law 5 cheap: recovery sweeps for intact leaves and repacks.
SACRIFICE (Law 4): a split leaves two leaves about half full, so the file is roughly 1.3-1.5x the size of a packed layout. Bought: an insert lands in a page that already exists, so adding one row never rewrites the store.
Structs§
- BTree
- Range
Iter - Reverse
Range Iter - A descending range cursor. Unlike reversing a forward
RangeIter, this pins one leaf at a time and never materialises the range it is walking. - TagHints
- The per-keyspace append hints for one handle.
Constants§
- TAG_
HINTS - How many leaves the per-keyspace append hint remembers at once.