openGauss行存储索引机制

本文以B-Tree索引为例，介绍openGauss中行存储（格式）表的索引机制。索引本质上是对数据的一种物理有序聚簇。有序聚簇参考的排序字段被称为索引键。为了节省存储空间，一般索引表中只存储有序聚簇的索引键键值以及对应元组在主表中的物理位置。在查询指定的索引键键值元组时，得益于有序聚簇排序，可以快速找到目标元组在主表中的物理位置，然后通过访问主表对应页面和偏移得到目标元组。B-Tree索引的组织结构如图所示。

图  B-Tree索引页面间和页面内结构示意图

当前openGauss版本中，每个B-Tree的页面采用和行存储astore堆表页面基本相同的页面结构。页面间按照树形结构组织，分为根节点页面、内部节点页面和叶子节点页面。其中，根节点页面和内部节点页面中的索引元组不直接指向堆表元组，而是指向下一层的内部节点页面或叶子节点页面；叶子节点页面位于B-Tree的最底层，叶子节点页面中的索引元组指向索引键值对应的堆表元组，即存储了该元组在堆表中的物理位置（堆表页面号和页内偏移）。

B-Tree索引元组结构由索引元组头、NULL值字典和索引键值字段3分组成。

索引元组头为IndexTupleData结构体，定义代码如下所示。其中，t_tid为堆表元组的位置或下一层索引页面的位置；t_info为标志位，记录键值中是否有NULL值、是否有变长键值、索引访存方式信息以及元组长度。

typedef struct IndexTupleData {
ItemPointerData t_tid; /* 堆表元组的物理行号 */
/* ---------------
* t_info标志位内容:
*
* 第15位：是否有NULL字段
* 第14位：是否有变长字段
* 第13位: 访存方式自定义
* 第0-12位: 元组长度
* ---------------
*/
unsigned short t_info; /* 如上 */
} IndexTupleData; /* 实际索引元组数据紧跟该结构体 */

与astore堆表元组不同，索引表的NULL值字典是定长的，一个bit位对应一个索引字段。当前最多支持32个索引字段，因此该字典的长度为4个字节（如果要支持变长，那么长度加变长字典的实际空间并不会比定长的4个字节少多少）。如果索引元组头部t_info标志位中存在NULL值的bit位为0，那么该索引元组没有NULL值字典，可以节约4个字节的空间。

索引键值字段和astore堆表元组的字段结构是完全相同的，唯一区别是索引键值只保存创建索引的那些字段上的值。

为了在一个索引页面中能够保存尽可能多的元组个数，降低整个B-Tree结构的层数，索引元组和astore堆表元组的结构相比要紧凑很多，去掉了一些和astore堆表元组冗余的结构体成员。在实际执行索引查询的时候，一般需要加载（索引层数+1）个物理页面才能找到目标元组。一般索引层数在2至4层之间，因此每减少一个层级近似就可以节省20%以上的元组访存开销。

当前openGauss版本中，索引元组头部不保存t_xmin和t_xmax这两个事务信息，因此元组可见性的判断不会在遍历索引时确定，而是要等到获得叶子索引最终指向的堆表元组以后，通过结合查询快照和堆表元组的t_xmin、t_xmax信息，才能判断对应堆表元组对本查询是否可见。将导致以下几个现象：

1) 对于被删除的astore堆表元组，其空间（至少其元组指针）不能立刻被释放，否则会留下悬空的索引指针，导致后续查询出现问题。

2) 对于被更新的astore堆表元组，如果更新前后索引字段的值发生变化，那么需要插入一条新的索引元组来指向更新后的堆表元组。然而即使更新前后所有索引字段的值没有发生变化，考虑到可能还有并发的查询需要访问老元组，因此老索引元组还要保留。同时要么插入一条新索引元组来指向更新后的堆表元组。或者也可以通过将更新后元组的位置信息保存在老元组中，这样通过原来的一条索引元组，就可以一并查到更新前后的两条新、老元组了。但是这种场景下老堆表元组的清理又变得复杂起来，否则还会存在悬挂索引指针的问题。

为了解决上述这些问题，openGauss当前提供了三种空间管理和回收的机制。在对astore堆表进行轻量级清理时，无法清理索引中的垃圾数据。只有对astore进行中量级VACUUM清理，或者重量级VACUUM FULL清理时，才能够清理对应索引中的垃圾数据。

最后，上述索引可见性判断机制有一种例外场景：如果查询不涉及非索引字段，如显示查询索引字段内容、或“SELECT COUNT(*)”类查询，且索引字段t_tid指向的astore堆表页面对应的VM（visibility map，可见性位图）比特位为1，那么该索引元组被认为是可见的，这种扫描方式称为“Index Only Scan”。该扫描方式不仅提高了可见性判断的效率，更重要的是避免了对于堆表页面的访问，从而可以节省大量I/O开销。在页面空闲空间回收过程中，如果被清理的堆表页面上的所有元组对于当前所有正在执行的事务都可见，那么其对应的VM比特位会被置为1；后续如果该堆表页面上有新的插入、删除或更新操作之后，都会将其对应的VM比特位置为0。

openGauss中的行存储索引表访存接口如表所示。

表  行存储索引表访存接口

和堆表存储接口不同，由于openGauss支持多种索引结构（B-Tree，hash，GIN（generalized inverted index，通用倒排索引）等），每种索引结构内部的页面间组织方式以及扫描方式都不太相同，因此在上述接口中，没有直接定义底层的页面和元组操作，而是进一步调用了各个索引自己的访存方式。不同索引的底层访存接口，可以在pg_am系统表中查询得到。