PostgreSQL 中的 fsm_search 函数有什么作用？

1.数据结构

宏定义
包括FSM页面的叶子节点数/非叶子节点数/FSM树深度等。

#define MaxFSMRequestSize MaxHeapTupleSize#define MaxHeapTupleSize (BLCKSZ - MAXALIGN(SizeOfPageHeaderData + sizeof(ItemIdData) ))#define FSM_CAT_STEP (BLCKSZ / FSM_CATEGORIES)#define FSM_CATEGORIES 256//如果块大小为 8K，FSM_CAT_STEP = 32#define Slot超频页面LeafNodesPerPage #define LeafNodesPerPage (NodesPerPage - NonLeafNodesPerPage ) = 8156 - 4095 = 4061#define NodesPerPage (BLCKSZ - MAXALIGN( SizeOfPageHeaderData) -\NBSP； Offsetof (FSMPAGEDATA, FP_NODES) = 8192-32-4 = 8156#DEFINE NONLEAFNODESPAGE (BLCKSZ/2-1) = 4095/**定义磁盘上时间。我们 n EED 能够寻址 2^32 -1 个块，* 并且 1626 是满足 X^3 >= 2^32-1 的最小数字。同样，*216是满足X^4>=2^32-1的最小数。实际上，*这意味着 4096 字节是我们可以通过 3 级树获得的最小 BLCKSZ，而 512 是我们支持的最小字节。 * 存储在磁盘上的树的深度。 * 我们需要对2^32 - 1块进行定位，1626可以满足X^3 >= 2^32 - 1是最小的数。 * 另外，216是能够满足X^4 >= 2^32 - 1的最小数字。 * 实际中，这意味着三层可以支持4096字节的Minimum BLCKSZ，512是最小支持的。 */#define FSM_TREE_DEPTH ((SlotsPerFSMPage >= 1626) ? 3 : 4)

FSMAddress
内部 FSM 处理 该过程采用逻辑寻址方案，每个t 的水平ree 可以被认为是一个独立的地址文件。

