概觀#

SP-GiST 名稱開頭的 SP 代表 Space Partitioning（空間分割）。這裡的「空間」指的是任意一組被搜尋的值，不必然是一般語意下的空間（例如二維平面）。名稱中的 GiST 則暗示了它與 GiST 的相似性：兩者都是廣義搜尋樹，都是索引各種資料型別的框架。

SP-GiST 的核心構想是：把搜尋空間切成數個互不重疊的區域，這些區域又可再遞迴地切成子區域。

這種分割產生的是非平衡樹（與 B-tree、GiST 不同），可用來實作幾種著名結構：四元樹（quadtree）、k-d 樹（k-dimensional tree）與基數樹（radix tree，又稱 trie）。

非平衡樹帶來的頁面問題#

非平衡樹通常分支少、深度大。例如四元樹節點最多四個子節點，k-d 樹節點只有兩個。

• 樹存在記憶體中時，這不構成問題
• 樹存在磁碟上時，節點必須盡可能密實地塞進頁面以減少 I/O——而這並不容易

B-tree 與 GiST 索引不必操心這件事，因為它們的每個樹節點就佔滿整個頁面。

節點內容#

與 GiST 一樣，SP-GiST 只實作主要演算法，並處理並行存取、鎖定、日誌等低層細節。新的資料型別與空間分割演算法透過運算子類別介面加入，大部分索引邏輯都落在運算子類別中。

搜尋與插入的關鍵函式#

搜尋在 SP-GiST 中永遠是深度優先，從根節點開始。值得下降的節點由一致性函式（consistency function）挑選，與 GiST 中的同名函式類似：

• 對內部節點：回傳一組其值不與搜尋述詞矛盾的子節點。它不會下降進這些節點，僅評估對應的標籤與前綴
• 對葉節點：判定該節點的索引值是否符合搜尋述詞

在非平衡樹中，搜尋時間會隨分支深度而變動——不同分支的查詢成本可能差異很大。

插入則有兩個支援函式參與：

• choose 函式：從根節點向下走訪時，決定要把新值送進既有子節點、為它建立新的子節點，或是分裂當前節點（當值不符合該節點前綴時）
• picksplit 函式：若選中的葉頁面空間不足，決定哪些節點該搬到新頁面

點的四元樹#

四元樹用於索引二維平面上的點。平面以一個選定的點為基準，遞迴地切成四個區域（象限）。這個點稱為質心（centroid），扮演節點前綴的角色，也就是定義子值位置的條件。

• 根節點把平面分成四個象限
• 每個象限再切成自己的四個象限
• 如此持續，直到達成所需的分割數

=> CREATE INDEX airports_quad_idx ON airports_big
USING spgist(coordinates) WITH (fillfactor = 10);

書中在擴充過的 airports 表上建索引，並刻意調低 fillfactor 讓樹變深，以便觀察：分支深度取決於對應象限中的點密度。

點的預設運算子類別是 quad_point_ops。

運算子類別#

quad_point_ops 的支援函式全部都是必要的：

 amprocnum |          amproc
−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−
         1 | spg_quad_config
         2 | spg_quad_choose
         3 | spg_quad_picksplit
         4 | spg_quad_inner_consistent
         5 | spg_quad_leaf_consistent
(5 rows)

此外還有數個選用函式。quad_point_ops 支援的策略與 GiST 相同。

=> SELECT amopopr::regoperator, oprcode::regproc, amopstrategy
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
  JOIN pg_amop amop ON amopfamily = opcfamily
  JOIN pg_operator opr ON opr.oid = amopopr
WHERE amname = 'spgist'
AND opcname = 'quad_point_ops'
ORDER BY amopstrategy;
     amopopr      |    oprcode     | amopstrategy
−−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−
 <<(point,point)  | point_left     |            1
 >>(point,point)  | point_right    |            5
 ~=(point,point)  | point_eq       |            6
 <@(point,box)    | on_pb          |            8
 <<|(point,point) | point_below    |           10
 |>>(point,point) | point_above    |           11
 <−>(point,point) | point_distance |           15
 <^(point,point)  | point_below    |           29
 >^(point,point)  | point_above    |           30
(9 rows)

=> SELECT airport_code, airport_name->>'en'
FROM airports_big
WHERE coordinates >^ '(80.3817,73.5167)'::point;
 airport_code |          ?column?
−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 THU          | Thule Air Base
 YEU          | Eureka Airport
 YLT          | Alert Airport
 YRB          | Resolute Bay Airport
 LYR          | Svalbard Airport, Longyear
 NAQ          | Qaanaaq Airport
 YGZ          | Grise Fiord Airport
 DKS          | Dikson Airport
(8 rows)

=> EXPLAIN (costs off) SELECT airport_code
FROM airports_big
WHERE coordinates >^ '(80.3817,73.5167)'::point;
                          QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Bitmap Heap Scan on airports_big
   Recheck Cond: (coordinates >^ '(80.3817,73.5167)'::point)
   −> Bitmap Index Scan on airports_quad_idx
       Index Cond: (coordinates >^ '(80.3817,73.5167)'::point)
