概觀#

B-tree（以 btree 存取方法實作）是一種資料結構，讓你能從根節點往下走，快速在樹的葉節點中找到所需元素。

為了讓搜尋路徑能被明確辨識，所有樹元素都必須是有序的。B-tree 是為序數資料型別（值可比較、可排序）設計的。

每個樹節點含有數個元素，每個元素由索引鍵與指標組成：

• 內部節點的元素參照下一層的節點
• 葉節點的元素參照 heap 元組

B-tree 的重要性質#

• 平衡：所有葉節點位於相同深度，因此保證對所有值的搜尋時間相同
• 分支眾多：每個節點含有許多元素，往往數百個。因此即使對非常大的表格，B-tree 的深度也始終很小
• 有序：索引中的資料依升冪或降冪排序，節點內與同層所有節點之間皆然。同層節點被串成雙向清單，因此只要單向掃描清單就能取得有序資料集，不必每次都從根節點開始

我們無法百分之百確定名稱中的 B 代表什麼。balanced 與 bushy 都同樣說得通。令人意外的是，它常被解讀為 binary——這肯定是錯的。

以機場代碼上的索引為例（內部節點畫成水平矩形，葉節點垂直排列）：

搜尋與插入#

等值搜尋#

從根節點開始，存取方法必須決定該往哪個子節點下降：它選擇滿足 Kᵢ ≤ 運算式 < Kᵢ₊₁ 的鍵 Kᵢ。這個程序遞迴重複，直到抵達含所需元組 ID 的葉節點。葉節點中的目標元素可用二分搜尋快速找到。

你可能注意到，樹內部節點中最左邊的鍵是多餘的——B-tree 不儲存這類鍵。

然而搜尋程序並不如看起來那麼單純，還必須考量：

• 索引中資料的排序可以是升冪也可以是降冪
• 即使是唯一索引也可能有多個匹配值，且全部都必須回傳
• 重複值可能多到塞不進單一節點，因此相鄰的葉節點也得處理
• 搜尋進行時其他行程可能修改資料，頁面可能被分裂，樹結構可能改變

所有演算法都盡可能設計成最小化並行操作間的爭用、避免過度上鎖。

由於索引可能含非唯一值，稱其順序為「非降冪」比「升冪」更精確。此外，元組 ID 是索引鍵的一部分（PostgreSQL 12 起），這讓我們即使在值實際相同時也能把索引項目視為唯一。

不等值與範圍搜尋#

• 不等值搜尋（≤／≥）：先搜尋滿足等值條件的值，再沿所需方向走訪葉節點直到樹的盡頭。對 <／> 運算子程序相同，只是必須排除第一個找到的值。

  

• 範圍搜尋（運算式1 ≤ 欄位 ≤ 運算式2）：先找到運算式 1，再往右走訪葉節點直到抵達運算式 2。

  

插入與節點分裂#

新元素的插入位置由鍵的順序明確決定。

但若葉節點空間不足呢？

1. 該節點被分裂成兩個，舊節點的部分元素被移到新節點
2. 指向新子節點的指標被加入父節點
3. 父節點顯然也可能被塞爆，於是它也被分裂成兩個，依此類推
4. 若一路裂到根節點，就在結果節點之上再建一個節點作為新的樹根——此時樹的深度增加一層

為確保任何節點都能被分裂，雙向清單串起了所有層級的節點，而不只是最底層。

上述插入與分裂程序保證樹維持平衡；而由於節點能容納的元素數量通常相當大，樹深度很少增加。

問題在於：節點一旦分裂就永遠無法合併回去，即使清理後只剩下極少元素。

這個限制並非源於 B-tree 資料結構本身，而是 PostgreSQL 的實作。因此嘗試插入時若節點已滿，存取方法會先嘗試修剪多餘資料以清出空間、避免額外的分裂。

頁面佈局#

B-tree 的每個節點佔一個頁面，頁面大小決定節點容量。

由於頁面分裂，樹根在不同時間可能由不同頁面代表。但搜尋演算法必須永遠從根開始掃描——它在**第零頁（metapage）**中找到目前根頁面的 ID，metapage 也含有其他中繼資料。

索引頁面中的資料佈局與前面所見略有不同：除了每層最右邊的頁面之外，所有頁面都含有一個額外的「high key」，保證不小於該頁面中的任何鍵。

=> SELECT root, level FROM bt_metap('bookings_pkey');
 root | level
−−−−−−+−−−−−−−
  290 |     2

=> SELECT itemoffset, ctid, data_to_text(data)
FROM bt_page_items('bookings_pkey',290);
 itemoffset |    ctid   | data_to_text
