1、背景
1.1 B树有关题外话
B树可以细分多个子类别，对比我们的数据结构课程，课里提及的一个结构容易与B树混淆。即二叉树。二叉树和B树都是平衡树，但二叉树它的每个节点里只能存储一个键值，而B树中的每个节点都存储了大量键值，因此树不会太高。
为什么经常使用B树来作为数据库的索引结构？实际上是B+树。B+树非常适用于数据库中的索引结构，它的最主要的目的就是减少磁盘lO，每个节点对应磁盘中的一个页，访问节点对应一次磁盘IO。因此我们会希望树非常扁，即树的高度非常少，因为树的高度就是访问磁盘IO的次数。
为什么使用B+树？因为B+树在节点不用存储数据或数据指针，因此每个节点里能存储的键值要比B树多，存储的键值多，B树就会变得非常扁，高度会非常低，磁盘lO就更少。因此我们选用的经常是B+树。
1.2 PostgreSQL中的B树 (实际上是B+树)
Postgresql的B-Tree索引页分为以下4种类别：
meta page
存放的是索引的元数据信息（描述索引本身的信息），每个索引文件的第0页都是meta page
root page
meta page的下一页（第一页）叫做root page，对于索引量小的情况（一页root page即可存放所有索引数据），只有一个root page即可
branch page
用于连接root page和leaf page（不存放实际的数据，存放索引数据）
leaf page
存放指向tuple物理位置的索引
meta page
->root page #btpo_flags=2
->branch page #btpo_flags=0
->leaf page #btpo_flags=1
注:如果即是leaf又是root则 btpo_flags=3
2、研究下PostgreSQL中的BTree
2.1、相关主要插件：pageinspect, pgstatuple
create extension pgstatuple;
create extension pageinspect;
postgres=# \dx+ pageinspect
Objects in extension "pageinspect"
Object description
-------------------------------------------------------------------
function bt_metap(text)
function bt_page_items(bytea)
function bt_page_items(text,bigint)
function bt_page_stats(text,bigint)
......
2.2、函数相关字段说明：
1、bt_metap函数
返回有关B树索引的元页面的信息，param1：索引名
postgres=# select * from bt_metap('test_pkey') \gx
-[ RECORD 1 ]-------------+-------
magic | 340322
version | 4 // 版本号
root | 412 // root页的页号 (与bt_page_stats.blkno相对应)
level | 2 // 有几层 (branch page和leaf page的层数之和), 0表示只有root page, 1表示有root和leaf
fastroot | 412
fastlevel | 2
last_cleanup_num_delpages | 0
last_cleanup_num_tuples | -1
allequalimage | t
2、bt_page_stats函数
返回有关B树索引的单个页面的信息，param1：索引名，param2：第几页索引（第0页存放的是meta page，不能用这个函数查看）
相关字段：
blkno：block no，即索引文件的页号
type：索引类型 (r: root, l: leaf, i: branch)
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，存放的是指向物理位置的指针）// 这个字段似乎现在没有了 (PG14)
btpo_flags:指示索引页的类型，0==branch page，1==leaf page，2==root page， 3==root page & leaf page
btpo_level: 索引的层级
3、bt_page_items函数
返回B树索引页上所有entry（行）的详细信息，param1：索引名，param2：页号
相关字段：
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 非最右页第一项存放的是下一个索引页的最小值，第二项为空，
最右页第一项为空（因为没有下一个索引页），第二项指向第一个子索引页的最小值
htid: heap tid, 指向tuple的物理位置，如果是中间层，它通常为空
tids: 该页指向的所有的tid.
nulls:
vars:
dead:
2.3、实际验证
1、准备表及数据
postgres=# create table test(id int primary key, col2 varchar(32));
CREATE TABLE
postgres=# insert into test select n, 'test' || n from generate_series(1, 300000) as n;
INSERT 0 300000
postgres=#
postgres=#
postgres=#
postgres=# select pg_total_relation_size('test');
pg_total_relation_size
------------------------
20070400
(1 row)
postgres=# vacuum verbose analyze test;
INFO: vacuuming "public.test"
INFO: table "test": found 0 removable, 115 nonremovable row versions in 1 out of 1622 pages
DETAIL: 0 dead row versions cannot be removed yet, oldest xmin: 401162
Skipped 0 pages due to buffer pins, 0 frozen pages.
CPU: user: 0.00 s, system: 0.00 s, elapsed: 0.00 s.
INFO: analyzing "public.test"
INFO: "test": scanned 1622 of 1622 pages, containing 300000 live rows and 0 dead rows; 30000 rows in sample, 300000 estimated total rows
VACUUM
2、看看index的metadata
postgres=# select bt_metap('test_pkey');
bt_metap
-------------------------------
(340322,4,412,2,412,2,0,-1,t)
(1 row)
postgres=# select * from bt_metap('test_pkey') \gx
-[ RECORD 1 ]-------------+-------
magic | 340322
version | 4
root | 412
level | 2
fastroot | 412
fastlevel | 2
last_cleanup_num_delpages | 0
last_cleanup_num_tuples | -1
allequalimage | t
root：412, level: 2意味着root页是412, 这个索引树共分为2层。或者说root页就在第2层。
3、看看root页的情况：
root页的page stats
postgres=# select * from bt_page_stats('test_pkey', 412) \gx
-[ RECORD 1 ]-+-----
blkno | 412
type | r
live_items | 3
dead_items | 0
avg_item_size | 13
page_size | 8192
free_size | 8096
btpo_prev | 0
btpo_next | 0
btpo_level | 2
btpo_flags | 2
type: r -> 表明它是root页
dead_items: 有3个索引项
btpo_level: 2，表示第2层。最高层。
接着，我们看看root页的具体数据:
postgres=# select * from bt_page_items('test_pkey', 412) ;
itemoffset | ctid | itemlen | nulls | vars | data | dead | htid | tids
------------+---------+---------+-------+------+-------------------------+------+------+------
1 | (3,0) | 8 | f | f | | | |
2 | (411,1) | 16 | f | f | 77 97 01 00 00 00 00 00 | | |
3 | (698,1) | 16 | f | f | ed 2e 03 00 00 00 00 00 | | |
(3 rows)
确实只有三条记录。第一项：(3, 0), 表示它位于第3页，第1条记录。data为空，意味着它是root页的最左节点。
我们接着它往下查找，看看第3页的索引页的stats情况：
4、下一级第3页的情况：
4.1、第3页stats
postgres=# select * from bt_page_stats('test_pkey', 3) \gx
-[ RECORD 1 ]-+-----
blkno | 3
type | i
live_items | 286
dead_items | 0
avg_item_size | 15
page_size | 8192
free_size | 2436
btpo_prev | 0
btpo_next | 411
btpo_level | 1
btpo_flags | 0
type: i 表示它是branch, live_items: 286 它存储了有286个索引项, 它的下一项指向的是第411页， 上一项指向的是第1页。
btpo_level: 1, 真正的第1层 btpo_flags: 0 表示它是branch页 （中间的索引页)
4.2、第3页具体数据
postgres=# select * from bt_page_items('test_pkey', 3) limit 10;
itemoffset | ctid | itemlen | nulls | vars | data | dead | htid | tids
------------+---------+---------+-------+------+-------------------------+------+------+------
1 | (287,1) | 16 | f | f | 77 97 01 00 00 00 00 00 | | |
2 | (1,0) | 8 | f | f | | | |
3 | (2,1) | 16 | f | f | 6f 01 00 00 00 00 00 00 | | |
4 | (4,1) | 16 | f | f | dd 02 00 00 00 00 00 00 | | |
5 | (5,1) | 16 | f | f | 4b 04 00 00 00 00 00 00 | | |
6 | (6,1) | 16 | f | f | b9 05 00 00 00 00 00 00 | | |
7 | (7,1) | 16 | f | f | 27 07 00 00 00 00 00 00 | | |
8 | (8,1) | 16 | f | f | 95 08 00 00 00 00 00 00 | | |
9 | (9,1) | 16 | f | f | 03 0a 00 00 00 00 00 00 | | |
10 | (10,1) | 16 | f | f | 71 0b 00 00 00 00 00 00 | | |
(10 rows)
postgres=# select count(*) from bt_page_items('test_pkey', 3);
count
-------
286
(1 row)
从中我们可以看到(1, 0)为第3页中的最左节点。可以继续查找下去。它是第3页的下一级。
5、下一级第1页的情况
5.1、第1页stats
postgres=# select * from bt_page_stats('test_pkey', 1) \gx
-[ RECORD 1 ]-+-----
blkno | 1
type | l
live_items | 367
dead_items | 0
avg_item_size | 16
page_size | 8192
free_size | 808
btpo_prev | 0
btpo_next | 2
btpo_level | 0
btpo_flags | 1
type: l，它是叶子节点
live_items: 367，有367条记录
btpo_prev: 上一页是第0页(那就是meta页) btpo_next: 下一页是第2页（应该是它的右侧指针)
btpo_level: 0，这也表示它是叶子节点，第0层
btpo_flags: 1, 表示它是leaf. 信息有些冗余哈
5.2、第1页具体索引数据
postgres=# select * from bt_page_items('test_pkey', 1) limit 10;
itemoffset | ctid | itemlen | nulls | vars | data | dead | htid | tids
------------+-------+---------+-------+------+-------------------------+------+-------+------
1 | (1,1) | 16 | f | f | 6f 01 00 00 00 00 00 00 | | |
2 | (0,1) | 16 | f | f | 01 00 00 00 00 00 00 00 | f | (0,1) |
3 | (0,2) | 16 | f | f | 02 00 00 00 00 00 00 00 | f | (0,2) |
4 | (0,3) | 16 | f | f | 03 00 00 00 00 00 00 00 | f | (0,3) |
5 | (0,4) | 16 | f | f | 04 00 00 00 00 00 00 00 | f | (0,4) |
6 | (0,5) | 16 | f | f | 05 00 00 00 00 00 00 00 | f | (0,5) |
7 | (0,6) | 16 | f | f | 06 00 00 00 00 00 00 00 | f | (0,6) |
8 | (0,7) | 16 | f | f | 07 00 00 00 00 00 00 00 | f | (0,7) |
9 | (0,8) | 16 | f | f | 08 00 00 00 00 00 00 00 | f | (0,8) |
10 | (0,9) | 16 | f | f | 09 00 00 00 00 00 00 00 | f | (0,9) |
(10 rows)
postgres=# select count(*) from bt_page_items('test_pkey', 1);
count
-------
367
(1 row)
我们来看(1, 1) 最左侧的叶子节点，htid, tids都是空的，就是一个索引节点。真正的数据在后边。(0, 1), (0, 2), ……这些是真正的数据。data部分存储的就是指向数据元组的ctid值。
postgres=# select ctid, * from test limit 5;
ctid | id | col2
-------+----+-------
(0,1) | 1 | test1
(0,2) | 2 | test2
(0,3) | 3 | test3
(0,4) | 4 | test4
(0,5) | 5 | test5
(5 rows)
参考：
F.25.3. B-Tree Functions in F.25. pageinspect of Appendix F. Additional Supplied Modules (https://www.postgresql.org/docs/15/pageinspect.html)
要懂Greenplum索引，心里得有B树 (https://cn.greenplum.org/b-tree/)
b-tree的索引页总览
(https://blog.csdn.net/shipeng1022/article/details/118692139)Postgresql的B-Tree索引页
(https://www.cnblogs.com/gc65/p/11011916.html)
