看代码，之困难在于如何剥离繁芜的细节，直接到代码的核心，即代码到底要解决什么问题，代码用的什么算法或者思想来解决的，弄懂了这个，基本摧枯拉朽了。就像上一篇源码分析Page。Page要解决的问题是多条记录在8KB的空间内存储问题，这自然包含当前8KB的空间内有多大的剩余空间;如何插入一笔记录到8KB的空间;如何删除一笔记录;至于算法实现，对照Momjian绘制的那副Page的图片，足以理解Page的所有代码。
   我们在数据库的磁盘文件中可以发现以fsm后缀的文件名，这些文件是干啥的，另外这些文件最小是24KB三个block的大小，从未见过8KB的fsm文件，这又是为何，这篇文章将要讲述这些问题。

    所谓FSM，指的是Free Space Map，空闲空间映射表。这个是干啥的呢？莫急，听我细细道来。一个relation有多个8KB大小的block，这些block存储在磁盘上。我们可以获取一个relation一共有多少个block。

    这个uinit32就决定了一个relation最大只能有4G个block，考虑到每个block大小为8KB，也就是说一个relation的磁盘大小最大为32TB,已经很大了。注意relation的不断的插入删除记录，会造成很多的block其实是有空闲空间的，Page的空闲空间管理的只是8KB空间内有多少剩余空间，而FSM管理的则是relation对应的所有的Block（或者说page，whatever，反正都是这8KB的空间）分别有多少剩余空间：
   FSM存储的并不是真是的剩余空间，而是近似值，用一个字节表示剩余空间的大小，也就是说

剩余空间分成了256个档次，每8K/256=32为一档，那么，一个字节就足以表示一个block的剩余空间。
   如果让你来管理relation所有block的的剩余空间，你如何做？最容易想到的方法就是以数组的方法表示各个block的剩余空间，fsm[0]表示第0个block的剩余空间，fsm[1]表示第一个block的剩余空间，然后把这个信息存入fsm文件即可。比如我想知道第800个block（0-based）还剩下多少空间，只需要将对应的fsm文件的第800个字节（从0开始计数）读出来即可。方便可以扩展，比如relation新增一个block，只需要fsm文件新增一个字节即可。
   目前看起来很完美，可是数组有致命的缺陷，我要查找剩余空间的值最小为40的，那数组就傻了眼，因为他不得不挨个的比较，知道遇到值大于40的才能停下，如果block特别多，数组长度非常大，这个问题就会恶化。运气好很快就找到了，运气不好可能遍历了整个数组，效率太低。所以不能采用这种方法。
   PostgreSQL采用的方法是分层+堆的思想。想想看假如有100万人需要你管理，你如何管理？只能分层，每100人选出一个百夫长，每100个百夫长选出一个万夫长，我来管理100个万夫长。这就是分层管理的思想。
  PostgreSQL源码中有个比较有意思的常数：

    如果SlotsPerPage>=1626,则为三层，否则，则为4层。什么意思？开始我也没看懂，看了注释方明白：刚才我们举例子是每100个人举出一个管理者，只需要三层就可以管理100万人。现在我们的需求是管理4G个block，到底是需要三层管理还是四层管理？就要看每层管理多少人。

    我们看到1626的立方是大于4G的，而1625的立方是小于4G的，所以要想三层管理4G的对象，必须每层次至少管理1626个子层。事实上，block大小为8KB，用一个字节管理一个子对象，每次管理的大约是4000左右 。4000×4000×4000 >>4G,三层管理结构，足以管理4G个block。

    现在我们分了层，但是仅仅分层是不够的。想想下面的场景，如果用户请求大小为620字节的空间，我一算（620+31）/32 = 20,需要freespace值为20的block。总领袖招来了4000个下属，问，你们谁的树下有超过20个freespace啊。我的4000个下属分别向自己的4000个下属询问，谁的下属有超过20的freespace，下属再向下属的下属询问...，这个场面很鸡飞狗跳，原因在于，没有管理好下属，不了解下属的情况。
   这就要用到堆的思想了。我有4000个下属，管理颇为不便，毕竟我不能挨个去问，你有没有超过20的剩余空间。那怎么办能，这就是heap的思想了：

   我们以管理4个下属为例，3和4一组PK，胜者是4,0和2一组PK，胜者是2 ，然后胜者4和2继续PK，胜者是4,依次类推，在最顶端的就是能力最强的下属。管理4000个下属其实也一样。两两一组，从最底层开始PK，得到两人中的优胜者，然后两人中的优胜者在两两PK，得到4人中的优胜者，以此类推，最终得到4000下属中的优胜者。如果4000下属的最终优胜者都不能满足需求，那么就不能满足需求了。如果可以的话，可以找到最接近需求的那个下属，比如我需要3,而顶层是4，表示可以找到，然后询问左右孩子，哪个可以办到。

   上图解释了分层管理，每个FSM的block有个逻辑块号，也有个物理块号。逻辑块号采用如下的方式表示：

    level表示第几层，logpageno表示该层的第几个下属。就是上图方框里面的数字，最顶层的是（2,0），他的第一个下属是（1,0），以此类推。www.it165.net
   除了逻辑号，还有物理块号，这些管理信息是以block的形式存放在FSM文件中。比如最顶层的root（2,0），对应fsm文件的第0个块号,就是上图中椭圆中的数。请注意，relation文件比较小的时候，比如只有一个block，那么其实只可能有三个fsm文件的block。因为（0,0）本身就可以管理4000个block，而（1，0）暂时管理（0,0）一个下属，而（2,0）管理（1,0）一个下属，其他的fsm block暂时不存在。虽然只有1个relation的block，但是需要个FSM block去管理。当然了（0～3999）个relaiton的block，也只需要这三个FSM block 块管理就够了。这也就解释了为什么FSM文件最少也是24KB，因为三层管理结构，哪怕只有1个block需要管理，也需要3个FSM blcok。

    原理都讲清楚了，剩下的都是细节了。比较典型的应用是：

这个函数就是典型的FSM的作用：给你一个relation,和spaceNeed，获取relation的哪个块的剩余空间可以满足要求。

    前面讲的都是根据FSM文件查找，一直没有讲述FSM文件信息的更新，relation的block不是固定不变的，假如relation的第N个block的剩余空间发生了变化，FSM文件就会发生改变，首先第0层会变化，如果必要会通知1层和2层的相关信息。
   我就不展开讲解细节了。

--转自