−−−−−−−−−−−−+−−−−−−−−−−+−−−−−−−−−−−−−−
           1 | (3,0)    |               ← 第一項不含鍵
 ...
          19 | (5135,1) | E2CB14
          20 | (5420,1) | EF6FEA
          21 | (5705,1) | FC147D

 itemoffset |    ctid   | data_to_text
−−−−−−−−−−−−+−−−−−−−−−−+−−−−−−−−−−−−−−
           1 | (5417,1) | EF6FEA        ← high key
           2 | (5132,0) |
           3 | (5133,1) | E2D71D
           4 | (5134,1) | E2E2F4

=> SELECT * FROM bookings WHERE ctid = '(11919,77)';
 book_ref |       book_date        | total_amount
−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−
 E2D725   | 2017−01−25 04:10:00+03 |     28000.00

去重（PostgreSQL 13 起）#

非唯一索引可能含有大量指向不同 heap 元組的重複鍵。由於非唯一鍵出現不只一次、佔用大量空間，重複項會被摺疊成單一索引項目，其中含有鍵與對應的元組 ID 清單。

這個程序（稱為 deduplication）在某些情況下能顯著縮小索引大小。

然而唯一索引也可能因 MVCC 而含有重複：索引保存對表格列所有版本的參照。HOT 更新機制能對抗「參照過期、通常短命的列版本」所造成的索引膨脹，但有時不適用——此時去重能爭取到清理多餘 heap 元組所需的時間，避免額外的頁面分裂。

觸發時機：為避免在無立即效益時浪費資源，只有在葉頁面空間不足以再容納一個元組時才會執行摺疊。屆時頁面修剪與去重能清出空間、防止不樂見的頁面分裂。

若重複很少見，可關閉 deduplicate_items 儲存參數來停用去重功能。

不支援去重的情況：

主要限制是鍵的相等必須能以「其內部表示的簡單二進位比較」來檢查。遠非所有資料型別都能這樣比較：

• 浮點數（float、double precision）：零有兩種不同表示
• 任意精度數字（numeric）：同一個數字可用不同的 scale 表示，而 jsonb 型別可能用到這類數字
• 文字型別若使用非確定性定序（同樣的符號可由不同位元組序列表示；標準定序是確定性的）
• 此外目前也不支援複合型別、範圍型別、陣列，以及以 INCLUDE 子句宣告的索引

要檢查某索引是否能用去重，看它 metapage 的 allequalimage 欄位即可。

內部索引項目的緊湊儲存（PostgreSQL 13 起）#

去重讓葉頁面能容納更多項目。但即使葉頁面構成索引的絕大部分，在內部頁面做資料壓實以防止額外分裂同樣重要——因為搜尋效率直接取決於樹的深度。

內部索引項目含有索引鍵，但它們的值只用來決定搜尋時該下降到哪個子樹。在多欄位索引中，取第一個鍵屬性（或前幾個）往往就夠了，其他屬性可被截斷以節省頁面空間。

這種後綴截斷（suffix truncation）發生在葉頁面被分裂、內部頁面必須容納新指標時。

=> CREATE INDEX tickets_bref_name_idx ON tickets(book_ref, passenger_name);
=> SELECT itemoffset, ctid, data_to_text(data)
FROM bt_page_items('tickets_bref_name_idx',229)
WHERE itemoffset BETWEEN 8 AND 13;
 itemoffset |   ctid   |        data_to_text
−−−−−−−−−−−−+−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−
          8 | (1607,1) | 1A98A0                      ← 第二屬性被截斷
          9 | (1833,2) | 1E57D1, SVETLANA MAKSIMOVA
         10 | (2054,1) | 220797

理論上還能更進一步，只保留屬性中有意義的部分（例如足以區分子樹的前幾個字元）。但目前尚未實作：索引項目要不含整個屬性，要不完全排除該屬性。

葉頁面自然必須保留所有鍵屬性與 INCLUDE 欄位值，否則就無法執行唯索引掃描。唯一的例外是 high key，它可以只保留一部分。

運算子類別#

比較語意#

除了雜湊值，系統也必須知道如何排序各種型別（包括自訂型別）的值——這對排序、分組、合併連接等操作不可或缺。與雜湊的情況一樣，特定資料型別的比較運算子由運算子類別定義。

運算子類別讓我們能從名稱（>、<、=）抽象出來，甚至能為同一型別提供多種排序方式。

btree 方法的任何運算子類別都必須定義五個比較運算子，各對應一個策略編號：

B-tree 運算子類別還包含數個支援函式：

=> CREATE TYPE capacity_units AS ENUM ('B', 'kB', 'MB', 'GB', 'TB', 'PB');
=> CREATE TYPE capacity AS (amount integer, unit capacity_units);

