一、B-tree索引的结构
在PostgreSQL中，B-tree索引的结构包括几种类型的页面：meta page、root page、branch page和leaf page。
1. Meta Page：Meta page是B-tree索引的元数据页面，它包含了关于索引的一些元信息，例如根页面的位置、最后一次vacuum的位置等。每个B-tree索引都有一个meta page。
2. Root Page：Root page是B-tree索引的顶层页面。在一个空的或者只有少量数据的B-tree索引中，root page可能同时也是leaf page。随着数据的增加，root page可能会变成branch page，它的主要作用是指向其他的branch page或leaf page。
3. branch Page：branch page位于B-tree索引的中间层级，它包含了指向其他branch page或leaf page的指针。
4. Leaf Page：Leaf page是B-tree索引的底层页面，它包含了实际的索引条目，即指向表中行的指针。
二、实验研究
2.1 扩建扩展
--使用pageinspect查看块结构
create extension pageinspect;2.2 准备数据
drop table t1;
create table t1(a int primary key, b varchar(255));
insert into t1 select generate_series(1,10), md5(random()::varchar);
vacuum analyze t1;
--t1的主键索引名为t1_pkey
postgres=#
Table "public.t1"
Column | Type | Collation | Nullable | Default
--------+------------------------+-----------+----------+---------
a | integer | | not null |
b | character varying(255) | | |
Indexes:
"t1_pkey" PRIMARY KEY, btree (a)2.3 btree索引第一层构架
1）查看meta块--bt_metap
postgres=# select * from bt_metap('t1_pkey');
-[ RECORD 1 ]-------------+-------
magic | 340322
version | 4
root | 1
level | 0
fastroot | 1
fastlevel | 0
last_cleanup_num_delpages | 0
last_cleanup_num_tuples | -1
allequalimage | t此时level为0即高度为1，root块为1。
2）查看root page--bt_page_stats
postgres=# select * from bt_page_stats('t1_pkey',1);
-[ RECORD 1 ]-+-----
blkno | 1
type | l
live_items | 10
dead_items | 0
avg_item_size | 16
page_size | 8192
free_size | 7948
btpo_prev | 0
btpo_next | 0
btpo_level | 0
btpo_flags | 3参数解释
ive_items:存活的索引行
dead_items：死亡的索引行
avg_item_size:平均索引行大小
page_size:块大小
free_size：块空余大小
btpo_prev：块前
btpo_next：块后
btpo_level ：当前块层次，0表示最低层
btpo_flags：当前块类型，3代表：它既是leaf又是root，即2+1
root page :btpo flags=2
branch page :btpo flags=0
leaf page :btpo flags=13）查看指定索引块内容--bt_page_items
postgres=# select * from bt_page_items('t1_pkey',1);
itemoffset | ctid | itemlen | nulls | vars | data | dead | htid | tids
------------+--------+---------+-------+------+-------------------------+------+--------+------
1 | (0,1) | 16 | f | f | 01 00 00 00 00 00 00 00 | f | (0,1) |
2 | (0,2) | 16 | f | f | 02 00 00 00 00 00 00 00 | f | (0,2) |
3 | (0,3) | 16 | f | f | 03 00 00 00 00 00 00 00 | f | (0,3) |
4 | (0,4) | 16 | f | f | 04 00 00 00 00 00 00 00 | f | (0,4) |
5 | (0,5) | 16 | f | f | 05 00 00 00 00 00 00 00 | f | (0,5) |
6 | (0,6) | 16 | f | f | 06 00 00 00 00 00 00 00 | f | (0,6) |
7 | (0,7) | 16 | f | f | 07 00 00 00 00 00 00 00 | f | (0,7) |
8 | (0,8) | 16 | f | f | 08 00 00 00 00 00 00 00 | f | (0,8) |
9 | (0,9) | 16 | f | f | 09 00 00 00 00 00 00 00 | f | (0,9) |
10 | (0,10) | 16 | f | f | 0a 00 00 00 00 00 00 00 | f | (0,10) |
(10 rows)
Time: 0.562 m我们从官网资料可以得知，索引里存的是行的rowid和对应的索引列值。上面的查询就可以验证这一点
postgres=# select * from t1 where ctid='(0,1)';
a | b
---+----------------------------------
1 | 95e4e27cb3ddfbf7a9f131f1235ae8a5
(1 row)2.3 btree索引第二层构架
模拟更多的数据插入，增加索引块
postgres=# insert into t1 select generate_series(11,1000), md5(random()::varchar);
INSERT 0 9901）查看meta块--bt_metap
postgres=# select * from bt_metap('t1_pkey');
-[ RECORD 1 ]-------------+-------
magic | 340322
version | 4
root | 3
level | 1
fastroot | 3
fastlevel | 1
last_cleanup_num_delpages | 0
last_cleanup_num_tuples | -1
allequalimage | t索引高度由0变成1，同时root块发生了变化，由blk1变成blk3。
2）查看root page--bt_page_stats
postgres=# select * from bt_page_stats('t1_pkey',3);
-[ RECORD 1 ]-+-----
blkno | 3
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 | 1
btpo_flags | 2可以看出来，此时root块既是root块，也是leaf块
3）查看指定索引块内容--bt_page_items
postgres=# select * from bt_page_items('t1_pkey',3);
itemoffset | ctid | itemlen | nulls | vars | data | dead | htid | tids
------------+-------+---------+-------+------+-------------------------+------+------+------
1 | (1,0) | 8 | f | f | | | |
2 | (2,1) | 16 | f | f | 6f 01 00 00 00 00 00 00 | | |
3 | (4,1) | 16 | f | f | dd 02 00 00 00 00 00 00 | | |
(3 rows)4）查看leaf块中的数据
postgres=# select count(1) from bt_page_items('t1_pkey',1);
count
-------
367
(1 row)
postgres=# select count(1) from bt_page_items('t1_pkey',2);
count
-------
367
(1 row)
postgres=# select count(1) from bt_page_items('t1_pkey',4);
count
-------
268
(1 row)
--leaf块中的明细
postgres=# select * from bt_page_items('t1_pkey',1);
itemoffset | ctid | itemlen | nulls | vars | data | dead | htid | tids
------------+---------+---------+-------+------+-------------------------+------+---------+------
1 | (3,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) |
11 | (0,10) | 16 | f | f | 0a 00 00 00 00 00 00 00 | f | (0,10) |
12 | (0,13) | 16 | f | f | 0b 00 00 00 00 00 00 00 | f | (0,13) |
13 | (0,14) | 16 | f | f | 0c 00 00 00 00 00 00 00 | f | (0,14) |
14 | (0,15) | 16 | f | f | 0d 00 00 00 00 00 00 00 | f | (0,15) |
15 | (0,16) | 16 | f | f | 0e 00 00 00 00 00 00 00 | f | (0,16) |
16 | (0,17) | 16 | f | f | 0f 00 00 00 00 00 00 00 | f | (0,17) |
17 | (0,18) | 16 | f | f | 10 00 00 00 00 00 00 00 | f | (0,18) |
18 | (0,19) | 16 | f | f | 11 00 00 00 00 00 00 00 | f | (0,19) |
19 | (0,20) | 16 | f | f | 12 00 00 00 00 00 00 00 | f | (0,20) |
20 | (0,21) | 16 | f | f | 13 00 00 00 00 00 00 00 | f | (0,21) |
21 | (0,22) | 16 | f | f | 14 00 00 00 00 00 00 00 | f | (0,22) |
22 | (0,23) | 16 | f | f | 15 00 00 00 00 00 00 00 | f | (0,23) |
Cancel request sent
Time: 1.495 ms
postgres=# select * from bt_page_items('t1_pkey',2);
itemoffset | ctid | itemlen | nulls | vars | data | dead | htid | tids
------------+---------+---------+-------+------+-------------------------+------+---------+------
1 | (6,1) | 16 | f | f | dd 02 00 00 00 00 00 00 | | |
2 | (3,9) | 16 | f | f | 6f 01 00 00 00 00 00 00 | f | (3,9) |
3 | (3,10) | 16 | f | f | 70 01 00 00 00 00 00 00 | f | (3,10) |
4 | (3,11) | 16 | f | f | 71 01 00 00 00 00 00 00 | f | (3,11) |
5 | (3,12) | 16 | f | f | 72 01 00 00 00 00 00 00 | f | (3,12) |
6 | (3,13) | 16 | f | f | 73 01 00 00 00 00 00 00 | f | (3,13) |
7 | (3,14) | 16 | f | f | 74 01 00 00 00 00 00 00 | f | (3,14) |
8 | (3,15) | 16 | f | f | 75 01 00 00 00 00 00 00 | f | (3,15) |
9 | (3,16) | 16 | f | f | 76 01 00 00 00 00 00 00 | f | (3,16) |
10 | (3,17) | 16 | f | f | 77 01 00 00 00 00 00 00 | f | (3,17) |
11 | (3,18) | 16 | f | f | 78 01 00 00 00 00 00 00 | f | (3,18) |
12 | (3,19) | 16 | f | f | 79 01 00 00 00 00 00 00 | f | (3,19) |
13 | (3,20) | 16 | f | f | 7a 01 00 00 00 00 00 00 | f | (3,20) |
14 | (3,21) | 16 | f | f | 7b 01 00 00 00 00 00 00 | f | (3,21) |
15 | (3,22) | 16 | f | f | 7c 01 00 00 00 00 00 00 | f | (3,22) |
16 | (3,23) | 16 | f | f | 7d 01 00 00 00 00 00 00 | f | (3,23) |
17 | (3,24) | 16 | f | f | 7e 01 00 00 00 00 00 00 | f | (3,24) |
18 | (3,25) | 16 | f | f | 7f 01 00 00 00 00 00 00 | f | (3,25) |
19 | (3,26) | 16 | f | f | 80 01 00 00 00 00 00 00 | f | (3,26) |
20 | (3,27) | 16 | f | f | 81 01 00 00 00 00 00 00 | f | (3,27) |
21 | (3,28) | 16 | f | f | 82 01 00 00 00 00 00 00 | f | (3,28) |
22 | (3,29) | 16 | f | f | 83 01 00 00 00 00 00 00 | f | (3,29) |
Cancel request sent
Time: 1.082 ms
postgres=# select * from bt_page_items('t1_pkey',4);
itemoffset | ctid | itemlen | nulls | vars | data | dead | htid | tids
------------+---------+---------+-------+------+-------------------------+------+---------+------
1 | (6,15) | 16 | f | f | dd 02 00 00 00 00 00 00 | f | (6,15) |
2 | (6,16) | 16 | f | f | de 02 00 00 00 00 00 00 | f | (6,16) |
3 | (6,17) | 16 | f | f | df 02 00 00 00 00 00 00 | f | (6,17) |
4 | (6,18) | 16 | f | f | e0 02 00 00 00 00 00 00 | f | (6,18) |
5 | (6,19) | 16 | f | f | e1 02 00 00 00 00 00 00 | f | (6,19) |
6 | (6,20) | 16 | f | f | e2 02 00 00 00 00 00 00 | f | (6,20) |
7 | (6,21) | 16 | f | f | e3 02 00 00 00 00 00 00 | f | (6,21) |
8 | (6,22) | 16 | f | f | e4 02 00 00 00 00 00 00 | f | (6,22) |
9 | (6,23) | 16 | f | f | e5 02 00 00 00 00 00 00 | f | (6,23) |
10 | (6,24) | 16 | f | f | e6 02 00 00 00 00 00 00 | f | (6,24) |
11 | (6,25) | 16 | f | f | e7 02 00 00 00 00 00 00 | f | (6,25) |
12 | (6,26) | 16 | f | f | e8 02 00 00 00 00 00 00 | f | (6,26) |
13 | (6,27) | 16 | f | f | e9 02 00 00 00 00 00 00 | f | (6,27) |
14 | (6,28) | 16 | f | f | ea 02 00 00 00 00 00 00 | f | (6,28) |
15 | (6,29) | 16 | f | f | eb 02 00 00 00 00 00 00 | f | (6,29) |
16 | (6,30) | 16 | f | f | ec 02 00 00 00 00 00 00 | f | (6,30) |
17 | (6,31) | 16 | f | f | ed 02 00 00 00 00 00 00 | f | (6,31) |
18 | (6,32) | 16 | f | f | ee 02 00 00 00 00 00 00 | f | (6,32) |
19 | (6,33) | 16 | f | f | ef 02 00 00 00 00 00 00 | f | (6,33) |
20 | (6,34) | 16 | f | f | f0 02 00 00 00 00 00 00 | f | (6,34) |
21 | (6,35) | 16 | f | f | f1 02 00 00 00 00 00 00 | f | (6,35) |
22 | (6,36) | 16 | f | f | f2 02 00 00 00 00 00 00 | f | (6,36) |
Cancel request sent
Time: 0.866 ms2.4 btree索引第三层构架
模拟更多的数据插入，增加索引块
postgres=# insert into t1 select generate_series(11111,1000000), md5(random()::varchar);
INSERT 0 9888901）查看meta块--bt_metap
postgres=# select * from bt_metap('t1_pkey');
-[ 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 | troot块再次发生变化， 同时索引level也变成3层(level2+1),此时根枝叶块全部生成。
2）查看root page--bt_page_stats
postgres=# select * from bt_page_stats('t1_pkey',412);
-[ RECORD 1 ]-+-----
blkno | 412
type | r
live_items | 10
dead_items | 0
avg_item_size | 15
page_size | 8192
free_size | 7956
btpo_prev | 0
btpo_next | 0
btpo_level | 2
btpo_flags | 2btpo_flags=2 表示该块是root块
3）查看指定索引块内容--bt_page_items
postgres=# select * from bt_page_items('t1_pkey',412);
itemoffset | ctid | itemlen | nulls | vars | data | dead | htid | tids
------------+----------+---------+-------+------+-------------------------+------+------+------
1 | (3,0) | 8 | f | f | | | |
2 | (411,1) | 16 | f | f | cd 9b 01 00 00 00 00 00 | | |
3 | (698,1) | 16 | f | f | 43 33 03 00 00 00 00 00 | | |
4 | (984,1) | 16 | f | f | b9 ca 04 00 00 00 00 00 | | |
5 | (1270,1) | 16 | f | f | 2f 62 06 00 00 00 00 00 | | |
6 | (1556,1) | 16 | f | f | a5 f9 07 00 00 00 00 00 | | |
7 | (1842,1) | 16 | f | f | 1b 91 09 00 00 00 00 00 | | |
8 | (2128,1) | 16 | f | f | 91 28 0b 00 00 00 00 00 | | |
9 | (2414,1) | 16 | f | f | 07 c0 0c 00 00 00 00 00 | | |
10 | (2700,1) | 16 | f | f | 7d 57 0e 00 00 00 00 00 | | |
(10 rows)可以看到，root块链接的branch块明显增加
4）查看branch块中status的信息
postgres=# select * from bt_page_stats('t1_pkey',411);
-[ RECORD 1 ]-+-----
blkno | 411
type | i
live_items | 286
dead_items | 0
avg_item_size | 15
page_size | 8192
free_size | 2436
btpo_prev | 3
btpo_next | 698
btpo_level | 1
btpo_flags | 0
postgres=# select * from bt_page_stats('t1_pkey',2700);
-[ RECORD 1 ]-+-----
blkno | 2700
type | i
live_items | 165
dead_items | 0
avg_item_size | 15
page_size | 8192
free_size | 4856
btpo_prev | 2414
btpo_next | 0
btpo_level | 1
btpo_flags | 05）查看branch块中item的信息
postgres=# select count(1) from bt_page_items('t1_pkey',411);
count
-------
286
(1 row)
postgres=# select * from bt_page_items('t1_pkey',411);
itemoffset | ctid | itemlen | nulls | vars | data | dead | htid | tids
------------+---------+---------+-------+------+-------------------------+------+------+------
1 | (574,1) | 16 | f | f | 6b 56 03 00 00 00 00 00 | | |
2 | (287,0) | 8 | f | f | | | |
3 | (288,1) | 16 | f | f | 63 c0 01 00 00 00 00 00 | | |
4 | (289,1) | 16 | f | f | d1 c1 01 00 00 00 00 00 | | |
5 | (290,1) | 16 | f | f | 3f c3 01 00 00 00 00 00 | | |
6 | (291,1) | 16 | f | f | ad c4 01 00 00 00 00 00 | | |
7 | (292,1) | 16 | f | f | 1b c6 01 00 00 00 00 00 | | |
8 | (293,1) | 16 | f | f | 89 c7 01 00 00 00 00 00 | | |
9 | (294,1) | 16 | f | f | f7 c8 01 00 00 00 00 00 | | |
10 | (295,1) | 16 | f | f | 65 ca 01 00 00 00 00 00 | | |
11 | (296,1) | 16 | f | f | d3 cb 01 00 00 00 00 00 | | |
12 | (297,1) | 16 | f | f | 41 cd 01 00 00 00 00 00 | | |
13 | (298,1) | 16 | f | f | af ce 01 00 00 00 00 00 | | |
14 | (299,1) | 16 | f | f | 1d d0 01 00 00 00 00 00 | | |
15 | (300,1) | 16 | f | f | 8b d1 01 00 00 00 00 00 | | |
16 | (301,1) | 16 | f | f | f9 d2 01 00 00 00 00 00 | | |
17 | (302,1) | 16 | f | f | 67 d4 01 00 00 00 00 00 | | |
18 | (303,1) | 16 | f | f | d5 d5 01 00 00 00 00 00 | | |三、总结
通过上面的实验，对比下图索引结构，我们对pg数据库中的索引有了初步了解，对后续学习索引优化有大的帮助。
另外需要配套pg数据库索引学习视频的同学，可以添加联系方式：（同V） 陈老师 199-4146-4235 / 郑老师 199-0663-2509 / 蕾老师199-0663-5786，我们会持续更新学习视频。
文章转载自云贝教育，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
