在 Day 13 我們介紹了 GIN 與 GiST 兩種適合全文搜尋的 Index，而 GiST 事實上也能幫忙加快搜尋空間範圍的查詢。前一陣子在讀 System Design 的時候，假如在設計查詢附近店家的功能，我們會需要利用使用者的位置（可能是經緯度），來查詢某個經緯度區間內的所有店家。

如果我們在資料庫內存有所有店家的經緯度資訊，最直觀的查詢方式是用 lat & long 兩個欄位的範圍，找出使用者附近的所有店家。但是這樣我們找位置時，是使用兩個欄位一起去查詢，當同時間的使用者很多時，查詢速度是不是可能很慢？

在我們需要查詢像是「經緯度區域」這類有方向性與範圍限制的資料時，GiST 能提供比 B-Tree 更有效的查詢方式。今天我們就透過一個簡單的例子，說明如何使用 GiST 建立適合經緯度查詢的 Index。

使用 B-Tree + lat / long

首先先用 lat & long 兩個欄位建立 B-Tree Index 的方式，看一下需要花費的查詢時間。

1. 建立儲存商店位置的 table

CREATE TABLE locations (
  id serial PRIMARY KEY,
  name text,
  lat double precision NOT NULL,
  long double precision NOT NULL
);

2. 塞入 100,000 筆資料

INSERT INTO locations (name, lat, long)
SELECT 
  'Location ' || g,
  21.9 + random() * (25.3 - 21.9),   -- 緯度：約 21.9 ~ 25.3
  120.0 + random() * (122.0 - 120.0) -- 經度：約 120.0 ~ 122.0
FROM generate_series(1, 50000) AS g;

3. 建立 B-Tree Index

CREATE INDEX idx_lat ON locations (lat);
CREATE INDEX idx_long ON locations (long);

4. 找出特定範圍的點（經度 25.05~25.07 & 緯度 121.58~121.60）

EXPLAIN ANALYZE
SELECT * FROM locations
WHERE lat BETWEEN 25.05 AND 25.07
  AND long BETWEEN 121.58 AND 121.60;

使用 B-tree 之後的執行速度是 3.3ms。這個方法將 lat & long 加上 B-Tree Index 之後，分別找了符合 lat 範圍的資料，再去找符合 long 範圍的資料，最後將這兩個重疊的資料回傳。

這個方法有可能有改善的空間嗎？那就再來試試看 SP-GiST～

用 point 搭配 GiST

透過 PostgreSQL 支援內建的 point 類型，我們可以組合 lat / long 作為二維座標，再建立 GiST Index。

1. 加入 pos 欄位作為空間位置

ALTER TABLE locations ADD COLUMN pos point;

-- 將 lat, long 計算成 pos
UPDATE locations SET pos = point(long, lat);

2. 建立 GiST Index

CREATE INDEX idx_locations_pos_gist ON locations USING gist (pos);

3. 查詢跟剛剛一樣的指定區域（經度 25.05~25.07 & 緯度 121.58~121.60）

EXPLAIN ANALYZE
SELECT * FROM locations
WHERE pos <@ box '((121.5, 25.0), (121.6, 25.1))';

確實速度變快了，從 3.3 ms 變為 0.2 ms！

SP-GiST

除了 GiST 之外，還有另外一個 Index 叫做 SP-GiST，（Space-Partitioned Generalized Search Tree），相對於 GiST 的平衡樹（balanced tree），SP-GiST 的資料結構是非平衡的分割樹（partitioned search tree）像是 Quadtree、k-d tree、radix tree。

SP-GiST supports partitioned search trees, which facilitate development of a wide range of different non-balanced data structures, such as quad-trees, k-d trees, and radix trees (tries).

以 Quadtree 來說，Quadtree 是一種專門用來處理二維空間資料（例如地圖座標）的樹狀結構，它的特性是每個節點最多有四個子節點。當一個區域的資料太多時，就會遞迴地把該區域分成四塊，進一步管理，特別適合用來做區域查詢（range query）。

The common feature of these structures is that they repeatedly divide the search space into partitions that need not be of equal size. Searches that are well matched to the partitioning rule can be very fast.

不論是 GiST 還是 SP-GiST，兩者都適合在處理複雜的非傳統資料型別、特別是地理空間資料的場景。通常空間資料的需求，還會搭配 PostgreSQL 空間資料庫擴充套件 PostGIS，來做到更完整的儲存、查詢與分析的功能。

重點回顧

• 用 B-Tree 處理空間範圍查詢效率低，因為它需要分別處理多個欄位。
• GiST / SP-GiST 能更有效處理空間範圍查詢。
• 處理空間資料時，GiST 或 SP-GiST 通常會搭配 PostGIS，可以實現更全面的 GIS 功能。

參考資料

https://www.postgresql.org/docs/current/spgist.html#SPGIST-BUILTIN-OPCLASSES