(4 rows)

以 GiST 章節用過的簡單多點範例說明四元樹的結構：落在邊界上的點歸入編號較小的象限；每個內部節點最多參照四個子節點，每個指標都以象限編號標示。

頁面佈局#

與 B-tree、GiST 不同，SP-GiST 的樹節點與頁面之間沒有一對一對應。由於內部節點通常子節點不多，必須把數個節點打包進單一頁面。

不同類型的節點存在不同頁面：內部節點存於內部頁面，葉節點存於葉頁面。

• 內部頁面的索引項目：作為前綴的值，加上一組指向子節點的指標（每個指標可附標籤）
• 葉頁面的索引項目：一個值與一個 TID

隸屬於同一個內部節點的所有葉節點，會一起存在單一頁面中並串成一個串列。若頁面容不下新節點，這個串列可以搬到別的頁面，或是把頁面分裂——不論哪種方式，一個串列絕不會橫跨數個頁面。

為節省空間，演算法會盡量把新節點加進同一批頁面，直到它們完全填滿。最後使用的頁面編號由 backend 快取，並定期存入第零頁（稱為 metapage）。

遺憾的是，pageinspect 擴充沒有提供任何探索 SP-GiST 的函式。可改用外部擴充 gevel。曾有人嘗試把它的功能整合進 pageinspect，但未能成功。

回到先前的範例。quad_point_ops 運算子類別實際上並不使用標籤；由於一個節點最多四個子節點，索引保留一個含四個指標的固定大小陣列，其中部分可能為空。

搜尋#

以「找出位於點 (7,5) 上方的點」為例：

1. 搜尋自根節點開始。內部一致性函式判定該下降到哪些子節點——把 (7,5) 與根節點質心 (5,5) 比較，選出可能含有目標點的象限（此例為象限 I 與 IV）
2. 進入質心 (7,7) 的節點後，再次選擇要下降的子節點。它們屬於象限 I 與 II，但象限 II 是空的，因此只需檢查一個葉節點
3. 葉一致性函式把該節點的點與查詢中的 (7,5) 比較，只有 (8,9) 滿足條件
4. 回到上一層，檢查根節點象限 IV 對應的節點——它是空的，搜尋結束

插入#

值被插入 SP-GiST 樹時，後續每個動作都由 choose 函式決定。以點的運算子類別而言，它單純把點導向對應象限的既有節點。

以加入值 (7,1) 為例：

該值屬於象限 II，會被加進對應的樹節點：

若插入後選定象限的葉節點串列變得過大（必須塞得進單一頁面），頁面就會分裂：

以插入 (2,1) 造成頁面溢位為例：

一個質心為 (1,1) 的新內部節點被加入樹中，點 (0,0)、(1,2)、(2,1) 隨之在新象限之間重新分配：

屬性#

存取方法層級：

 amname |     name      | pg_indexam_has_property
−−−−−−−−+−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−
 spgist | can_order     | f
 spgist | can_unique    | f
 spgist | can_multi_col | f
 spgist | can_exclude   | t
 spgist | can_include   | t
(5 rows)

• 不支援排序與唯一性，也不支援多欄索引
• 支援排除約束（exclusion constraint），與 GiST 相同
• 從 PostgreSQL 14 起，SP-GiST 索引可帶額外的 INCLUDE 欄位

索引層級：

     name      | pg_index_has_property
−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−
 clusterable   | f
 index_scan    | t
 bitmap_scan   | t
 backward_scan | f
(4 rows)

與 GiST 不同，SP-GiST 索引不支援叢集化（clusterization）。取得 TID 的兩種方式（逐一或以 bitmap）都支援；反向掃描不可用，因為對 SP-GiST 而言毫無意義。

欄位層級：排序不受支援，所有相關屬性因而失效；search_nulls 為 t。

關於 NULL 值：與 GiST 不同，SP-GiST 不把 NULL 存在主樹裡，而是另建一棵樹，其根位於第二個索引頁面。

因此前三個頁面的意義永遠固定：metapage、主樹的根、NULL 值之樹的根。

returnable 與 distance_orderable 皆為 t，因此此索引可用於 index-only scan，也支援最近鄰搜尋（運算子類別中的 <-> 排序運算子）。

但一般而言，運算子類別不一定要在葉頁面存放完整的值，它可以改以資料表重新檢查。這讓 PostGIS 得以把 SP-GiST 索引用於可能很大的幾何值。

點的 k-d 樹#

平面上的點也能用另一種分割方式索引：把平面切成兩個子區域，而非四個。這由 kd_point_ops 運算子類別實作：

=> CREATE INDEX airports_kd_idx ON airports_big
USING spgist(coordinates kd_point_ops);

分割方式為：

1. 選一個 Y 軸座標（範例中代表緯度），把平面切成上下兩個子區域
2. 對每個子區域，選一個 X 軸座標（經度），切成左右兩個子區域
3. 持續交替水平與垂直分割，直到每個部分的點都塞得進單一索引頁面

這樣建出的樹，所有內部節點都只有兩個子節點。此方法可輕易推廣到任意維度的空間，因此這類樹常被稱為 k 維（k-d）樹。

