PostgreSQL 源码解读（146）- Storage Manager#2（fsm_search_avail函数）

本节简单介绍了PostgreSQL在执行插入过程中与存储相关的函数RecordAndGetPageWithFreeSpace->fsm_set_and_search,该函数设置给定的FSM page的相应值,并返回合适的slot。

FSMAddress


内部的FSM处理过程以逻辑地址scheme的方式工作,树的每一个层次都可以认为是一个独立的地址文件.

FSMPage


FSM page数据结构.详细可参看src/backend/storage/freespace/README.

FSMLocalMap


对于小表,不需要创建FSM来存储空间信息,使用本地的内存映射信息.

fsm_set_and_search设置给定的FSM page的相应值,并返回合适的slot.

主要处理逻辑如下:

1.初始化相关变量

2.设置相应页面的FSM可用标记

3.如search_cat/minvalue(请求空间)不为0,则调用fsm_search_avail搜索slot

4.解锁,返回

搜索树的算法是逐渐扩展”search triangle”(暂且称为搜索三角),也就是说,被当前节点所覆盖的所有节点,确保我们从开始点向右搜索.在第一步,只有目标slot会被检查.当我们从左边子节点往上移动到父节点时,我们同时添加了父节点的右子树到搜索三角中.当我们从右边子节点往上移动到父节点时,我们同时删除了当前搜索三角(这时候已经知道了没有合适的page), 同时向右检索下一个更大尺寸的三角.因此,我们免费云主机域名不会从起点向左搜索,在每一步搜索三角的尺寸都会翻倍,确保只需要log2(N)步就可以搜索N个页面.

例如,考虑下面这棵树:

假定目标节点是字母T指示的节点,同时我们正在使用6或更大的数字搜索节点.检索从T开始.在第一轮迭代,移到右边,然后到父节点,到达最右边的节点 5.在第二轮迭代,移到右边,回卷,然后上溯,在第三个层次上到达节点 7这时候7满足我们的搜索要求,因此我们沿着7这条路径下降到底部.实际上,这是(考虑到回卷)起点右侧第一个满足条件的页面.

测试脚本

启动gdb,设置断点

输入参数

获取buffere,并锁定

获取page

调用fsm_search_avail函数,进入fsm_search_avail

获取FSMPage,fp_nodes数组,0表示未使用

使用fp_next_slot开始搜索.

从目标slot开始检索.每一步,把节点移到右边,然后上溯父节点.

在到达一个有足够空闲空间的节点时停止(因为根节点有足够的空间).

循环,直至找到满足条件的节点.

方法是移动到右边,如需要在同一层次上回卷,然后上溯.

现在已到达了有足够空闲空间的节点,树中间的某个位置上面.

沿着有足够空闲空间的路径下降到底部.

如有选择,往左移动.本例,往左移动了.

找到了相应的叶子节点

现在已到底层,在有足够空间的节点上.

同时,更新下一个目标块指针.

回到fsm_set_and_search,返回slot

DONE!

PG Source Code

Database Cluster, Databases, and Tables

相关推荐: Oracle Vault是什么

这篇文章主要为大家展示了“Oracle Vault是什么”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“Oracle Vault是什么”这篇文章吧。Oracle数据库作为目前最成熟的商业数据库，在稳定其核心功能的同时…