PostgreSQL/索引 Btree
术语 B 树索引 表示 平衡树 的实现。B 树的特点是，从根节点到每个叶子节点的距离都相同。此类树支持对 WHERE status=5 等搜索条件的快速评估。在大多数情况下，此类树具有高分支因子，因此深度较低。例如，如果分支因子为 500，则该树可以使用 3 次页面读取来管理约 1.25 亿个条目。
此外，PostgreSQL 实现使用 Lehmann 和 Yao 最初提出的策略优化了树上并发写入操作的锁定行为。该想法是为每个页面添加额外的（从整个树的角度来看是冗余的）指针。
B 树是默认的索引类型。它由 SQL 命令 CREATE INDEX 创建，其中省略了关键字 USING。
-- create a b-tree index
CREATE INDEX test_idx ON table_1 (column_1);
-- equivalent syntax:
CREATE INDEX test_idx ON table_1 USING BTREE(column_1);
包含 B 树的文件由不同的页面类型组成。
- 该文件的第一个页面（＃0）包含有关索引的元信息，例如指向根页面的指针（并不总是位于页面＃1 上），或当前树深度。
- 内部页面 包含键和指针对。键保存要索引的值，指针指向下一级的内部页面或叶子页面。这些对被称为索引条目。
- 叶子页面 也包含此类对。但在这种情况下，它们指向数据文件（堆）中的页面和行。此类指针称为元组 ID 或TID。
- 内部页面加上叶子页面构成 B 树。
随着时间的推移，需要拆分页面，因为它们的容量已用尽。首先，树的宽度会增加。在极少数情况下，需要扩展树的高度。在这种情况下，根页面会被拆分，并创建一个新的根页面。
有一些特殊规则可以优化对 B 树的访问，特别是减少多用户环境中锁的可能性。因此，这些页面包含一些额外的信息，增强了纯 B 树实现。
- 每个页面的第一个索引条目包含一个值，该值被视为该页面中所有键的上限。它不包含指向另一个页面的指针。它被称为高键，在上面的图形中，它以红色显示。每级最右边的页面不包含高键。它在定义上是正无穷大。
- 第二个（如果不存在高键，则为第一个）索引条目指向页面的左侧子项。它不包含实际的键。有时它被称为负无穷大。叶子页面不使用它。
- 每级页面通过 双向链表 连接在一起。这有助于加速
WHERE status>17等查询，因为消除了向上遍历树的需要。
-- PostgreSQL version 14.1 at Ubuntu 20.4
-- a helper to create huge text values via 'gen_random_bytes()'
CREATE EXTENSION IF NOT EXISTS pgcrypto;
-- a helper to inspect physical pages
CREATE EXTENSION IF NOT EXISTS pageinspect;
-- table with a text field
DROP TABLE IF EXISTS t1;
CREATE TABLE t1 (
key integer,
val text -- will be indexed with B-tree
);
-- insert huge text values to enforce page splits in index file
INSERT INTO t1
(SELECT
generate_series(11, 22, 1),
concat(generate_series(11, 22, 1), ' ', gen_random_bytes(1024)::text)
);
-- same as:
-- INSERT INTO t1 VALUES (11, '11 ' || gen_random_bytes(1024)::text);
-- INSERT INTO t1 VALUES (12, '12 ' || gen_random_bytes(1024)::text);
-- ...
-- create the B-tree
CREATE INDEX t1_btree_idx ON t1 (val);
-- Inspect the pages of the created B-tree
-- read meta page: it shows that page 9 is the root of the B-tree
SELECT * FROM bt_metap('t1_btree_idx');
-- read page 9: root page of B-tree
SELECT itemoffset, ctid, itemlen, nulls, vars, left(data, 23) AS data FROM bt_page_items('t1_btree_idx', 9);
-- read pages 3 + 8 (internal pages)
SELECT itemoffset, ctid, itemlen, nulls, vars, left(data, 23) AS data FROM bt_page_items('t1_btree_idx', 3);
SELECT itemoffset, ctid, itemlen, nulls, vars, left(data, 23) AS data FROM bt_page_items('t1_btree_idx', 8);
-- read pages 1, 2, 4 and 5, 6, 7 (leaf pages)
SELECT itemoffset, ctid, itemlen, nulls, vars, left(data, 23) AS data FROM bt_page_items('t1_btree_idx', 1);
SELECT itemoffset, ctid, itemlen, nulls, vars, left(data, 23) AS data FROM bt_page_items('t1_btree_idx', 2);
SELECT itemoffset, ctid, itemlen, nulls, vars, left(data, 23) AS data FROM bt_page_items('t1_btree_idx', 4);
SELECT itemoffset, ctid, itemlen, nulls, vars, left(data, 23) AS data FROM bt_page_items('t1_btree_idx', 5);
SELECT itemoffset, ctid, itemlen, nulls, vars, left(data, 23) AS data FROM bt_page_items('t1_btree_idx', 6);
SELECT itemoffset, ctid, itemlen, nulls, vars, left(data, 23) AS data FROM bt_page_items('t1_btree_idx', 7);
-- show the TIDs per key (in heap file, NOT in index file)
SELECT key, ctid FROM t1;