简介上一篇文章的结尾《PostgreSQL的MVCC机制解析》提到PostgreSQL使用vacuum命令处理过期数据。本文将继续介绍vacuum命令并使用它来导致PostgreSQL空闲数据块的产生，然后分析空闲数据块管理机制的原理。根据PostgreSQL的MVCC机制，所有的UPDATE和DELETE操作都会产生过期数据，需要使用vacuum命令来清理过期数据。vacuum命令基本上有两种类型：VACUUM将过期元组对应的磁盘空间标记为可用，但实际上并不释放该空间给操作系统，其他程序无法重用。该操作不需要排它锁（EXCLUSIVELOCK），不影响表的读写操作。VACUUMFULL将普通元组数据复制到新的磁盘文件中，重组，删除原数据文件，将未使用的磁盘空间归还给操作系统。该操作需要获取排它锁，会影响正常的读写操作。.因此，执行该操作时需要谨慎，尤其是表数据量较大时，执行时间会比较长。我们知道PostgreSQL的表（Relation）其实是由多个物理数据块（页）组成的。在执行vacuum操作之后，这些具有过期记录（元组）的数据块中的磁盘空间将被标记为可用。会有自由空间。当增加一条新记录（元组）时，会先重用表中数据块的空闲空间，而不是分配新的数据块。但是，当多个数据块都有空闲空间时，应该选择哪个数据块来保存新的记录呢？所选记录必须有足够的空间来存储新记录。空闲数据块的组织结构为了解决上述问题，PostgreSQL设计了FSM（FreeSpaceMap）结构来表示每个数据块中空闲磁盘空间的大小。pg8.4版本之后，每个表（Relation）都会有一个独立的FSM空间，具体为一个以_fsm为后缀的物理文件：-bash-4.2$cd$PGDATA/ins2/base-bash-4.2$ll*fsm-rw------1postgrespostgres24576Jun2615:401247_fsm-rw------1postgrespostgres24576Jun2615:401249_fsm-rw------1postgrespostgres24576Jun2615:401255_fsm数据块，减少IO，节省搜索带来的开销（即FSM文件的大小），FSM结构只用一个字节记录一个数据块中的空闲磁盘大小，因为1byte=8bits，那么可以记录2^8个空闲磁盘大小，假设一个数据块大小（BLCKSZ）为8k（PostgreSQL默认为8k），那么可以分成256（2^8）等份，每份有BLCKSZ/256字节表示范围，例子如下：RangeCategory0-31032-631......8096-81272538128-81632548164-8192255FSM数据块中的数据结构知道数据块中空闲空间的表示方法，那么如何组织这些表示离子记录保持高效率查询效率呢？答案是PostgreSQL使用二叉树结构（大根堆）来存储这些代表空闲空间大小的记录。叶子节点存储实际空间大小的记录，非叶子节点仅作为辅助查询。当需要检查是否有合适的数据块大小时，只需要比较树的根节点就知道了，大大减少了查询次数。大根堆数据结构示例如下：4423402<-Thislevelrepresentssheappages上例中叶子节点的值3、4、0、2分别表示空闲数据块的映射值，值3表示[96,127]块中有空闲磁盘空间的数据。PostgreSQL源码中FSM页数据结构定义如下：typedefstruct{intfp_next_slot;uint8fp_nodes[FLEXIBLE_ARRAY_MEMBER];}FSMPageData;其中，fp_next_slot指向下一次查询开始的slot位置。具体功能后面会讲到。fp_nodes数组存放的是二叉树的节点值。FSM数据块中的数据存储结构类似于下图所示：根据这种存储结构，一个FSM数据块（存储FSM的数据块）实际可以存储的记录数（数据块）records与普通数据块大小相同）空闲空间大小对应的map值）为：(BLCKSZ-headers)/2//除以2，因为二叉树的叶子节点数约为1/2节点总数。其中，BLCKSZ表示数据块的大小，headers表示固定大小的数据块头信息。如果数据块默认大小为8k，那么单个FSM数据块可以存储的记录数约为4000条。另外，PostgreSQL中一张表（Relation）最多可以有2^32个数据块，所以amaximumof2^32recordsarerequiredMap记录用于指示这些数据块中可用空间的大小。显然，单个FSM数据块无法存储这些记录，实际需要大约2^32/4000个FSM数据块来存储。前面我们介绍了在单个FSM数据块中存储map值的数据结构。当有多个FSM数据块时，我们应该按照什么顺序选择FSM数据块页进行搜索呢？按顺序搜索FSM数据块显然效率太低了。FSM数据块间的逻辑组织结构为了提高查找FSM数据块的效率，PostgreSQL采用了一种Higher-level（类似于多叉树）的逻辑结构来组织FSM数据。为每个FSM数据块指定一个额外的逻辑结构FSMAddress。数据结构定义如下：#defineFSM_TREE_DEPTH((SlotsPerFSMPage>=1626)?3:4)#defineFSM_ROOT_LEVEL(FSM_TREE_DEPTH-1)#defineFSM_BOTTOM_LEVEL0typedefstruct{intlevel;/*level*/intlogpageno;/*pagenumberwithinthelevel*/}FSMAddress;其中，level表示FSM数据块的层数，logpageno表示在该层的序号，序号从0开始。类似于FSM单个数据块中的存储方式，只有FSM数据块在最高层（level=0）实际存储记录，其他层作为查询的辅助层，上层的叶节点值代表下层值的根节点。需要多少层逻辑结构来表示所有的数据块记录？答案是当一个FSM数据块中存储的记录（map值）超过1626条时，三层就够了，因为162616261626>=2^32。下面用一张示意图来表示整体的组织架构。为了简化示意图，图中每个数据块只存储4个字节的数据，符合存储1626个字节的原则。FSM文件数据块间的逻辑组织结构示意图如下：如图所示，第二层数据块中的叶子节点值123代表第2层数据块的根节点值。下一层（第一层）的0，和第一层0号数据块的叶子节点值123表示0层1号数据块的根节点，叶子节点值1230层1号数据块的表示数据块空闲空间大小[3936,3967]字节。每个数据块都有一个逻辑地址。例如，1号数据块的逻辑地址{1,0}表示第一层的0号FSM数据块，实际上是对应的FSM物理文件的1号数据块。第二层和第一层FSM数据块中存储的数据仅作为辅助层索引。实际上，只有第0层FSM数据块中的叶子节点存储了表中空闲数据块的map值，其他节点都是索引值。空闲数据块搜索算法上面介绍了空闲数据块的表示方法和FSM文件中各个数据块的组织形式，接下来介绍空闲数据块的搜索算法。首先介绍FSM数据块内的查找算法。对于大根堆二叉树查找，简单的方法就是每次从根节点开始比较查找。如果根节点小于要查找的值，说明块中没有满足条件的map值，否则可以继续寻找满足条件的叶子。节点。然而，PostgreSQL的设计并不是这样的。而是使用前面介绍的FSMPageData结构的fp_next_slot来保存下一次查询的起始位置（slot）。查找算法如下：比较根节点值，如果要查询的值大于根节点，则直接返回，说明FSM数据块中没有满足条件的map值，否则继续下一步。比较查询的起始位置（slot）对应的map值，如果不满足则进行下一步，否则跳至第5步。将新的查询位置设置为下一个槽（slot）的父节点number+1，槽值代表叶子节点的序号），然后比较。如果不满足条件，则重复此步骤，直到向上找到根节点。如果找到满足条件的中间节点，则继续下一步。往下看，找到满足条件的叶子节点，然后进行下一步。为下一次查询重新设置fp_next_slot变量，然后返回叶子节点的slot。FSM数据块中搜索算法核心源码如下：FSM数据块中搜索算法核心源码如下：intfsm_search_avail(Bufferbuf,uint8minvalue,booladvancenext,boolexclusive_lock_held){...restart:if(fsmpage->fp_nodes[0]
