free-space-maplisted

# free-space-map — where INSERT finds room The Free Space Map tracks approximate free space per page in a relation, so INSERT and other appenders can find a target page without scanning. It's a **fork** of the relation (like the visibility map — a separate file at `<relfilenumber>_fsm`), organized as a tree over the heap's page numbers. The design tradeoff: exact byte-level accounting would require WAL-logging every space change and dominate write traffic. Instead, FSM stores a small **category** per heap page (5 bits, 32 buckets) and updates it lazily — not WAL-logged in the hot path — with periodic reconciliation by VACUUM. ## The file map | File | Lines | Role | |---|---:|---| | `freespace.c` | ~870 | Main API: `RecordAndGetPageWithFreeSpace`, `GetPageWithFreeSpace`, `RecordPageWithFreeSpace`, `FreeSpaceMapVacuum{Range}`. Tree traversal + descent. | | `fsmpage.c` | ~430 | Per-FSM-page operations. Each FSM page is a binary tree; `fsm_search_avail`, `fsm_set_and_search`, path navigation within a page. | | `indexfsm.c` | ~55 | The 2-function shim for indexes. Indexes reuse the FSM machinery but only for "is this page reusable?" — the category is 0/nonzero. | The README in `src/backend/storage/freespace/` has an ASCII diagram of the tree layout — read it before touching FSM code. It's the shortest path to understanding the layout. ## The 3-level tree FSM's `<relfilenumber>_fsm` file contains FSM PAGES (not heap pages). Each FSM page holds a **binary tree of 4096 slots**