PostgreSQL 的空闲空间映射（Free Space Map，FSM）是用于跟踪堆和索引关系中可用空间的数据结构。FSM 的设计目标是快速定位到有足够空间容纳新元组的页面，或者决定是否需要扩展新的页面。
FSM 页面的组织方式
-
存储结构
每个堆和索引关系（除了哈希索引）都有一个 FSM 文件，文件名以关系的文件节点号命名，并加上_fsm后缀。例如，如果关系的文件节点号是12345，则其 FSM 文件名为12345_fsm。 -
树形结构
FSM 被组织成一个页面树，底层 FSM 页面存储每个堆页面（或索引页面）的可用空间，每个页面用一个字节表示。上层 FSM 页面则聚合下层页面的信息。 -
页面内部结构
每个 FSM 页面内部是一个二叉树，存储在一个数组中，每个节点占用一个字节。叶节点表示一个堆页面或下层 FSM 页面，非叶节点存储其子节点的最大值。根节点存储叶节点中的最大值。 -
逻辑与物理地址
FSM 页面的逻辑地址由层级号和当前层的逻辑页号组成（FSMAddress）。物理地址则是 FSM 页面在_fsm文件中的偏移位置。
FSM 的功能与实现
-
快速查找
FSM 的主要功能是快速定位到有足够空间的页面，避免遍历整个数据文件。通过二叉树结构，可以快速判断某个页面是否有足够的空闲空间。 -
空间表示
PostgreSQL 使用一个字节表示每个页面的空闲空间，将空闲空间按 32 为步长分为 256 个区间，从而减少存储空间。 -
多层结构
FSM 的树形结构通常为三层：顶层和中间层为辅助层，底层为实际存储数据页面空闲空间的叶子节点。这种结构可以高效地支持大规模数据文件。 -
更新与搜索
FSM 的更新和搜索策略在 PostgreSQL 源码的src/backend/storage/freespace/README文件中有详细说明。
工具支持
PostgreSQL 提供了 pg_freespacemap 模块，可以用来检查存储在空闲空间映射中的信息，帮助管理员了解 FSM 的状态。
通过这种设计，FSM 在保证高效查找的同时，也减少了存储空间的占用，是 PostgreSQL 优化存储和插入性能的重要机制。
