概觀#

GiST（Generalized Search Tree，廣義搜尋樹）是一種存取方法，實質上是平衡搜尋樹對「支援值之間相對定位」之資料型別的推廣。

• B-tree 的適用性侷限於允許比較操作的序數型別（但對這類型別的支援極其高效）
• GiST 的運算子類別則允許定義任意的資料分佈準則

因此一個 GiST 索引可以容納：空間資料的 R-tree、集合的 RD-tree，以及任何資料型別（包括文字與影像）的簽章樹。

拜可擴充性之賜，你可以在 PostgreSQL 中從頭實作索引引擎介面來建立新的存取方法。但除了設計索引邏輯，你還得定義頁面佈局、有效率的鎖定策略與 WAL 支援——這需要紮實的程式技巧與大量實作心力。

GiST 簡化了這項任務：它處理掉所有低層級技術細節、提供搜尋演算法的基礎。要把 GiST 用於新的資料型別，你只需新增一個含約十個支援函式的運算子類別。

與 B-tree 那個平凡的運算子類別不同，GiST 的運算子類別含有大部分的索引邏輯。就此而言，GiST 可視為建構新存取方法的框架。

核心概念：述詞#

概括地說：

• 葉節點項目含有一個述詞（邏輯條件）與一個 heap 元組 ID。索引鍵必須滿足該述詞；鍵本身是否屬於該項目並不重要
• 內部節點項目也含有述詞與指向子節點的參照，該子樹中所有被索引的資料都必須滿足這個述詞

換言之，內部項目的述詞是其所有子項目述詞的聯集。GiST 的這項重要性質，扮演了 B-tree 中「簡單排序」所起的作用。

搜尋：一致性函式#

GiST 的樹搜尋依賴一致性函式（consistency function），這是運算子類別定義的支援函式之一。

一致性函式在索引項目上被呼叫，判定該項目的述詞是否與搜尋條件「一致」：

• 對內部項目：顯示是否必須下降到對應的子樹
• 對葉項目：檢查其索引鍵是否滿足條件

搜尋從根節點開始。一致性函式決定哪些子節點必須走訪、哪些可以跳過，接著對每個找到的子節點重複此程序。

搜尋永遠是深度優先的：演算法盡快抵達葉頁面。因此它能立刻開始回傳結果——當使用者只需要前幾列時，這非常有意義。

插入：penalty 與 picksplit#

插入新值時無法使用一致性函式，因為我們需要恰好選一個節點下降。這個節點必須有最小的插入成本，由運算子類別的 penalty 函式決定。

與 B-tree 一樣，選中的節點可能沒有空間而導致分裂。這需要另外兩個函式：

• picksplit 函式在新舊節點之間分配項目
• union 函式形成兩個述詞的聯集，以更新父節點的述詞

隨著新值不斷加入，既有述詞會擴張，而它們通常只在頁面分裂或整個索引重建時才被收窄。因此對 GiST 索引頻繁更新可能導致效能退化。

點的 R-tree#

第一個例子處理平面上點（或其他幾何物件）的索引。一般 B-tree 無法用於這種資料型別，因為點沒有定義比較運算子。

我們當然可以自行實作這類運算子，但幾何物件需要的是對完全不同操作的索引支援。以下只談其中兩項：搜尋落在特定區域內的物件，以及最近鄰搜尋。

結構#

R-tree 在平面上畫矩形；合起來它們必須涵蓋所有被索引的點。索引項目存放邊界框（bounding box），述詞可定義為：該點位於這個邊界框內。

• 根節點含有數個大矩形（可能重疊）
• 子節點含有塞得進其父節點的較小矩形，合起來涵蓋所有底下的點
• 葉節點本該含有被索引的點本身，但 GiST 要求所有項目具有相同的資料型別，因此葉項目也以矩形表示——只是退化成點

書中以擴充到五千列的機場資料為例，並刻意調低 fillfactor 讓樹變深（預設值會得到單層樹）：

=> CREATE INDEX airports_gist_idx ON airports_big
  USING gist(coordinates) WITH (fillfactor=10);

上層是數個部分重疊的大邊界框，下一層被切成較小的矩形，內層則讓每個邊界框恰好含有單一頁面所能容納的點數。

其他幾何物件也能以相同方式索引，但索引存放的不是物件本身，而是它的邊界框。

頁面佈局#

與 B-tree 索引不同，GiST 沒有 metapage，第零頁永遠是樹根。若根頁面被分裂，舊的根被搬到獨立的頁面，新的根取代它的位置。

=> SELECT ctid, keys
FROM gist_page_items(
   get_raw_page('airports_gist_idx', 0), 'airports_gist_idx'
);
    ctid     |                          keys
