Module bulk 

Building a large tree by repeated insertion means one descent and one random write per key. Sorting first and packing bottom-up means one sequential pass.

Peak RAM is the arena in phase 1 and MAX_FANOUT x buffer in phase 2. Both are chosen numbers, neither is proportional to the input. That is Law 1 by construction rather than by care: without a fanout cap, iter would open every run at once and merge memory would be run_count * buffer, and run_count is input / arena – linear in the input, correct at the test scale and wrong at the target one. SortedRuns::merge_down bounds it by merging runs down to at most MAX_FANOUT before the final pass.

Phase 3, pack_tree, is bounded the same way and for the same reason. It used to accumulate one (first_key, page_no) pair per page of the level it was building into a Vec, which is one entry per page and therefore linear in the rows – correct at the test scale, wrong at the target one. Measured on a 209M-row / 50.08 GiB load under a 1 GiB cap, that vector was several hundred MiB of the 539 MiB rss_anon the process peaked at, against a 113 MiB pool. Each level is now spilled to a scratch file as it is built and streamed back to build the level above it, so peak pack memory is one write buffer plus one read buffer whatever the input.

SACRIFICE (Law 4): the input is written to temporary files and read back, so a bulk load costs roughly 3x the data in sequential I/O and needs scratch disk comparable to the input, plus one more read-and-rewrite pass of the whole dataset for every factor of MAX_FANOUT the run count exceeds it. Bought: linear build time instead of a curve, with merge memory that stays fixed regardless of how large the input grows.

SACRIFICE (Law 4), scratch integrity: every temporary record carries four checksum bytes and is checksummed once when written and once when read. Extra merge passes repeat that work. Bought: a changed scratch byte cannot become a checksummed page and then pass the publication row-count check.

SACRIFICE (Law 4), spilled separators: each level’s separators are written once and read once instead of being held. That is 16 + key_len bytes per PAGE of the level, not per row – for 8-byte keys, 24 bytes per 4096-byte page, so the level-0 file is about 0.59% of the tree it describes and every level above it is another ~1/200th of that. Measured at 0.586% of the tree (265,080 B of scratch against a 45.2 MB tree) by pack_tree_spill_is_a_small_fraction_of_the_tree in kernel/tests/pack_shape.rs, which polls the scratch directory while the pack runs rather than deriving the figure from the record layout. Scaled to the 50.08 GiB reference load that is ~300 MiB of extra sequential I/O. Bought: pack memory that does not grow with rows at all, which is the whole premise of indexing 50 GB under a 1 GiB cap.

Structs

ExternalSort

Removes its scratch directory if it is dropped without finish().

MergeIter

SortedRuns

Functions

pack_tree

Pack a complete sorted tree. Kept as the stable whole-tree primitive used by bulk load and recovery; range grafting extends it through pack_range instead of duplicating its page builder.

pack_tree_pooled

Pack a complete sorted tree through the ORDINARY buffer pool.