共计 7737 个字符，预计需要花费 20 分钟才能阅读完成。
这篇文章主要讲解了“PostgreSQL 数据库 B -Tree 索引的物理存储结构是怎样的”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着丸趣 TV 小编的思路慢慢深入，一起来研究和学习“PostgreSQL 数据库 B -Tree 索引的物理存储结构是怎样的”吧！
一、测试数据
我们继续使用上一节使用的测试数据，这一次我们追加插入 1000 行的数据。
-- 为方便对比，插入数据前先查看索引元数据页
testdb=# select * from bt_metap( pk_t_index
magic | version | root | level | fastroot | fastlevel | oldest_xact | last_cleanup_num_tuples
--------+---------+------+-------+----------+-----------+-------------+-------------------------
340322 | 3 | 1 | 0 | 1 | 0 | 0 | -1
(1 row)
testdb=# do $$
testdb$# begin
testdb$# for i in 19..1020 loop
testdb$# insert into t_index (id, c1, c2) values (i, # ||i|| # , # ||i|| #
testdb$# end loop;
testdb$# end $$;
testdb=# select count(*) from t_index;
count
-------
1008
(1 row)二、索引存储结构
插入数据后，重新查看索引元数据页信息：
testdb=# select * from bt_metap( pk_t_index
magic | version | root | level | fastroot | fastlevel | oldest_xact | last_cleanup_num_tuples
--------+---------+------+-------+----------+-----------+-------------+-------------------------
340322 | 3 | 3 | 1 | 3 | 1 | 0 | -1
(1 row)root block 从原来的 block 1 变为 block 3，查看 block 3 的的 Special space：
testdb=# select * from bt_page_stats(pk_t_index ,3);
blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags
-------+------+------------+------------+---------------+-----------+-----------+-----------+-----------+------+------------
3 | r | 3 | 0 | 13 | 8192 | 8096 | 0 | 0 | 1 | 2
(1 row)type=r，表示 root index block，这个 block 有 3 个 index entries（live_items=3，该 index block 只是 root block（btpo_flags=BTP_ROOT）。下面我们来看看这个 block 中的 index entries：
testdb=# select * from bt_page_items(pk_t_index ,3);
itemoffset | ctid | itemlen | nulls | vars | data
------------+---------+---------+-------+------+-------------------------
1 | (1,0) | 8 | f | f |
2 | (2,53) | 16 | f | f | 7b 01 00 00 00 00 00 00
3 | (4,105) | 16 | f | f | e9 02 00 00 00 00 00 00
(3 rows)root/branch index block 存储的是指向其他 index block 的指针。第 1 行，index entries 指向第 1 个 index block，由于该 block 没有 left block，因此，itemlen 只有 8 个字节，数据范围为 1 -\x0000017b（十进制值为 379）；第 2 行，index entries 指向第 2 个 index block，数据范围为 380-\x000002e9（745）；第 3 行，index entries 指向第 4 个 index block，数据范围为大于 745 的值。
这里有个疑惑，正常来说，root index block 中的 entries 应指向 index block，但 ctid 的值（2,53）和（4,105）指向的却是 Heap Table Block，PG11 Beta2 的 Bug？
In a B-tree leaf page, ctid points to a heap tuple. In an internal page, the block number part of ctid points to another page in the index itself, while the offset part (the second number) is ignored and is usually 1.
testdb=# select * from heap_page_items(get_raw_page( t_index ,2)) where t_ctid = (2,53)
lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax | t_field3 | t_ctid | t_infomask2 | t_infomask | t_hoff | t_bits | t_oid | t_data
----+--------+----------+--------+---------+--------+----------+--------+-------------+------------+--------+--------+-------+------------------------------------------
53 | 5648 | 1 | 43 | 1612755 | 0 | 360 | (2,53) | 3 | 2306 | 24 | | | \x7b0100001323333739232020200d2333373923
(1 row)
testdb=# select * from heap_page_items(get_raw_page( t_index ,4)) where t_ctid = (4,105)
lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax | t_field3 | t_ctid | t_infomask2 | t_infomask | t_hoff | t_bits | t_oid | t_data
-----+--------+----------+--------+---------+--------+----------+---------+-------------+------------+--------+--------+-------+------------------------------------------
105 | 3152 | 1 | 43 | 1612755 | 0 | 726 | (4,105) | 3 | 2306 | 24 | | | \xe90200001323373435232020200d2337343523
(1 row)回到正题，我们首先看看 index block 1 的相关数据：
testdb=# select * from bt_page_stats(pk_t_index ,1);
blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags
-------+------+------------+------------+---------------+-----------+-----------+-----------+-----------+------+------------
1 | l | 367 | 0 | 16 | 8192 | 808 | 0 | 2 | 0 | 1
(1 row)
testdb=# select * from bt_page_items(pk_t_index ,1) limit 10;
itemoffset | ctid | itemlen | nulls | vars | data
------------+--------+---------+-------+------+-------------------------
1 | (2,53) | 16 | f | f | 7b 01 00 00 00 00 00 00
2 | (0,1) | 16 | f | f | 02 00 00 00 00 00 00 00
3 | (0,2) | 16 | f | f | 04 00 00 00 00 00 00 00
4 | (0,3) | 16 | f | f | 08 00 00 00 00 00 00 00
5 | (0,4) | 16 | f | f | 10 00 00 00 00 00 00 00
6 | (0,6) | 16 | f | f | 11 00 00 00 00 00 00 00
7 | (0,5) | 16 | f | f | 12 00 00 00 00 00 00 00
8 | (0,8) | 16 | f | f | 13 00 00 00 00 00 00 00
9 | (0,9) | 16 | f | f | 14 00 00 00 00 00 00 00
10 | (0,10) | 16 | f | f | 15 00 00 00 00 00 00 00
(10 rows) 第 1 个 block 的 Special space，其中 type=l，表示 leaf index block，btpo_flags=BTP_LEAF 表示该 block 仅仅为 leaf index block，block 的 index entries 指向 heap table。同时，这个 block 里面有 367 个 items，右边兄弟 block 号是 2（btpo_next）。
值得注意到，index entries 的第 1 个条目，是最大值 \x017b，第 2 个条目才是最小值，接下来的条目是按顺序存储的其他值。源码的 README（src/backend/access/nbtree/README）里面有解释：
On a page that is not rightmost in its tree level, the high key is
kept in the page s first item, and real data items start at item 2.
The link portion of the high key item goes unused. A page that is
rightmost has no high key , so data items start with the first item.
Putting the high key at the left, rather than the right, may seem odd,
but it avoids moving the high key as we add data items.
官方文档也有相关解释：
Note that the first item on any non-rightmost page (any page with a non-zero value in the btpo_next field) is the page s“high key”, meaning its data serves as an upper bound on all items appearing on the page, while its ctid field is meaningless. Also, on non-leaf pages, the first real data item (the first item that is not a high key) is a“minus infinity”item, with no actual value in its data field. Such an item does have a valid downlink in its ctid field, however.
下面我们再来看看 index block 2 4：
testdb=# select * from bt_page_stats(pk_t_index ,2);
blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags
-------+------+------------+------------+---------------+-----------+-----------+-----------+-----------+------+------------
2 | l | 367 | 0 | 16 | 8192 | 808 | 1 | 4 | 0 | 1
(1 row)
testdb=# select * from bt_page_items(pk_t_index ,2) limit 10;
itemoffset | ctid | itemlen | nulls | vars | data
------------+---------+---------+-------+------+-------------------------
1 | (4,105) | 16 | f | f | e9 02 00 00 00 00 00 00
2 | (2,53) | 16 | f | f | 7b 01 00 00 00 00 00 00
3 | (2,54) | 16 | f | f | 7c 01 00 00 00 00 00 00
4 | (2,55) | 16 | f | f | 7d 01 00 00 00 00 00 00
5 | (2,56) | 16 | f | f | 7e 01 00 00 00 00 00 00
6 | (2,57) | 16 | f | f | 7f 01 00 00 00 00 00 00
7 | (2,58) | 16 | f | f | 80 01 00 00 00 00 00 00
8 | (2,59) | 16 | f | f | 81 01 00 00 00 00 00 00
9 | (2,60) | 16 | f | f | 82 01 00 00 00 00 00 00
10 | (2,61) | 16 | f | f | 83 01 00 00 00 00 00 00
(10 rows)
testdb=# select * from bt_page_stats(pk_t_index ,4);
blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags
-------+------+------------+------------+---------------+-----------+-----------+-----------+-----------+------+------------
4 | l | 276 | 0 | 16 | 8192 | 2628 | 2 | 0 | 0 | 1
(1 row)
testdb=# select * from bt_page_items(pk_t_index ,4) limit 10;
itemoffset | ctid | itemlen | nulls | vars | data
------------+---------+---------+-------+------+-------------------------
1 | (4,105) | 16 | f | f | e9 02 00 00 00 00 00 00
2 | (4,106) | 16 | f | f | ea 02 00 00 00 00 00 00
3 | (4,107) | 16 | f | f | eb 02 00 00 00 00 00 00
4 | (4,108) | 16 | f | f | ec 02 00 00 00 00 00 00
5 | (4,109) | 16 | f | f | ed 02 00 00 00 00 00 00
6 | (4,110) | 16 | f | f | ee 02 00 00 00 00 00 00
7 | (4,111) | 16 | f | f | ef 02 00 00 00 00 00 00
8 | (4,112) | 16 | f | f | f0 02 00 00 00 00 00 00
9 | (4,113) | 16 | f | f | f1 02 00 00 00 00 00 00
10 | (4,114) | 16 | f | f | f2 02 00 00 00 00 00 00
(10 rows)感谢各位的阅读，以上就是“PostgreSQL 数据库 B -Tree 索引的物理存储结构是怎样的”的内容了，经过本文的学习后，相信大家对 PostgreSQL 数据库 B -Tree 索引的物理存储结构是怎样的这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是丸趣 TV，丸趣 TV 小编将为大家推送更多相关知识点的文章，欢迎关注！