字串的基數樹#

SP-GiST 的 text_ops 運算子類別實作了字串的基數樹。這裡內部節點的前綴真的是前綴——所有子節點字串共有的開頭部分。

• 指向子節點的指標，以前綴之後第一個位元組標示
• 子節點存放前綴之後的部分與標籤；葉節點只保留後綴
• 要重建葉頁面中索引鍵的完整值，只需從根節點起把所有前綴與標籤串接起來

為求清晰以單一字元表示前綴，但這只在單位元組編碼下成立。一般而言運算子類別把字串當作位元組序列處理；此外前綴還可取數個具特殊語意的值，因此實際上每個前綴分配了兩個位元組。

以下是建在數個人名上的基數樹：

運算子類別#

text_ops 支援序數型別（含文字字串）常用的比較運算子：

 oprname |      oprcode     | amopstrategy
−−−−−−−−−+−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−
 ~<~     | text_pattern_lt |            1
 ~<=~    | text_pattern_le |            2
 =       | texteq          |            3
 ~>=~    | text_pattern_ge |            4
 ~>~     | text_pattern_gt |            5
 <       | text_lt         |           11
 <=      | text_le         |           12
 >=      | text_ge         |           14
 >       | text_gt         |           15
 ^@      | starts_with     |           28
(10 rows)

=> CREATE INDEX tickets_spgist_idx ON tickets
  USING spgist(passenger_name);
=> EXPLAIN (costs off) SELECT *
FROM tickets
WHERE passenger_name LIKE 'IVAN%';
                        QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Bitmap Heap Scan on tickets
   Filter: (passenger_name ~~ 'IVAN%'::text)
   −> Bitmap Index Scan on tickets_spgist_idx
       Index Cond: ((passenger_name ~>=~ 'IVAN'::text) AND
       (passenger_name ~<~ 'IVAO'::text))
(5 rows)

若你搭配「C」以外的定序使用一般運算子 >= 與 <，索引將形同無用——因為它處理的是位元組而非字元。

對於這類前綴搜尋，運算子類別自 PostgreSQL 11 起提供更合適的 ^@ 運算子：

=> EXPLAIN (costs off) SELECT *
FROM tickets
WHERE passenger_name ^@ 'IVAN';
                     QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Bitmap Heap Scan on tickets
   Recheck Cond: (passenger_name ^@ 'IVAN'::text)
   −> Bitmap Index Scan on tickets_spgist_idx
       Index Cond: (passenger_name ^@ 'IVAN'::text)
(4 rows)

基數樹的表示法有時會比 B-tree 精簡許多，因為它不保留完整的值，而是在走訪樹時按需重建。

搜尋#

以在 names 表上執行下列查詢為例：

SELECT * FROM names
WHERE name ~>=~ 'VALERIY'
  AND name ~<~ 'VLADISLAV';

儘管這個查詢用的是 B-tree 常見的大於、小於運算子，SP-GiST 的範圍搜尋效率低得多。在 B-tree 中，只需下降到範圍的一個邊界值，接著掃描葉頁面串列即可。

插入#

點的運算子類別，其 choose 函式總能把新值導入某個既有子區域（象限或某一半）。但基數樹並非如此：新值可能不符合任何既有前綴，此時內部節點必須被分裂。

以把名字 VLADA 加進已建好的樹為例：

1. choose 函式順利從根下降到下一個節點（V + L），但值剩下的部分 ADA 不符合 ADI 前綴。節點必須一分為二：其中一個結果節點含有前綴的共同部分（AD），前綴剩餘的部分則往下移一層

   

2. 接著在同一節點再次呼叫 choose 函式。前綴此時已對應到該值，但沒有帶合適標籤（A）的子節點，因此函式決定建立這樣一個節點

屬性#

存取方法與索引層級的屬性上面已述，為所有類別共通。多數欄位層級屬性也維持不變：

         name       | pg_index_column_has_property
−−−−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 returnable         | t
 distance_orderable | f
(2 rows)

儘管被索引的值並未明確存放在樹中，index-only scan 仍然受支援——因為值會在從根走訪到葉的過程中被重建。

至於距離運算子，字串沒有定義，因此此運算子類別不提供最近鄰搜尋。

其他資料型別#

SP-GiST 的運算子類別不限於上述的點與文字字串。

幾何型別：

• box_ops 運算子類別為矩形實作四元樹。矩形以四維空間中的點表示，因此該區域被切成十六個分割
• poly_ops 類別（PostgreSQL 12 起）可索引多邊形。它是模糊運算子類別：實際上與 box_ops 一樣使用邊界框而非多邊形，再以資料表重新檢查結果

該選 GiST 還是 SP-GiST，主要取決於待索引資料的性質。例如 PostGIS 文件建議：重疊嚴重的物件（俗稱「義大利麵資料」，spaghetti data）用 SP-GiST。

範圍型別：range_ops 運算子類別提供範圍的四元樹。一個區間以二維點定義：X 軸代表下界，Y 軸代表上界。

網路位址型別：對 inet 資料型別，inet_ops 運算子類別實作了基數樹。