1. 表的页面结构

1.1 表和索引相关文件的布局

在数据库内部，表和索引作为数据库对象是通过oid(object identifier, 对象标识符)来管理的，而这些数据文件由变量relfilenode管理。
数据库和堆表对象的 oid 分别存储在pg_database和pg_class 中。
表和索引在刚创建的时候，relfilenode值是与其oid一致的；但是在后续维护过程中relfilenode会发生变化，oid不会变。

查看t1表的oid及relfilenode值：

select relname,oid,relfilenode from pg_class where relname='t1';

查看t1表的文件：

select pg_relation_filepath('t1');

表和索引的relfilenode值会被一些命令所改变。
例如对表t1执行TRUNCATE命令，会为表分配一个新的relfilenode(24595)，删除旧的数
据文件(24592)，并创建一个新的数据文件(24595)：

新建表：

对表执行truncate后：

当表和索引的文件大小超过1GB时，会创建并使用一个名为relfilenode.1的新文件。
如果新文件也填满了，则会创建下一个名为 relfilenode.2的新文件，以此类推。
之所以采用1G的大小，是因为在32位操作系统中，允许的单个文件最大大小一般是2G或者4G，采用1G可以避免操作系统integer溢出的问题。在实践中发现1G也是最合理的值。

在数据库系统内部，这些文件(主体数据文件、空闲空间映射文件、可见性映射文件等)也被称为相应关系的分支(fork)。
表、索引、TOAST表都归类为关系。
每个关系(relation)可能会有4种分支，分支编号分别为0、1、2、3

• 0号分支main为关系数据文件本体
• 1号分支fsm(空闲空间映射)保存了main分支中空闲空间的信息
• 2号分支vm(可见性映射)保存了main分支中可见性的信息
• 3号分支init 是很少见的特殊分支，通常表示不被日志记录的表与索引

1.2 堆表文件的内部结构

其中重点如下：

• pd_lsn: 存储最近改变该页面的xlog位置。（在集群环境下，xlog堆积等问题可能会用到）
• pd_checksum: 存储页面校验和。（页面损坏问题可能会用到）
• pd_lower，pd_upper: pd_lower指向行指针(line pointer)的尾部，即图中的pg_linp[1]，pd_upper指向最后那个元组，即图中的Tuple2（元组是从页尾往前写的。所以Tuple2实际上是时间上更靠后的）。
• pd_special: 索引页面中使用，它指向特殊空间的开头。（pd_special在堆表中是个固定值，没什么用；但在索引中是串联形成平衡树的）
• pd_line: 行指针，四字节，每一条元组会有一个行指针指向真实元组位置。
• Tuple: 存放真实的元组数据，
  注意元组是从页面的尾部向前堆积的，元组和行指针之间的是数据页的空闲空间。

page选择8192大小的原因主要是出于在常用场景表列数支持下，对性能和效率的考虑。
以下是几个主要因素:

• 1.内存管理: 内存中，在linux下，每页的大小通常为4096，选择8192(显然选择4096更合适，为什么选择的8192?)大小的页面可以更好地适应内存缓存的页大小，从而提高查询效率。
• 2.I/O性能: 磁盘I/O操作是数据库性能的一个重要瓶颈。选择8192(16384更加减少磁盘I/O操作次数，为什么还是8192?)大小的页面可以更好地利用磁盘块的大小，从而减少磁盘I/O操作次数，提高数据库的整体性能。
• 3.并发控制: Postgresql数据库使用多版本并发控制(MVCC)机制来支持并发访问。选择8192大小的页面可以更好地控制并发访问时的锁竞争，从而提高并发性能。

注：8KB也是理论和长期实践得出的结论。

1.3 行页面结构

即元组的结构：

• t_xmin: 代表插入此元组的事务xid;
• t_xmax: 代表更新或者删除此元组的事务xid，如果该元组插入后未进行更新或者删除，txmax=0:
• t_cid: commandid，代表在当前事务中已经执行过多少条sql，例如执行第一sql时cid=0，执行第二条sql时cid=1;
• t_ctid: 保存着指向自身或者新元组的元组标识(tid)，由两个数字组成，第一个数字代表物理块号，或者叫页面号，第二个数字代表元组号。
  在元组更新后tid指向新版本的元组，否则指向自己，这样其实就形成了新旧元组之间的“元组链”，这个链在元组查找和定位上起着重要作用。

