Module bits 

A bitmap, a rank index over it, and select in both directions.

The rank index was written for the dense key map of spec/graph/03-the-file-format.md section 3.3 and lived inside keymap.rs until the monotone forward link of section 3.4 needed the same structure with select added. It is here rather than there because two callers with different reasons is what a module is for, and because the second caller needs an operation the first does not: a key map only ever asks how many keys are below this one, and a monotone link asks where the nth one is.

The rank index is unchanged by the move, including its serialized bytes, so a file written before it reads the same after. BitVector is the new part: it owns a bitmap, a rank index over it, and the sampling that makes select a bounded search rather than a scan.

What select costs and why it is not stored

Section 3.4 budgets “a sampled select structure of one position every four thousand ninety six ones plus a two-level rank index” at about thirteen percent over the bitmap. The rank index is stored, because rebuilding it is a pass over ninety four megabytes at SF100 and that is a thing you notice at open time. The samples are not stored, because rebuilding them is a pass over the superblock array, which at SF100 is a hundred and eighty three thousand entries and is not. A number derivable in a microsecond is a number that should not be given the chance to disagree with the array it describes.

Structs

BitVector

A bitmap with rank and select, in both directions.