1.结构与特性

1.基本结构

1. linp代表行指针，指向对应的索引元组
2. itup代表有序的索引元组
3. special space存放了 BTPageOpaqueData，存放了当前页面对应节点对应的左右兄弟节点以及相关信息

typedef struct BTPageOpaqueData
{
	BlockNumber btpo_prev;		/* 上一页 */
	BlockNumber btpo_next;		/* 下一页 */
	union
	{
		uint32		level;		/* 页面在索引树中的层次 --- zero for leaf pages */
		TransactionId xact;		/*删除页面的事务id,用于判断该页面是否可以被重新分配使用 */
	}			btpo;
	uint16		btpo_flags;		/* 页面类型 */
	BTCycleId	btpo_cycleid;	/* vacuum cycle ID of latest split */
} BTPageOpaqueData;

typedef BTPageOpaqueData *BTPageOpaque;

/* Bits defined in btpo_flags */
#define BTP_LEAF		(1 << 0)	/* leaf page, i.e. not internal page */
#define BTP_ROOT		(1 << 1)	/* root page (has no parent) */
#define BTP_DELETED		(1 << 2)	/* page has been deleted from tree */
#define BTP_META		(1 << 3)	/* meta-page */
#define BTP_HALF_DEAD	(1 << 4)	/* empty, but still in tree */
#define BTP_SPLIT_END	(1 << 5)	/* rightmost page of split group */
#define BTP_HAS_GARBAGE (1 << 6)	/* page has LP_DEAD tuples */
#define BTP_INCOMPLETE_SPLIT (1 << 7)	/* right sibling's downlink is missing */

每个b-tree索引都有一个meta， 它始终位于b-tree的第0页

typedef struct BTMetaPageData
{
	uint32		btm_magic;		/* 用于完整性检查和辅助调试，确定该结构确实是b-tree的元页 */
	uint32		btm_version;	/* 版本号信息*/
	BlockNumber btm_root;		/* 根节点对应块号*/
	uint32		btm_level;		/* 根节点在树中的层次*/
	BlockNumber btm_fastroot;	/* current "fast" root location */
	uint32		btm_fastlevel;	/* tree level of the "fast" root page */
} BTMetaPageData;

fastroot是有效的根节点，大量删除操作可能导致根节点下面出现单节点层，此时可标记最底层的单节点层为 fastroot，后续对索引的操作可以从 fastroot开始，从而提高效率。

//索引元组由IndexTupleData表示
typedef struct IndexTupleData
{
	ItemPointerData t_tid;		/* 索引元组执指向的表元组id(blockno+offset)*/

	/* ---------------
	 * t_info is laid out in the following fashion:
	 *
	 * 15th (high) bit: has nulls
	 * 14th bit: has var-width attributes
	 * 13th bit: AM-defined meaning
	 * 12-0 bit: size of tuple
	 * ---------------
	 */

	unsigned short t_info;		/* various info about tuple */
	//紧接着存储的就是data
} IndexTupleData;				/* MORE DATA FOLLOWS AT END OF STRUCT */

typedef IndexTupleData *IndexTuple;

2.与b+tree的区别

1.前置知识

1. right link:所有相邻节点都使用双向链表连接（用于发生分裂时找到正确的节点）
2. high key:当前节点所能存放key的最大值，通常是相邻右节点的最小值(用于判断是否发生分裂)
   

分裂的两个阶段：

1.水平操作：将原节点n分成n和n'，将key也分成两拨，同时节点n指向节点n'

1. 获取分裂点。
2. 创建一个新的节点。
3. 将原始节点中一半的数据迁移到新节点中。
4. 修改原始节点的high key。
5. 将新节点加入链表。

2.垂直操作：将新的节点n'的min key和节点编号写入父节点。
在1和2之间允许其他进程从父节点进行搜索，进入节点n，如果：

1. 目标key在节点n中，则搜索n后返回；
2. 目标key在n'中，通过节点n跳到n'中搜索；

2.并发查找过程

假设现在有一个查询操作需要获取44，在查询时B+树的结构如下图所示，这是一个分裂的中间状态，即block1已经发生了分裂，但还没有来得及将节点的min key和blockno写入父节点。

1. 查询进程先对block3加共享锁，然后从block3得知，44应该在block1中；
2. 释放block3上的共享锁，尝试锁定block1；
3. 插入进程对block3加互斥锁，然后完成分裂；
4. 查询进程获取block1的共享锁，block1的high key为38 < 44，说明发生分裂；
5. 向右遍历节点，直到找到一个high key > 44的节点