−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 (207,65535) | (coordinates)=((50.84510040283203,78.246101379395))
 ...
(4 rows)

遺憾的是，鍵在這裡被顯示為點（對葉頁面合理），而非矩形（對內部頁面才合邏輯）。不過我們總是可以取得原始資料自行解讀。

運算子類別的支援函式#

 amprocnum |         amproc
−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−
         1 | gist_point_consistent
         2 | gist_box_union
         3 | gist_point_compress
         5 | gist_box_penalty
         6 | gist_box_picksplit
         7 | gist_box_same
         8 | gist_point_distance
         9 | gist_point_fetch
        11 | gist_point_sortsupport

五個必要函式：

point_ops 運算子類別包含的運算子，全都涉及幾何物件的相對定位（左於、右於、上方、下方、包含、被包含）與它們之間的距離。

相較於 B-tree，GiST 提供更多策略。有些策略編號為數種索引類型共用，有些則由公式計算（例如 28、48、68 實質上代表同一個策略：矩形、多邊形、圓形的「被包含」）。

運算子類別可以只實作部分可用策略。例如「包含」策略不被點的運算子類別支援，但在有可測面積的幾何型別類別（box_ops、poly_ops、circle_ops）中可用。

搜尋被包含的元素#

典型能被索引加速的查詢，是回傳指定區域內的所有點：

=> SELECT airport_code, airport_name->>'en'
FROM airports_big
WHERE coordinates <@ '<(37.622513,55.753220),1.0>'::circle;
 airport_code |              ?column?
−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 SVO          | Sheremetyevo International Airport
 VKO          | Vnukovo International Airport
 ...

「包含」運算子 <@ 判定某點是否位於指定矩形內。該運算子的一致性函式在「索引項目的矩形與這個矩形有任何共同點」時回傳「是」。

這意味著：對存放「退化成點的矩形」的葉節點項目而言，這個函式判定的正是「該點是否被包含在指定矩形內」。

以一個簡單例子來看這個運算子：

若邊界框如此選定，索引結構會是：

搜尋過程（以尋找矩形內的點為例）：

1. 從根節點開始。邊界框與目標區域重疊者才需下降，不重疊的子樹直接跳過

2. 下一層若與兩個邊界框都重疊（或相切），兩個子樹都得檢查

   

3. 抵達葉節點後，走訪其中所有點，回傳滿足一致性函式者

   

最近鄰搜尋#

多數被索引支援的運算子（如 = 或 <@）稱為搜尋運算子，它們是述詞、回傳邏輯值。

但還有一組排序運算子（ordering operator），它們回傳參數之間的距離。這類運算子用在 ORDER BY 子句中，由具備 DISTANCE ORDERABLE 屬性的索引支援，讓你能快速找到指定數量的最近鄰——這種搜尋稱為 k-NN（k 最近鄰）搜尋。

=> SELECT airport_code, airport_name->>'en'
FROM airports_big
ORDER BY coordinates <-> '(40.926780,57.767943)'::point
LIMIT 10;

計畫使用 Index Scan 搭配 Order By。

由於索引掃描逐一回傳結果、可隨時停止，前幾個值能被非常快速地找到。

沒有索引支援的話，這種搜尋會非常難有效率地達成：我們得先找出某區域內所有的點，再逐步擴大區域直到回傳所需數量——這需要多次索引掃描，更別提「原始區域大小與遞增量該取多少」的問題。

distance 函式的關鍵約束#

要支援這類查詢，運算子類別必須定義額外的支援函式——distance 函式，它在索引項目上被呼叫，計算「該項目所存的值」到「另一個值」的距離。

• 葉元素：必須回傳到該被索引值的距離。對點而言就是一般的歐氏距離
• 內部元素：必須回傳「其所有子葉元素可能距離中的最小值」

由於掃描所有子項目相當昂貴，這個函式可以樂觀地低估距離（犧牲效率），但絕不可回傳更大的值——那會破壞搜尋的正確性。

因此對以邊界框表示的內部元素，「到點的距離」採一般數學意義：點到矩形的最小距離，或點在矩形內時為零。這個值不必走訪矩形的所有子點就能輕易算出，且保證不大於到其中任何一點的距離。

完整走訪：尋找點 (5,6) 的三個最近鄰

搜尋從根節點開始，它持有兩個邊界框：到 (0,0)–(3,4) 的距離取自矩形角落 (3,4)，等於 2.8（書中四捨五入到小數第一位，此例中寫作 5.0 與 0.0 的示意）；到 (5,3)–(9,9) 的距離為 0.0。