/* * 内部 FSM 例程按照逻辑寻址方案工作。树的每个级别都可以被认为是一个单独的可寻址文件。 * 内部 FSM 处理采用逻辑地址方案。 * 树的每一层都可以被认为是一个独立的地址文件。 */typedef struct{ //Level int Level;/*Level*/// 该level内的页码int logpageno; /* 级别内的页号 */} FSMAddress; /* 根页地址。 *///根页地址 static const FSMAddress FSM_ROOT_ADDRESS = {FSM_ROOT_LEVEL, 0};

FSMPage
FSM页数据结构。详细内容请参见src/backend/storage/freespace/README。

/* * FSM页面结构。 * 详细信息请参阅 src/backend/storage/freespace/README。 * FSM页数据结构。详细信息请参考 src/backend/storage/freespace/README。 */typedef struct{ /* * fsm_search_avail() 尝试分散多个负载* 以循环方式将不同的页面返回到不同的后端。 fp_next_slot 指向要返回的下一个槽（假设*上有足够的空间用于请求）。它被定义为 int, * 因为它的更新没有独占锁。 uint16 会更合适，但 int 更可能是原子地可获取/可存储的。 * fsm_search_avail() 函数尝试通过循环将不同页面返回到不同后台进程来将负载分散到后台进程。 * 该字段不需要独占锁。 ，因此定义为整数。 * unit16可能更合适，但integer似乎更适合原子提取和存储。 */int FP_NEXT_SLOT;/**FP_NODES 包含二叉树，存储在数组中。第一个*nonleafnodeSperpage 元素是上节点，后面的*lea FNODESPERPAGE 元素是叶节点。未使用的节点为零。*fp_nodes以数组的形式存储二叉树。*第一个t NonLeafNodesPerPage 元素是上一层的节点，后面的 LeafNodesPerPage 元素是叶子节点。 * 未使用的节点为0。 */ uint8 fp_nodes[FLEXIBLE_ARRAY_MEMBER];} FSMPageData;typedef FSMPageData *FSMPage;

/*要么已经尝试过，要么超出关系末尾*///已经尝试过或者已经超出表末尾# define FSM_LOCAL_NOT_AVAIL 0x00/* 可尝试 *///可尝试 #define FSM_LOCAL_AVAIL 0x01/* * 对于小型关系，我们不创建 FSM 以节省空间，而是使用 * 本地内存中页面映射来尝试。为了找到可用空间，我们只需直接尝试 * 页面，而无需提前知道它们有多少可用空间。对于小表，不需要创建FSM来存储空间信息和使用本地内存映射信息。 * 为了找到免费的水疗中心ce，我们不需要知道他们有多少可用空间，只需尝试该页面即可。 * * 请注意，此映射用于查找任何给定关系所需的可用空间 * 的块。当我们发现一个具有足够可用空间的块时，当我们扩展关系时，或者在事务中止时，我们会清除此映射。 * 有关更多详细信息，请参阅 src/backend/storage/freespace/README。 * 请注意，此映射用于搜索给定表所请求的可用空间。 * 当找到有足够空闲空间的块/关系扩展/事务回滚时，这个map的信息被清除。 * 详细信息请查看 src/backend/storage/freespace/README。 */typedef struct{ BlockNumber nblocks;//块数 uint8 map[HEAP_FSM_CREATION_THRESHOLD];//Array} FSMLocalMap;static FSMLocalMap fsm_local_map ={ 0, { FSM_LOCAL_NOT_AVAIL}};#define FSM_LOCAL_MAP_EXISTS (fsm_local_map.nblocks > 0)

一般例程
包括获取左子节点/右子节点子节点/父节点等

/* 用于在页面内导航树的宏。根的索引为零。 *///遍历page中的树。根号为0#define leftchild(x) (2 * (x) + 1)#define rightchild(x) (2 * (x) + 2)#define Parentof(x) (((x) - 1) / 2 )/* * 找到 x 的右邻居，在级别内环绕 * 搜索 x 邻居的右侧，如果需要将它们环绕在同一级别 */static intrightneighbor(int x){ /* * 向右移动。这可能会环绕，步进到下一个级别的最左边的节点。 * 向右移动。这可能会导致到下一级最左边的节点的回绕。 */ x++; /* * 检查我们是否已走到下一级的最左边节点，如果是，则更正。每层最左边的节点编号为 x = 2^level - 1，因此 * 使用标准的补码算术技巧检查 (x + 1) 是否为 2 的幂。 * 使用标准技巧检查 (x + 1) 是否是 2 的幂。在该级别的最左侧节点上，如果是，则更正 x。 * 最左边的节点号每个级别上都是 x = 2^level - 1, * 因此，检查 (x+1) 是否是 2 的幂，使用标准的补码算术技术就足够了。 */ if (((x + 1) & x) == 0)//有符号整数，全1为0 x = Parentof(x); return x;}/* * 返回FSM页的物理块号 * 返回FSM页的物理块号 *//*计算公式：要找到叶子页n对应的物理块#，我们需要统计数量页 n 之前的叶页和上层页的数量。结果为 bey = n + (n / F + 1) + (n / F^2 + 1) + ... + 1，其中 F 是扇出。第一项 n 是前面的叶子页数，第二项是第 1 层的页数，依此类推。*/static BlockNumberfsm_logic_to_physical(FSMAddress addr){ BlockNumber pages;//块号 int Leafno;//Page number int l;//临时变量 /* * 计算给定页下面的第一个叶页的逻辑页号。 * 给定页面下，计算逻辑l 第一个叶子页的页码 */ leafno = addr.logpageno; for (l = 0; l < addr.level; l++) leafno *= SlotsPerFSMPage; /* 计数寻址叶子页所需的上层节点 */ //计数用于定位叶子页的上层节点个数pages = 0; for (l = 0; l < FSM_TREE_DEPTH; l++) { 页数 += leafno + 1; leafno / = SlotsPerFSMPage ; } /* * 如果我们请求的页面不在底层，则减去我们上面计算的其他较低级别的页面。 */ 页 -= addr.level; /* 将页计数转换为从 0 开始的块号 */ //计数从 0 开始（减 1） return page - 1;} /* * 返回给定堆块对应的 FSM 位置。 * 返回给定堆块的 FSM 位置。 。 *///addr = fsm_get_location(oldPage, &slot);静态 FSMAddressfsm_get_location(BlockNumber heapblk, uint16 *slot){ FSMAddress addr; addr.level = FSM_BOTTOM_LEVEL; //#define SlotsPerFSMPage Leaf NodesPerPage //#define LeafNodesPerPage (NodesPerPage - NonLeafNodesPerPage) = 8156 - 4095 = 4061 //#define NodesPerPage (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) - \ &nBSP; Offsetof (FSMPAGEDATA, FP_NODES) = 8192-32-4 = 8156 //#definenleafnodeSperpage (BLCKSZ/2-1) =第4095章/span> 2.源码解读
fsm_search函数搜索FSM并找到具有足够可用空间（min_cat）的堆页。
/* * 在树中搜索堆至少具有 min_cat 可用空间的页面 * 搜索 FSM 以查找具有足够可用空间 (min_cat) 的堆页面 * ///return fsm_search(rel, search_cat);static BlockNumberfsm_search(Relation rel, uint8 min_cat){ int restarts = 0; FSMAddress addr = FSM_ROOT_ADDRESS; for (;;) { //---------loop int slot; Buffer buf; uint8 max_avail = 0; /* 读取 FSM 页 */he page */ //在页内搜索 if (BufferIsValid(buf)) { LockBuffer(buf, BUFFER_LOCK_SHARE); //搜索可用槽 slot = fsm _search_avail(buf, min_cat, (addr.level == FSM_BOTTOM_LEVEL), false);if (slot == -1) //获取最大可用空间 max_avail = fsm_get_max_avail(BufferGetPage(buf) ）；解锁释放缓冲区（buf）； } else              //buffer无效，则设置为-1         slot = -1; if (槽！= -1)                                                                                                                             公共服务提供商； * 下降树，或者如果我们在底部，则返回找到的块。 * 如果位于树的底部，则返回找到的块。 */ if (addr.level == FSM_ BOTTOM_LEVEL) return fsm_get_heap_blk(addr, slot);使用 使用 使用 使用 使用 ‐ 使用 使用使用 through out through out through out out out through out through out through out out out out out out out out out out of  时 While- s to            {                                                                       */           返回InvalidBlockNumber； } else else { uint16 父母槽； FSMAddress 父级； date * 上层节点，避免再次陷入同样的​​陷阱，并 * 重新开始。 * 在下层，如果上层节点没有反映下层页面的值，就会出现故障。我们面前的父 * 页面。然后，我们将使用我们拥有的现在*过时的信息更新父页面。没关系，因为它应该很少发生，and 将由下一次真空修复。 * 我们发布后，如果另一个后台进程更新了这个页面并锁定了我们之前的父节点，就会出现竞争条件。 * 然后我们使用现有已知的Stable信息更新父页面。 * 如果可以，因为这种情况很少发生，所以这个问题将在下一次真空中修复。 */ 父 = fsm_get_parent(addr, &parentslot); fsm_set_and_search(rel, 父级, 父级槽, max_avail, 0 );; * 如果上面的页面严重过时，我们可能需要循环很多次，随时更新它们。任何不一致*最终都应该得到纠正并且循环应该结束。然而，无限循环**仍然很可怕，因此请提供紧急**阀。 * 如果上页太旧，可能需要循环多次来更新上页信息。 *不一致会被循环修正，循环就会停止。*但是无限循环很可怕，所以设置阈值，超过这个阈值就退出循环。*/If (RESTARTS ++> 10000) Return InvalidBlocknumber;/*Start Search All Oveer From the root*///从root开始搜索addr = fsm_root_address;}}} 
 
 " postgreSql中的FSM_SEARCH函数的作用是什么》这里，谢谢大家的。读。如果您想了解更多行业资讯，可以关注网站，小编将为大家输出更多优质实用文章！