2.使用 pageinspect工具查看索引结构

create extension pageinspect；
#查看meta块
select * from bt_metap('tab1_pkey');
#查看root page的stats
select * from bt_page_stats('tab1_pkey',1);
#查看root(leaf)页里面的内容：
select * from bt_page_items('tab1_pkey',1);
#根据ctid来访问表：
select * from tab1 where ctid='(0,1)';

1.0层结构

create table tab1(id int primary key, info text);     
insert into tab1 select generate_series(1,100), md5(random()::text);

1.查看meta page

select * from bt_metap('tab1_pkey');

在CN节点无法找到 root页面：

要去 DN节点查询：

得到的信息：

• root页面的 blockno为1；
• level = 0说明 root节点就是叶子节点

2.查看root page

select * from bt_page_stats('tab1_pkey',1);

得到的信息：

• btpo = 0说明是最底层页面
• btpo_flags = 3说明既是root页面也是leaf页面

3.查看root page item

select * from bt_page_items('tab1_pkey',1);

得到的信息：

• 叶子节点的index item中的ctid指向实际存储的数据
• data存储key值

select * from tab1 where ctid='(0,10)';

2.1层结构

truncate tab1;  
insert into tab1 select generate_series(1,1000), md5(random()::text);

1.查看meta page

select * from bt_metap('tab1_pkey');

2.查看root page相关信息

1.root page

select * from bt_page_stats('tab1_pkey',3);

2.root page items

select * from bt_page_items('tab1_pkey',3);

得到的信息：

• 第一条data为空，但是ctid会指向最左leaf，所有非叶子节点的第一条有效数据的data都为空
• 其他 items存储的是指向页面的最小值，对比bt_page_items得到的item最小值发现和data相同

3.查看 leaf page相关信息

1.leaf page

select * from bt_page_stats('tab1_pkey',1);  
select * from bt_page_stats('tab1_pkey',2);  
select * from bt_page_stats('tab1_pkey',4);

2.leaf page items

select * from bt_page_items('tab1_pkey',1);  
select * from bt_page_items('tab1_pkey',2);  
select * from bt_page_items('tab1_pkey',4);

得到的信息：

• 非最左叶子页面的首项存放 highkey
• key值按序存放

3.2层结构

create table tab2(id int primary key, info text);  
insert into tab2 select trunc(random()*10000000), md5(random()::text) from generate_series(1,1000000) on conflict on constraint tab2_pkey do nothing;

1.查看meta page

select * from bt_metap('tab2_pkey');

2.查看root page相关信息

1.root page

select * from bt_page_stats('tab2_pkey',411);

2.root items

select * from bt_page_items('tab2_pkey',411);

3.查看branch page相关信息

1.branch page

select * from bt_page_stats('tab2_pkey',3); 
select * from bt_page_stats('tab2_pkey',2738); 
select * from bt_page_stats('tab2_pkey',1344);

2.branch page items

select * from bt_page_items('tab2_pkey',3); 
select * from bt_page_items('tab2_pkey',2738); 
select * from bt_page_items('tab2_pkey',1344);

blk3对应最左 branch page，可以看到 item1存储的是 highkey，item2存储的是最左叶子节点的 ctid，data为空

• 非最右节点的item1存储highkey
• 非叶子节点的的第一个有效item的data为空

4.查看leaf page相关信息

1.leaf page

select * from bt_page_stats('tab2_pkey',1); 
select * from bt_page_stats('tab2_pkey',3034); 
select * from bt_page_stats('tab2_pkey',1330);

2.leaf page items

select * from bt_page_items('tab2_pkey',1); 
select * from bt_page_items('tab2_pkey',3034); 
select * from bt_page_items('tab2_pkey',1330);

4.多层结构

5.总结

1. 除meta页面外，所有类型页面的结构相同；
2. 除meta页面外，所有类型页面的非最右页面的linp0指向highkey(右边页面的最小值)（每层最右节点的highkey应该是无穷大，所以无需表示）
3. 除meta页面外，所有非叶子页面的第一个有效item的data都为空
4. 内部节点：其index-tuple 保存的是下级节点的min key 以及指向子节点的指针
5. 叶子节点：其内部的 index-tuple 保存的是key 以及 指向 数据tuple的 tid