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;