PostgreSQL/索引
關係型資料庫系統儲存大量資料。只有當能夠快速檢索到單個數據片段時，它們的值才會變得明顯。例如，在一個包含一億條記錄的電話簿中，對特定電話號碼進行的簡單查詢平均需要讀取五千萬條記錄。幸運的是，智慧演算法可以顯著減少必要的讀取操作。在本例中，二分查詢 將把讀取次數減少到最大 27 次。與使用更快的硬體相比，使用智慧演算法效率更高，尤其是在處理海量資料時。
在我們資料庫的案例中，這種演算法的實現是基於額外的結構，這些結構以特定方式重複原始資料的部分。它們被稱為索引，當然，它們也帶來了一些開銷。它們佔用磁碟和記憶體空間；它們會產生額外的工作量，例如，排序，以及每當原始資料發生變化時，它們必須相應地進行維護。
如前所述，它們的主要目的和最大優勢是加速查詢——在識別行以及對結果行集進行排序方面。除此之外，它們還支援一些約束，例如唯一性。
如果存在索引，系統不一定使用它們。因為系統在執行查詢之前會對其進行最佳化，它有時會決定忽略現有索引，而選擇執行全表掃描。如果表非常小，或者檢索值的選取性非常低，並且將返回現有行的很大一部分，就會出現這種情況。
PostgreSQL 提供了一些擴充套件機制。除了其他功能外，還可以向系統新增新的資料型別，並將它們整合到現有的索引型別中。除此之外，還可以開發特定於應用程式的運算子，以滿足專業應用程式的需求，例如，影像或音樂的分類、任意物件的聚類、股票價格中的模式檢測等等。GIN[1]、BRIN[2]、GiST[3] 和 SP-GiST[4] 提供了一個介面（某種模板），允許實現索引輔助的特定於領域的動作。這種技術被稱為訪問方法。只有 B-樹和雜湊是傳統索引，沒有這種擴充套件機制。
B-樹（平衡樹）是預設的索引型別。它適用於數字或短字串經常作為WHERE子句的一部分的用例。可能的運算子是通常的算術運算子：<，<=，=，>，>=。
-- create a B-Tree index: key word 'USING' can be omitted
CREATE INDEX test_idx ON table_1 (column_1);
-- equivalent syntax:
CREATE INDEX test_idx ON table_1 USING BTREE(column_1);
-- use it
SELECT * FROM table_1 WHERE column_1 BETWEEN 5 AND 6;
GIN（廣義倒排索引）支援可分為較小元件的資料型別，例如陣列元素、文字文件的單詞或 JSON 物件的屬性。我們稱它們為複合資料型別。與 B-樹相反，GIN 不會為完整值生成單個索引條目，而是為每個單個元件生成一個索引條目。
WHERE子句中可用的運算子取決於資料型別
- 陣列：
<@（包含在內），@>（包含），=（等於）和&&（重疊/有一些共同的元素）。 - 文字查詢（詞素）：
@@（包含）。 - JSON：
->（具有給定鍵的 JSON 物件欄位），->>（具有給定鍵的 JSON 物件欄位，作為文字）。
-- create a table with a column that holds an array of integers
CREATE TABLE t2 (id INTEGER, arr INTEGER[]);
-- create a GIN index
CREATE INDEX t2_gin_idx ON t2 USING GIN(arr);
-- use the index
SELECT * FROM t2 WHERE arr @> ARRAY[11];
BRIN（塊範圍索引）是一種結構，可以加速對包含大量行（>百萬）且這些行在資料檔案內以特定物理順序出現的表的查詢。典型的用例是那些某一列包含時間戳或生成的序列號，並且這些號隨著時間的推移很少或從不改變，例如：物聯網資料、計算值、感測器輸出、日誌資訊。
資料檔案中行物理順序與其在感興趣列中的內容之間的相關性來自於INSERT命令的順序和列值的增長：後面的INSERT必須包含相同或更高的值。這種相關性可能會隨著時間的推移而丟失，這是由於後面的UPDATE命令造成的。在這種情況下，BRIN 的優勢可能會消失。
BRIN 的強大功能來自於它只需要很少的空間。對於包含數億行的表，典型的 BRIN 大小僅為幾 KB，可以輕鬆地放入記憶體中。所有其他索引型別都需要更多空間，佔表大小的 25-50% 並不罕見。
-- create a table with a timestamp column
CREATE TABLE t3 (id INTEGER, ts TIMESTAMP);
-- create a BRIN index
CREATE INDEX t3_brin_idx ON t3 USING BRIN(ts);
-- use the index in the usual way
SELECT * FROM t3 WHERE ts = '2022-01-01';
PostgreSQL 使用兩種基本策略來實現雜湊索引。首先，雜湊函式將任何型別和長度的列值對映到大小為 32 位的雜湊值。這些雜湊值以及它們原始行的 TID 是雜湊索引的基本磚塊。其次，一個精心設計的演算法確保索引檔案的大小隨著索引條目的增加而平滑增長（即，一次在少量頁面中增長）。因此，它是一個可擴充套件雜湊。
為了節省空間，雜湊索引不儲存原始列值，而只儲存計算出的雜湊值。這有一些影響。計算出的雜湊值的排序順序與原始值的排序順序沒有關係。因此，這種索引型別只能支援=運算子，而不能支援其他比較運算子，例如<或>。此外，還有重複的風險。兩個不同的列值可能會產生相同的雜湊值。這是不可避免的，因為可能的列值（任何長度）比可能的雜湊值（固定大小）多得多。因此，在根據找到的 TID 讀取行之後，有必要從堆中重新評估列值。
DROP TABLE IF EXISTS t5;
-- create a table with a UUID column and some text
CREATE TABLE t5 (id INTEGER, pseudo_id UUID, col TEXT);
-- insert some rows
INSERT INTO t5 VALUES (1, md5('1')::uuid, 'First row.');
INSERT INTO t5 VALUES (2, md5('2')::uuid, 'Second row.');
INSERT INTO t5 VALUES (3, md5('3')::uuid, 'Third row.');
-- ...
-- insert many rows
INSERT INTO t5 VALUES
(generate_series(10, 10000, 1),
md5(generate_series(10, 10000, 1)::text)::uuid,
'more text more text more text more text more text more text more text');
-- create a HASH index over UUID column
CREATE INDEX t5_hash_idx ON t5 USING HASH(pseudo_id);
-- use the index
SELECT * FROM t5 WHERE pseudo_id = md5('2')::uuid;
-- show index usage
EXPLAIN SELECT * FROM t5 WHERE pseudo_id = md5('2')::uuid;
GiST 代表廣義搜尋樹，並實現了類似於 B-樹的平衡樹結構。這對於所有型別的 B-樹和 R-樹結構都很有用。一些 PostgreSQL 擴充套件使用它們，例如：hstore（鍵值對）、intarray（整數陣列）、ltree（“標籤”如“世界.國家.歐洲.俄羅斯”）、pg_trgm（三元組匹配）等等。
SP-Gist 代表空間分割槽廣義搜尋樹，並實現了非平衡樹結構，主要用於包含相似或相等物件型別的物件型別。這對於四叉樹、k-d 樹、基數樹等等很有用。
上面提到的索引型別和索引訪問方法是每個 PostgreSQL 安裝的組成部分。
一個額外的索引訪問方法是布隆[5]。布隆必須使用PG 的擴充套件機制顯式安裝（在使用這種索引型別之前，必須執行一次CREATE EXTENSION bloom;）。此擴充套件實現了一個布隆過濾器，它在 SQL 語句的WHERE條件中未指定多列索引的第一列的情況下，比 B-樹更具優勢。