空闲空间映射表(FSM)

随着数据表中不断插入和删除元组,页内必然会产生空闲空间。当我们需要插入新的元组时,需要优先将元组放到已有页内的空闲空间内,以节约存储空间。如果每次都用新的页来存放新元祖,显然会造成空间利用率的浪费。但我们怎么知道哪个页中有空闲空间、空闲空间的大小是否足够存放新的元组呢?如果没有其他任何技术,则需要遍历页、直到找到足够的空闲空间用于插入新元组,这样开销将会非常大。为了解决这个问题,PostgreSQL使用了空闲空间映射表(FSM)来记录所有表文件的空闲空间信息。

在PostgreSQL中,对于每一个表文件(包括系统表)都会同时存在一个名为OID_fsm的空闲空间映射表,其中OID是对应表的oid。

FSM中存储的并不是实际的空闲空间大小,而是用一个字节来表示一个范围内的空闲空间大小,如下表所示:

字节空闲空间范围(字节)
00 ~ 31
132 ~ 63
......
2558164 ~ 8192

为了更快的查找,FSM文件也不是使用数组存储每个页的空闲空间,而是使用了一个三层树结构。第0层和第1层是辅助层, 第2层用于实际存放各表页中的空闲空间字节位。

Last Updated:
Contributors: yuesong-feng