子節點依距離遞增順序被走訪。因此先下降到右子節點，它含有兩個矩形，距離分別為 0.0 與 3.0。

再次選右子樹，進入含三個點的葉節點：距離分別為 2.0、2.2、3.2。

於是得到前兩個點。但到這個節點第三個點的距離，大於到矩形 (5,3)–(8,5) 的距離——所以必須下降到左子節點，它含有兩個點，距離為 5.1 與 3.6。

結果發現：前一個子節點中的那個點比左子樹的任何節點都更近，因此可以把它作為第三個結果回傳。

這個例子說明了 distance 函式對內部項目的要求。由於到矩形 (5,3)–(8,5) 的距離被低估（3.0 而非實際值），多掃描了一個節點、搜尋效率下降；但演算法本身仍然正確。

插入#

新鍵插入 R-tree 時，使用哪個節點由 penalty 函式決定：邊界框的大小必須增加得越少越好。

例如點會被加到「面積只增加 2 單位」的矩形，而非「得增加 12 單位」的那個。下一層（葉層）也依同樣邏輯。

假設一頁最多放三個元素，就必須分裂成二、把元素分配到新頁面。此例結果看似顯然，但一般情況下資料分配的任務並不簡單。

排除約束#

GiST 索引也可用於排除約束。排除約束保證任何兩個 heap 元組的指定欄位在某運算子意義下不互相匹配，必須滿足：

• 該索引方法支援排除約束（CAN EXCLUDE 屬性）
• 該運算子屬於此索引方法的運算子類別
• 該運算子可交換：a 運算子 b = b 運算子 a 必須成立

對前面談過的 hash 與 btree 方法，唯一合適的運算子是「等於」，這實質上把排除約束變成唯一約束——並不特別有用。

gist 方法則多了兩種適用策略：

• 重疊：&& 運算子
• 相鄰：-|- 運算子（為區間定義）

=> ALTER TABLE airports_data ADD EXCLUDE
USING gist (circle(coordinates,0.2) WITH &&);
=> INSERT INTO airports_data(...) VALUES ('ZIA', ...);
ERROR: conflicting key value violates exclusion constraint
"airports_data_circle_excl"

定義排除約束時，用來強制它的索引會被自動加上。此處是一個建立在運算式上的 GiST 索引。

btree_gist 擴充#

更複雜的例子：允許機場彼此靠近，但僅限它們屬於同一城市。可表述為：禁止有「圓形相交（&&）且對應城市名稱不同（!=）」的列配對。

直接建立會失敗，因為 text 型別沒有 GiST 的運算子類別：

ERROR: data type text has no default operator class for access method "gist"

然而 GiST 確實提供「嚴格左於」「嚴格右於」「相同」之類的策略，這些也能套用到數字或文字字串等一般序數型別。btree_gist 擴充正是為了實作「通常與 B-tree 搭配使用之操作」的 GiST 支援：

=> CREATE EXTENSION btree_gist;
=> ALTER TABLE airports_data ADD EXCLUDE USING gist (
   circle(coordinates,0.2) WITH &&,
             (city->>'en') WITH !=
);
ALTER TABLE

約束建立成功後，同名城鎮的 Zhukovsky 機場無法加入（莫斯科的機場太近），但指定其城市為 Moscow 就可以了。

必須記得：儘管 GiST 支援大於、小於、等於操作，B-tree 在這方面高效得多，尤其是存取值域範圍時。

因此只有在確實因其他正當理由需要 GiST 索引時，才適合使用上述 btree_gist 的技巧。

全文檢索的 RD-tree#

全文檢索簡述#

全文檢索的目標是從給定的文件集合中選出符合搜尋查詢者。

• 待搜尋的文件被轉型為 tsvector，其中含有詞素（lexeme）及其在文件中的位置。詞素是被轉換成適合搜尋格式的字詞：預設所有字詞被正規化為小寫、字尾被截掉
• 所謂的停用詞（如 the、from）會被濾掉：它們被假定出現得太頻繁，搜尋它們不會回傳有意義的結果
• 搜尋查詢由另一種型別 tsquery 表示，含一或多個以邏輯連接詞 &（AND）、|（OR）、!（NOT）綁定的詞素，也可用括號定義優先序

=> SELECT to_tsvector(
   'No one can tell me, nobody knows, ' ||
   'Where the wind comes from, where the wind goes.'
);
 'come':11 'goe':16 'know':7 'nobodi':6 'one':2 'tell':4 'wind':10,15

全文檢索唯一使用的運算子是匹配運算子 @@，它判定文件是否滿足查詢。

索引 tsvector 資料#

要跑得快，全文檢索必須有索引支援。由於被索引的不是文件本身而是 tsvector 值，你有兩個選擇：

