海山数据库(He3DB)源码详解：海山PG 表和元组的组织方式（1）

一、概述

PostgreSQL是一种开源的关系型数据库管理系统，具有强大的功能和可靠性。在PostgreSQL数据库中，表和元组是数据组织的基础单元。其中，表是PG数据库中存储数据的逻辑结构，由多个列（Column）和行（Row）组成。列代表了数据字段，而行则代表了一条条的数据记录。每个表都有其独特的属性，如主键（Primary Key）、外键（Foreign Key）、索引（Index）等。主键用于唯一标识表中的一条记录，外键用于建立表与表之间的关联，索引则用于提高查询效率。在PostgreSQL中，元组通常指的是表中的一行数据，即一条记录。元组包含了该记录在表中所有字段的值，这些字段值对应于表中的列。每个字段值都有其特定的数据类型，如整数、浮点数、字符串等。在物理存储上，元组被存储在表文件的页（Page）中。每个页包含了多个元组，并且这些元组按照创建顺序或特定的存储策略被组织在一起。
在PostgreSQL中，一个表中的元组按照创建顺序依次插入到表文件中。这样的表文件即堆文件，按照功能可分为四类。而其中的元组数据信息主要通过设计的元组头部信息来进行多版本并发控制、数据可见性判断等操作。

二、表和元组的组织方式

PostgreSQL中的表和元组通过特定的组织方式来提高存储效率和查询性能。

1、堆文件组织：

• PostgreSQL使用堆文件（Heap File）来存储表数据。堆文件是一种无序的数据存储结构，其中的元组按照创建顺序或VACUUM操作后的空闲空间顺序被插入。
• 堆文件由多个页组成，每个页包含了多个元组。页的大小通常是固定的（如8KB），并且页内元组的存储顺序是连续的。
  为了管理页内的空闲空间，PostgreSQL为每个页维护了一个页头（Page Header），其中包含了关于页的一般信息，如空闲空间指针、特殊空间指针等。

2、行指针和索引：

• 在堆文件中，每个元组都通过行指针（Item Pointer）来定位。行指针包含了元组在页内的偏移量和长度信息，使得系统能够快速找到并访问元组。
• 为了提高查询效率，PostgreSQL还支持索引机制。索引是一种特殊的数据结构，用于存储表中元组的键值对，并允许系统根据键值快速定位元组。

3、存储管理：

• PostgreSQL的存储管理由SMGR（Storage Manager）提供统一接口。SMGR负责处理表的物理存储，包括文件的创建、读取、写入和删除等操作。
• 为了优化存储性能，PostgreSQL还采用了空闲空间映射表（FSM）和可见性文件映射表（VM）等机制来管理页内的空闲空间和元组的可见性。

4、特殊堆文件：

• 除了普通的堆文件外，PostgreSQL还支持其他类型的堆文件，如临时堆、序列堆和TOAST表等。这些特殊堆文件在功能和用途上有所不同，但底层文件结构却与普通堆文件相似。

三、数据结构设计

1、页面头部——HeapTupleHeaderData

Page头定义在PageHeaderData结构体中，需要注意的是结构体尾部的行指针数组是一个0长度数组，又称为柔性数组（flexible array），不占用结构体大小。

typedef struct PageHeaderData
{
    PageXLogRecPtr pd_lsn;      // Page最后一次被修改对应的xlog的标识
    uint16      pd_checksum;    // 校验和
    uint16      pd_flags;       // 标记位
    LocationIndex pd_lower;     // 空闲空间开始位置
    LocationIndex pd_upper;     // 空闲空间结束位置
    LocationIndex pd_special;   // 特殊空间开始位置
    uint16      pd_pagesize_version; // 页面大小和版本号
    TransactionId pd_prune_xid; // Page中可以修剪的最老元组的XID
    ItemIdData  pd_linp[FLEXIBLE_ARRAY_MEMBER]; // 行指针数组
} PageHeaderData;

typedef PageHeaderData *PageHeader;
复制

pd_flags有以下几种情况：

#define PD_HAS_FREE_LINES   0x0001  // 是否有空闲的数据指针
#define PD_PAGE_FULL        0x0002  // 是否有空闲空间可供插入新的元组
#define PD_ALL_VISIBLE      0x0004  // 页内所有元组对所有人都可见

#define PD_VALID_FLAG_BITS  0x0007  // 以上所有有效标志位
复制

2、行指针——ItemIdData

行指针结构体内保存着Page中元组的位置和长度，通过一个行指针可以在Page中拿到相应的元组。

typedef struct ItemIdData
{
    unsigned    lp_off:15,      // 元组的偏移量
                lp_flags:2,     // 行指针状态
                lp_len:15;      // 元组的长度
} ItemIdData;

typedef ItemIdData *ItemId;
复制

其中lp_flags有以下四种取值：

#define LP_UNUSED       0       // 空闲行指针
#define LP_NORMAL       1       // 行指针被使用，指向一个元组
#define LP_REDIRECT     2       // HOT技术标识
#define LP_DEAD         3       // 行指针对应的元组为死元组
复制

3、数据指针——ItemPointerData

对于一个元组，我们只需要知道它在文件中的页号和页内偏移量，就可以访问元组的数据。元组的全局数据指针定义在ItemPointerData结构体中：

typedef struct ItemPointerData
{
    BlockIdData ip_blkid;   // 文件内的块号
    OffsetNumber ip_posid;  // 页内行指针偏移量
}
复制

4、堆元组头数据——HeapTupleHeaderData

HeapTupleHeaderData是PostgreSQL中用于组织元组信息的关键数据结构。通过存储元组的基本信息、支持MVCC机制、关联物理存储与逻辑表示、实现元组的版本控制以及优化查询性能等方面的功能，

struct HeapTupleHeaderData
{
	union
	{
		HeapTupleFields t_heap;    
		DatumTupleFields t_datum;   
	}t_choice;                     
	ItemPointerData t_ctid;
	int16		t_natts;	
	uint16		t_infomask2;	
	uint16		t_infomask;		
	uint8		t_hoff;	
	bits8		t_bits[FLEXIBLE_ARRAY_MEMBER];
};
复制

其中，每个字段的含义如下：
t_choice： 是具有两个成员的联合类型：
t_heap：用于记录对元组执行插入/删除操作的事务ID和命令ID，这些信息主要用于并发控制时检查元组对事务的可见性。
t_datum：当一个新元组在内存中形成的时候，我们并不关心其事务可见性，因此在t_choice中只需用DatumTupleFields 结构来记录元组的长度等信息。但在把该元组插入到表文件时，需要在元组头信息中记录插入该元组的事务和命令ID，故此时会把t_choice所占用的内存转换为HeapTupleFields结构并填充相应数据后再进行元组的插入。
t_ctid：用于记录当前元组或者新元组的物理位置（块内偏移量和元组长度），若元组被更新（He3DB对元组的更新采用的是标记删除旧版本元组并插入新版本元组的方式），则记录的是新版本元组的物理位置。
t_infomask2：使用其低11位表示当前元组的属性个数，其他位则用于包括用于HOT技术及元组可见性的标志位。
t_infomask：用于标识元组当前的状态，比如元组是否具有OID、是否有空属性等;
t_infomask：该字段的每一位对应不同的状态，共16种状态。
t_hoff：表示该元组头的大小。
t_bits[]：数组用于标识该元组哪些字段为空。