如下面例子中，我们事务100先插入一条记录，值为a，t_ctid值是(0,1)表示在0页的1号元组。
然后我们事务101将其更新为b，结果如下：

在此基础上我们的事务102将其删除，结果如下：

1.4 页面结构的变化：DML

依赖于安装pageinspect插件。

参考：

https://cloud.tencent.com/developer/article/1377728

然后执行vacuum：

2. FSM及VM的介绍

2.1 FSM

空闲空间管理：用于快速定位到表文件中的空闲空间以便于插入新数据及整理空间从而提高空间利用率。
在mvcc机制中，当进行增删改这些操作时，都会产生一些旧版本的数据，在vacuum时会清理掉这些旧版本数据，这样数据块上就会存在很多空闲的空间。
如果不能够把这些空间再次利用起来，每次新插入数据最后一个数据块不够空间时都分配一个新的数据块，那么数据文件的膨胀速度就会非常快，因此便通过FSM来实现这一功能。

为了能够更快地查找合适的空闲空间，FSM文件不应该太大。
因此在FSM中存储的并不是实际的文件块空闲空间的大小，而是仅仅用一个字节来记录。
该字节的值用于描述对应文件块中空闲空间的范围。
以页面的1/256的粒度记录空闲空间，最大映射值是255。

为避免混淆，我们将表中的文件块称为表块，将FSM文件中的文件块称为FSM块。
对于每个表块，不论其中是否有空闲空间，在FSM文件中都能找到对应的字节。

为了实现快速查找，FSM文件中并不是简单地使用数组顺序存储每个表块的空闲空间，而是使用了树结构。
在FSM块之间使用了一个三层树的结构，第0层和第1层为辅助层，第2层FSM块中用于实际存放各表块的空闲空间值。

• 第0层: FSM块只有一个，作为树根，叶子节点从左至右顺序对应第1层FSM块的根节点。表示第1层数据块中的最大值。
• 第1层: FSM块可以有多个，作为第0层FSM块的子节点，叶子节点从左至右顺序对应第2层FSM块的根节点。表示第2层数据块中的最大值。
• 第2层: FSM块也可以有多个，作为第1层FSM块的子节点，叶子节点从左至右顺序对应表文件中的每一个表块的空闲空间值。

每个FSM块大小默认为8KB，除去必要的文件块头部信息，FSM块中剩下的空间都用来存储块内的二叉树结构，每个叶子节点用一个字节记录，因此FSM块内大约可以保存4000个叶子节点，其他空间均用作构成最大堆二叉树的辅助节点。
in reality, it holds (BLCKSZ-headers)/2, or ~4000 with default BLCKSZ
这样，一个FSM文件中总共可以记录4000^{3个叶子节点(表块)，远远大于2}32——单个表的
最大块数，这样三层的结构足以记录表文件所有文件块的空闲空间值。

例: 假如表文件有1024*1024个block(即:8G)，则需要FSM文件的block数量为:
1024 × 1024 - 4000 = 262余576，再加上第0层和第1层的fsm块，所以共需要265个block，则共需要fsm文件大小为:265 × 8KB ≈ 2.07MB，这个空间极小。

2.2 创建FSM

文件并不是在创建表文件的时候就被创建，而是推迟到需要使用FSM文件的时候，即：
执行VACUUM操作时或为了插入元组而第一次查找FSM文件时才创建。

在创建FSM文件时，会预先创建三个FSM块: 第0号为根节点即第0层的FSM 块，第1号为第1层的第一个节点，第2号为第2层的第一个节点。
当第2号FSM块满了之后，将会扩展新的FSM块，该工作主要调用函数fsm_extend进行实现。

2.3 VM

多版本并发控制(MVCC)，当事务删除或者更新元组时，并非从物理上删除，而是将其标记无效，最终再通过VACUUM命令清理这些无效元组，真正的物理删除发生在清理过程。
清理无效元组时，需要先找到无效元组，再进行清理。如果没有其他技术，需要遍历查找每一个页，找到页中的无效元组。如果更新和删除不是很频繁，表文件中大部分页都没有无效元组，如果遍历所有页，开销会非常大。
为了能加快VACUUM查找包含无效元组的文件块的过程，Vastbase为每个表文件设置了一个附属文件 -- 可见性映射表。

