转载：http://my.oschina.net/u/233784/blog/146389

前面几篇博客分析了shared buffer,从shared buffer到磁盘文件的映射，到shared buffer的分配和替换，再到如何测量shared buffer的性能情况，配置是否合理，基本把shared buffer大概介绍了下，这篇博客主要分析page。
page的源码落在/src/backend/storage/page，page对于Postgresql是个什么概念？page，block，file，这些概念怎么理解？
文件是数据库的持久化存储，当然我们已经知道数据库的relation以文件的形式存在在磁盘上，无论是xxx文件还是xxx_fsm,还是xxx_vm，这是文件的概念。当relation的xxx的文件特别大，超过1G的时候，同一个relation还会分文件存储，出现xxx.1，xxx.2这种文件。Whatever，文件在，Postgresql数据库的信息就在。
所谓block，指的是每次加载进内存的基本单位，如果Postgresql需要某个relation的信息，不会是直接relation对应的磁盘文件全部读入内存，而是分block载入内存。Postgresql有一定的规则知道自己需要的信息或者记录或者说tuple 落在磁盘文件的那个8K block上，然后将8K block加载入local buffer，或者shared buffer，总之加载入内存。简单的说，block是磁盘上文件和内存之间加载/驱逐的基本单位。
page是个什么概念呢？page大小也是8K，就是上面提到的block，只不过，page仔细的端详了8KB的内容，分析了信息是如何组织，如何存放到8KB的block空间之内。注意每条记录内部的结构不是page关心的事情，他的视角没有这个细，我们关心的是这条记录作为一个整体如何存放到8K的page中去;当然8K的page可能存放多条记录，如何摆放到8K的page中去;当前page剩余空间还有多少;我有一条需要空间为size的记录，page是否有足够的空间容纳之;记录可能会插入，也可能会删除，page里面会不会因为删除动作，页面内部有很多的洞，或者页面碎片化，如何清理碎片，这些都是page要解决的问题。
简而言之，page，就是管理8K大小的一亩三分地，他要把多条记录（Tuple）有条不紊地组织在这8K的空间之内。
一条记录会插入到8KB的page之中，信息如何组织？自然大多数记录占用的空间不会超过8KB，以我们前边提到的friends为例：

这个friends的设计不太好，不过我们的重点不在于此，我们关心的是这长度为8192（1个Block或者说1个page）的文件，到底存放的是啥内容？

我们看到文件虽然有8K，但是实际上只有最前面的2行32字节，和最后面的64字节中包含信息，因为这个文件对应的就是我们的friends这张表，而这张表里面有Lee，Bean ，158XXXXX，Nan Jing等信息，当然了这是一条记录，或者一个Tuple，Tuple内部的组成或者layout我们不关心，但是这个16385文件作为一定记录了这些信息。我们用vbindiff查看之：


我们看到了，我们的信息Bean，Nan Jing之类的，不管是如何组织的，的确存储在表friend对应文件16385之中。这条记录如何放入8K的空间之内，头部的一些字符有是干啥的，记录的信息为何放到了现在的这个位置，这就是page要管的事情，我们下面详查之。

上图就是page的结构图，8K的空间包括一个头部Page Header，若干个Item，每个Item指向一条记录（Tuple），有些Page在初始化的时候，就page的末尾，预留出空间作为Special用，作什么用，我暂时不知，不过没关系，不影响我们理解Page。当然了，有些Page不需要Special空间，就没有预留。
好我们可以分析源码了。
INIT-page的初始化
首当其冲的是PageInit函数。我们申请了一个新的干净的8K的page，把记录插入page之前，需要将page初始化，基本就是初始化一下Page Header。：

对于pageSize，默认情况下就是8K即BLCKSZ，而specialSize，某些情况下为0,某些情况下不为0,这都没关系。
Init做的事情是
1 给special预留空间
page header的成员变量pd_special相当于画了一条线，从pd_special这个位置到page的结尾，都是special的地盘，普通插入Tuple，都不许进入这个私有地盘。而且这个pd_special一旦初始化之后，这个值就不会动了。
2 设置pd_lower和pg_upper
当初始化的时候，pd_lower设置为SizeOfPageHeaderData，pd_upper设置为和pd_special一样。但是注意，这个lower和upper不是固定的，随着Tuple的不断插入，lower变大，而upper不断变小。当我们每插入一条Tuple，需要在当前的lower位置再分配一个Item，记录Tuple的长度，Tuple的起始位置offset，还有flag信息。这个Page Header中的pd_lower就是记录分配下一个Item的起始位置。所以如果不断插入，lower不断增加，每增加一条Tuple，就要分配一个Item（4个字节）。同样道理，Tuple的存放位置，根据upper提供的信息，可以找到将Tuple分配到何处比较合。分配之后，pd_upper就会减少，减少Tuple的长度（对齐也考虑进去）。
3 设置 page的size 和version
这个不多说，基本就是将版本号和page的长度记录在16bit的结构里面。
下面我们比较刚初始化和插入一条记录之后的情形：