而如我們馬上會看到的，GiST 會重新檢查所有列——這使第一種做法的代價更明顯。

=> CREATE TABLE ts(
   doc text,
   doc_tsv tsvector GENERATED ALWAYS AS (
     to_tsvector('pg_catalog.english', doc)
   ) STORED
);
=> CREATE INDEX ts_gist_idx ON ts USING gist(doc_tsv);

此處使用明確指定組態的 to_tsvector 版本。單參數版本隱含依賴 default_text_search_config 參數值，其 volatility 類別為 STABLE；而明確指定組態的版本是 IMMUTABLE，才能用在產生欄位的運算式中。

從 RD-tree 到簽章樹#

R-tree 本身對索引文件毫無用處——邊界框的概念對文件沒有意義。因此改用它的 RD-tree（Russian Doll，俄羅斯娃娃）變體：以邊界集合取代邊界框，該集合含有其所有子集合的元素。

對全文檢索而言，這個集合含有文件的詞素；但一般情況下邊界集合可以是任意的。

最簡單的表示法是列舉集合的所有元素：

要找出滿足 doc_tsv @@ to_tsquery('cow') 條件的文件，只需下降到「子項目已知含有 cow 詞素」的節點：

但問題顯而易見：

全文檢索採用另一個更緊湊的解法：簽章樹（signature tree）——熟悉 Bloom filter 的人應該不陌生。

• 每個詞素以其簽章表示：一個特定長度的位元字串，其中只有一個位元被設為 1，該位元由詞素的雜湊函式決定
• 文件的簽章是其所有詞素簽章做逐位元 OR 的結果

搜尋時，查詢的簽章以相同方式計算，一致性函式必須找出「簽章中設定了相同位元」的所有子節點。

由於簽章容量有限，大集合中的某些詞素必然共用相同簽章（書中例子裡是 cow 與 oink），因此一個簽章可能匹配到不同文件。

偽陽性降低索引效率，但完全不影響其正確性：由於偽陰性保證被排除，所需的值不可能被漏掉。

簽章長度的調校#

實際的簽章當然大得多——預設 124 位元組（992 位元），碰撞機率遠低於書中示例。必要時可用運算子類別參數把簽章加大到約 2024 位元組（PostgreSQL 13 起）：

CREATE INDEX ... USING gist(column tsvector_ops(siglen = 1024));

此外，若值夠小（略小於頁面的 1/16，標準頁面約 500 位元組），tsvector_ops 運算子類別在索引葉頁面中存放的是 tsvector 值本身而非其簽章。

實測（pgsql-hackers 郵件列表封存，356,000 封郵件）：

=> CREATE INDEX mail_gist_idx ON mail_messages USING gist(tsv);
-- 索引大小 127 MB

=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM mail_messages WHERE tsv @@ to_tsquery('magic & value');
 Index Scan using mail_gist_idx on mail_messages (actual rows=898 loops=1)
   Index Cond: (tsv @@ to_tsquery('magic & value'::text))
   Rows Removed by Index Recheck: 7859

除了 898 列符合條件，存取方法還回傳了 7859 列待重檢濾除。把簽章容量加大（siglen=248）後：

• 索引大小從 127 MB 增為 139 MB
• 被重檢濾除的列從 7859 降為 2060

屬性#

存取方法屬性#

索引層級屬性#

欄位層級屬性#

大多數欄位屬性定義在存取方法層級、保持不變：

     name     | pg_index_column_has_property
−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 orderable    | f
 search_array | f
 search_nulls | t

但有兩個欄位層級屬性確實取決於特定的運算子類別：

• 點：葉節點保有完整索引鍵，因此允許唯索引掃描；且該運算子類別提供最近鄰搜尋的距離運算子（到 NULL 的距離視為 NULL，這類值最後回傳，類似 B-tree 的 NULLS LAST）
• 範圍型別：它們代表線段（線性而非面狀幾何），沒有距離運算子
• 全文檢索：無法從簽章還原原始值，因此唯索引掃描不可能。這在此情境下完全沒問題——tsvector 值只用於搜尋，我們要取回的是文件本身

GiST 支援的其他資料型別#

前述兩個例子顯示：儘管 GiST 方法建立在平衡樹之上，透過不同運算子類別中不同的支援函式實作，它能被用於各種資料型別。

談到 GiST 索引時，我們必須永遠指明運算子類別——因為它對索引屬性起決定性作用。

運算子類別名稱中多出的底線屬於「基本型別陣列」的名稱。例如整數陣列除了常見的 int4[] 寫法，也可記為 _int4——不過並沒有 _int 與 _bigint 這兩種型別。