对于每个表文件，其对应的VM文件命名为: “关系表OID_vm”。
VM中为表的每一个文件块(Page)设置了一位，用来标记该文件块是否包含无效元组。
当表块中所有元组都对当前事务可见时，表块对应的位才被设置为1，VACUUM会忽略扫描
对应的表块，所以能大大提高VACUUM的效率。
当对某个表块中的元组进行更新或者删除后，那么该表块在VM文件中对应位置的标志位将
被置为0。

（除了提升vacuum效率外，还有一个常见场景是提升索引扫描效率）

VM文件被划分为若干个文件块(简称VM块)。
VM块中除了必要的标记信息（头信息）外，其他的每一位都对应于一个表块（或页）。每一位中0表示存在，1表示不存在。

假设该表包含三个页面，第0页和第2页包含死元组，而第1页不包含死元组。（0表示存在，1表示不存在）
表的可见性映射中保存着那些页面包含死元组的信息。
在这种情况下，清理过程可以参考VM中的信息，跳过第一个页面。

2.4 FSM及VM的应用

vacuum、索引

• 查询优化器使用可见性映射
  如果一个查询使用了索引扫描，并且目标页被标记为ALL_VISIBLE，则可以跳过 Heap Tuple
  的可见性检查(Heap Fetch)。
  这减少了 I/O 和 CPU 开销，提升查询性能。
• 支持 HOT 更新优化(Heap-Only Tuple)
  当一个页面被标记为ALL_VISIBLE，HOT更新可以在不创建新索引项的情况下进行(因为不
  需要修改索引键)。
  这有助于减少索引膨胀。

3. 索引的页面结构

3.1 索引

• 1、索引类型: Vastbase支持不同类型的索引，包括B-tree、哈希、GiST、SP-GiST、GIN和BRIN等。
  每种索引类型都有自己的适用场景和优缺点。
• 2、索引结构: 不同类型的索引采用不同的数据结构，例如B-tree采用平衡树结构，哈希采用哈希表结构，GiST和SP-GiST采用通用搜索树结构等。
  这些结构都是为了提高查询效率和节省存储空间而设计的。
• 3、索引操作: Vastbase提供了多种索引操作，包括创建索引、删除索引、修改索引、查询索引等。
  通过这些操作，可以对索引进行管理和优化，以满足不同的查询需求。
• 4、索引优化: 在实际应用中，为了提高查询效率和节省存储空间，需要对索引进行优化。Vastbase提供了多种优化方法，包括索引列的选择、索引类型的选择、多列索引的使用、索引覆盖等。
  这些方法都是为了在满足查询需求的前提下，尽可能地提高查询效率和节省存储空间。

3.2 Btree索引的页面结构

• B树是平衡有序的，每个页面与根都有相同数量的内部页面分隔开，搜索任何值都需要花费类似的时间。
• B树是多分支的，B树的深度不会太深，对于大表4-5层就够了。
• 同一级别的页面通过双向列表相互连接，可以通过列表的一个方向或另一个方向获得有序数据集，不必每次都返回到根。（通过前面提到的pd_special串联起来）
• B树适用于范围和等值查询。

【meta page】

• 1)meta page 原数据块, 指向root page的page_id
• 2)root page根块，一个页面存储，当存不下时就有leaf page,或者branch page
• 3)根，枝，叶组成了索引的高度

3.3 索引的成长

通过bt_metap()看meta page的基本信息：下图中root page是1个，0层，即一个root page就能存下例子中的100条。
通过bt_page_stat()看索引统计信息：其中1是刚才查出来的root号；可以看到item有100个，页面大小是8k，btpo是它的深度，0表示就1层，跟bt_metap()中的level是对应的，btpo_flags=3意思是即是根节点又是叶子节点。
通过bt_page_items()查看ctid（哪个页的哪个元组，以及具体数据），可通过ctid看在表里的数据（显示的info是16进制，转换后得到插入值，由此可反推数据）。

然后我们插入更多的数据（10000条）；
再看根节点已经变成了3号，level变成了1，也就是两层了；btpo即前面的level；
此时再看叶子结点，记录的已经不是一个值了，而是一个范围

我们继续插入更多的数据：
root已经变成了411号，深度已经3层；
我们查看branch信息

3.4 Vacuum对索引的影响

更新后再vacuum，信息变了；所以vacuum不仅对表有影响，对索引也有影响。

3.5 索引的分裂