一个记录对应两个部分，就头部附近Item空间和真正记录信息的Tuple。Item记录的是Tuple在Page的offset，size等信息。
AddItem-page增加一个记录
Page是用来存放Tuple的，增加一个Tuple删除一个Tuple都是Page份内的事情，我们首先看下Page如何增加一个Tuple：
functionPageAddItem是完成这件事情。因为这个接口是很通用的接口，要满足上层的各种需求，所以稍显复杂，不过整体还好。
item是我的当前记录的指针，size记录记录的长度，（item，item+size）这部分地址是Tuple的信息。Page表示从这个page中查找空间保存当前的Tuple。这我们很好理解，因为这是基本的要求：在当前页随便找个空间保存我的item。咱的要求比较简单，可是有些客户要求可就不简单了，比如客户要求，就要将我的记录拜放到page的第三个item，这就是比较坑爹的客户了。就像去饭馆吃饭，我到了饭馆，喊了一嗓子，小二，给哥随便找个8人桌，小二很happy，因为我的要求低。也有客官直接喊了一嗓子，小二，我要去三楼最好的那个雅间，如果有客人，让他给我腾地方，我们有8个人。得，小二就傻了眼，但是还得办不是。PageAddItem也是一样，offsetNumber这个如参表示，大爷我就要将记录存放在这个位置。overwrite则这个参数就更拽了，如果有记录放在我要的位置，让原来那条记录给大爷滚蛋，。如果overwrite =0 表示，大爷要的位置如果有人，原来位置的记录换个地方，给大爷我腾地方。 OK，这几个参数是干啥的，我基本交代清楚了

因为Page Header的长度是固定，而紧跟其后的Item的长度也是固定的，而每增加一个Item,pd_lower就增加一个Item的长度，这样，根据pd_lower就可以算出当前的页面已经有几个Tuple了。
这个limit记录的是当前记录数+1 ，用这个来判段新来的AddItem请求有没有指定既有的位置
上面分析了文艺青年式的AddItem，下面我们分析下普通青年的AddItem，普通青年要求低，随便找个地儿存放当年记录：
比较容易想到的是offsetNumber = limit = 当前记录数 + 1,这个太顺理成章了，那个PageHasFreeLinePointers是搞什么飞机？我们看下：
这个标志是啥意思？看名字的意思是 表征是否有free line。我们会把一些Item状态置为LP_UNUSED，这时候，Item和它原来的Tuple就没有映射关系。这样原来对应Tuple，就成了垃圾。后面会有会 PageRepairFragmentation清理这些空间，但是仍然不会删除这个LP_UNUSED状态的Item，只是打上一个标志，表示存在无主的Item，可以被复用。
因为新增个Tuple，需要alignedSize存储这记录的Tuple部分，所以pd_upper - alignedSize作为新的pd_upper.
ItemIdSetNormal把Tuple的size，offset信息记录在Item中：
PageIndexTupleDelete-page删除一条记录
我们下面讲述删除一条记录：
offnum指示第几个记录，offnum是从1开始计数的，查找对应item 是offnum-1.
我们找到Item，就可以找到Tuple对应的offset和size：

删除第二个记录之后，我们得到的Page布局如下：

我们可以看到，至少发生两次memmove
1 删除记录的Item后面的item都要往迁移，防止出现一个空洞
2 删除记录的Tuple后面的Tuple，也要移动，否则，会出现Tuple-2对应的空洞。
除了移动内存，item对应的指针也要发生相应的改变：比如洋红色的两个item需要修改offset
Page还剩多少剩余空间这是很重要的，这决定我们能否插入一条记录到当前Page。 原理就非常简单了，pd_upper - pd_lower,就是剩余空间，但是，还需要存放Item，所以还需要减Item占据的空间，剩下的才能存放Tuple的空间：
文章写的已经很长了，PageIndexMultiDelete 和PageRepairFragmentation核心逻辑是类似的，我就不写这两个。原来也不难，把这些碎片化的Tuple排个序，重新连接成一个连续的空间。
参考文献： 1 Postgresql 9.1.9 源码 原文链接：https://www.f2er.com/postgresql/195913.html