=> CREATE FUNCTION capacity_to_bytes(a capacity) RETURNS numeric
AS $$
SELECT a.amount::numeric *
  1024::numeric ^ ( array_position(enum_range(a.unit), a.unit) - 1 );
$$ LANGUAGE sql STRICT IMMUTABLE;

=> CREATE FUNCTION capacity_cmp(a capacity, b capacity) RETURNS integer
AS $$
SELECT sign(capacity_to_bytes(a) - capacity_to_bytes(b));
$$ LANGUAGE sql STRICT IMMUTABLE;

=> CREATE OPERATOR #<# (
   LEFTARG = capacity, RIGHTARG = capacity, FUNCTION = capacity_lt
);
-- #<=#、#=#、#>=#、#># 以類似方式定義
=> CREATE OPERATOR #=# (
   LEFTARG = capacity, RIGHTARG = capacity, FUNCTION = capacity_eq,
   MERGES -- 可用於合併連接
);

=> CREATE OPERATOR CLASS capacity_ops
DEFAULT FOR TYPE capacity -- 預設使用
USING btree AS
  OPERATOR 1 #<#,
  OPERATOR 2 #<=#,
  OPERATOR 3 #=#,
  OPERATOR 4 #>=#,
  OPERATOR 5 #>#,
  FUNCTION 1 capacity_cmp(capacity,capacity);

多欄位索引與排序#

宣告索引時選擇最佳的欄位順序極為重要：頁面內的資料排序從第一欄開始，再到第二欄，依此類推。

多欄位索引只有在過濾條件涵蓋「從第一欄起的連續欄位序列」時才能保證有效率的搜尋：第一欄、前兩欄、第一到第三欄的範圍等。其他類型的條件只能用來過濾依其他準則取得的多餘值。

以 (book_ref, passenger_name) 索引為例：

• 依 book_ref 搜尋 → 有效率（Index Scan）
• 依 book_ref + passenger_name 搜尋 → 有效率
• 只依 passenger_name 搜尋 → 必須掃描所有列（Parallel Seq Scan）

即使規劃器選擇執行索引掃描，所有索引項目仍必須被走訪一遍。遺憾的是，計畫不會顯示該條件實際上只被用於過濾結果。

col1 = v1 AND col2 = value
col1 = v2 AND col2 = value
⋯
col1 = vn AND col2 = value

反過來，若建立 (passenger_name, book_ref) 索引，它就更適合「只依乘客姓名」或「姓名 + 訂位代碼」的查詢。

排序方向與 NULL 位置#

除了欄位順序，建立索引時也該注意排序方向。預設升冪（ASC），必要時可反轉（DESC）。

單欄位索引無所謂（可雙向掃描），但多欄位索引中方向就變得重要：

• ORDER BY passenger_name, book_ref → Index Scan
• ORDER BY passenger_name DESC, book_ref DESC → Index Scan Backward
• ORDER BY passenger_name ASC, book_ref DESC → 索引只提供部分有序資料，須再用 Incremental Sort 依第二屬性排序

NULL 值的位置也影響索引能否用於排序。預設 NULL 在排序上被視為「大於」一般值：升冪時位於樹的右側，降冪時位於左側。可用 NULLS FIRST 與 NULLS LAST 子句改變。

-- 索引不滿足 ORDER BY → 必須排序
=> EXPLAIN (costs off) SELECT * FROM tickets
ORDER BY passenger_name NULLS FIRST, book_ref DESC;
 Gather Merge
   −> Sort
       Sort Key: passenger_name NULLS FIRST, book_ref DESC

-- 建立符合所需順序的索引後
=> CREATE INDEX tickets_name_bref_idx2
ON tickets(passenger_name NULLS FIRST, book_ref DESC);
 Index Scan using tickets_name_bref_idx2 on tickets

屬性#

存取方法屬性#

索引層級屬性#

欄位層級屬性#

         name       | pg_index_column_has_property
−−−−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 asc                | t
 desc               | f
 nulls_first        | f
 nulls_last         | t
 orderable          | t
 distance_orderable | f
 returnable         | t
 search_array       | t
 search_nulls       | t

• orderable 表示 B-tree 中的資料是有序的，而前四個屬性（asc／desc、nulls_first／nulls_last）定義特定欄位的實際順序。本例為升冪、NULL 排最後
• search_nulls 表示可以搜尋 NULL 值
• distance_orderable 為 false——B-tree 不支援排序運算子，儘管曾有實作的嘗試
• search_array 支援在陣列中搜尋多個元素；returnable 表示能不存取 heap 就回傳結果資料