B-Tree

1. B-Tree索引

1.1. 索引类型

Postgresql的B-Tree索引页分为4种类别

l meta page

存放的是索引的元数据信息（描述索引本身的信息），每个索引文件的第0页都是meta page

l root page

meta page的下一页（第一页）叫做root page，对于索引量小的情况（一页root page即可存放所有索引数据），只有一个root page即可

l branch page

用于连接root page和leaf page（不存放实际的数据，存放索引数据）

l leaf page

存放指向tuple物理位置的索引

1.2. bt_metap函数

l 简述

返回有关B树索引的元页面的信息，param1：索引名

l 字段

magic：

version：版本号

root：root页的页号（对应bt_page_stats.blkno）

level：branch page和leaf page的层数之和。表示索引的层数，level为0表示只有root page。level=1表示有一个root page和多个leaf page

fastroot：

fastlevel：

1.3. bt_page_stats函数

l 简述

返回有关B树索引的单个页面的信息，param1：索引名，param2：第几页索引（第0页存放的是meta page，不能用这个函数查看）

l 字段

blkno：block no，即索引文件的页号

type：索引类型

live_items：对于leaf page表示有效索引的数量，对于root/branch page表示子索引页的数量

dead_items：无效索引的数量，或者是无效子索引页

avg_item_size：平均字段大小

page_size：文件页的大小

free_size：空闲的大小

btpo_prev：指向同一级的当前索引页的上一页（同一级索引是双向链表）

btpo_next: 指向同一级的下一个索引页，如果没有上一页或者下一页则指向meta page

btpo:索引的层级，0表示最低级（leaf page，存放的是指向物理位置的指针）

btpo_flags:指示索引页的类型，0==branch page，1==leaf page，2==root page， 3==root page & leaf page

1.4. bt_page_items函数

l 简述

返回B树索引页上所有entry（行）的详细信息，param1：索引名，param2：页号

l 字段

itemoffset：

ctid：如果btpo==0（leaf page）,则值指向tuple的物理位置，可以使用类似select * from tab1 where ctid='(0,1)';进行查询。否则为子索引页的页号（忽略后一项），如(3,1)表示blkno=3的页为子索引页

itemlen：

data：

leaf page存放的是索引数据的值（非最右页的第一项存放的是下一索引页的最小值，最右页第一项存放的是tuple数据），

root page存放的是子索引页的最小值（第一项为空，因为最左页不存放最小值），

branch page非最右页第一项存放的是下一个索引页的最小值，第二项为空，

最右页第一项为空（因为没有下一个索引页），第二项指向第一个子索引页的最小值

1.5. 实战1-0级索引（max：407条）

l sql命令

drop table if exists tab1;

create table tab1(id int primary key, info text);

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

select * from bt_metap('tab1_pkey');

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

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

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

insert into tab1 select 408, md5(random()::text);

select * from bt_metap('tab1_pkey');

l 分析

插入407条数据，通过bt_metap函数查看主键索引（默认为btree索引），显示索引级别为0级，root页的页号为1.（当前页为meta page，是第0页，固定值）

通过bt_page_stats查看root页的统计信息，live_items表示其索引了407条数据（这里因为没有子索引页），btpo=0表示这是最底层的页，btpo_flags=3表示为root页和leaf页。

通过bt_page_items查看root页的数据内容，data为索引的值。

通过count可以看出，root页的确有407条数据，每个索引项一条数据。

再插入一条数据，查看索引级别变为了1，说明产生了leaf page。具体待1级索引实战说明。

l 索引结构分析

首先说结论，一个索引页最多存放407条int索引数据。

已知页头占用24字节，每个索引项的指针占用4字节（存放在head后面），索引数据（从末尾开始存放）占用16字节（可以通过下图的itemlen得出，data实际是int 4字节，填充了4字节，另外8字节目前分析应该是ctid，待确定），另通过page_header可以看出预留了16字节。所以，计算公式如下（实测亦如此，此处略图）：

8192-24-16=8152

8152 / (16+4) = 407 (可以存放407项)

8152 % (16+4) = 12 （页的空闲空间为12）

l 执行结果

l 理论图解

1.6. 实战-1级索引（max：149369条）

l sql命令

drop table if exists tab1;

create table tab1(id int primary key, info text);

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

select * from bt_metap('tab1_pkey');

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

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

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

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

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

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

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

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

l 分析

向表中插入1000条数据

通过bt_metap可以看出索引级别为1，root页的页号为3.

通过bt_page_stats的live_items=3可以看出root页有三个子索引页（此时root本身不在存放索引内容），通过btpo_flags=2也可以看出是root页，btpo=1表示其内存储的不是指向底层数据的指针。

通过bt_page_stats可以看出页1,2,4分别有367,367,268条数据。367+367+268=1002（多了两条？？）.

通过btpo_prev和btpo_next可以看出一级索引之间的双向连接关系如下图：

通过bt_page_items可以看出root页有3个子索引页（图上失误，使用了limit3，实际也只有三条结果）。子索引页的页号可以由ctid得到(1,1),(2,1),(4,1),可知子页页号为1,2,4（对于非叶子索引，忽略ctid的后一个字段）。data项存放的是子索引页的最小值，第一项（1号页）为空，因为最左页不保存最小值。第二页的最小值为016f=367,第四页的最小值为02dd=733=366+366+1（366为上面的live_items-1，见下面说明）。

通过bt_page_items可以看出leaf 页1的第一项存放的是页2的最小值016f，页2的第一项存放的是页4的最小值，页4的第一项存放的是正常的数据（因为没有下一页）。

所以，验证上面一个问题，总数据数量367+367+268=1002，因为前两页，分别有一条数据用来保存下一页的最小值。

l 执行结果