PostgreSQL/雜湊索引
PostgreSQL 使用兩種基本策略來實現 *雜湊索引*。首先，*雜湊函式* 將任何型別和長度的列值對映到 32 位固定大小的 *雜湊值*。這些雜湊值與它們源自行的 TID 一起構成了雜湊索引的基本組成部分。其次，一個精心設計的演算法確保索引檔案的大小在新增索引條目時平滑增長（即，每次只增長一小部分頁）。因此，它是一種 可擴充套件雜湊。
為了節省空間，雜湊索引不儲存原始列值，只儲存計算後的雜湊值。這有一些影響。計算後的雜湊值的排序與原始值的排序沒有關係。因此，這種索引型別只能支援 `=` 運算子，而不能支援其他比較運算子，例如 `<` 或 `>`。此外，還存在重複項的風險。兩個不同的列值可能會生成相同的雜湊值。這是不可避免的，因為可能的列值（**任何** 長度）遠多於可能的雜湊值（**固定** 大小）。因此，在根據找到的 TID 讀取行後，需要重新評估堆中的列值。
在大多數情況下 - 特別是對於長列值 - 雜湊索引的大小比 B 樹索引的大小更小。此外，讀取和寫入命令的執行時間通常更短。
雜湊索引的核心部分由所謂的 *桶* 組成。它們是頁面的雙向連結串列，儲存著 *桶條目*。第一個桶頁面可以非常快地訪問，因為它的編號與雜湊值中的某些位相關聯。
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;
在建立和維護雜湊索引期間，會執行以下步驟
- 讀取列值及其原始行的 TID。
- *雜湊函式* 根據原始列值計算一個 *雜湊值*。它的大小始終為 32 位 - 與資料型別和資料長度無關。
- 雜湊值和 TID 的組合構成一個 *桶條目*。
- 存在多個 *桶*，用來儲存桶條目。雜湊值中的某些位決定了哪個桶擁有並接收桶條目。
- 桶包含一個 *主桶頁面* 以及可選的 *溢位桶頁面*。在桶中，頁面透過雙向連結串列連線在一起。
- 如果主桶頁面及其所有溢位頁面都沒有空閒插槽來存放新的桶條目，就會建立一個新的溢位頁面。
- 計算現有桶數量與所有桶條目數量的比率。根據這個值和索引選擇的 `fillfactor`，按需建立新的桶。
*元資料頁面* 包含有關索引的統計資料：桶和桶條目的數量、指向桶的連結陣列 (hashm_spares) 等等。
*主桶頁面* 和 *溢位桶頁面* 包含指向堆中行的雜湊值和 TID 對。
*點陣圖頁面* 包含一個位數組，指示可能存在未使用的溢位頁面（在對相應行執行 DELETE 操作後）。這些頁面可以被其他桶重新使用。
DROP TABLE IF EXISTS t6;
-- create a table with a UUID column and some text
CREATE TABLE t6 (id INTEGER, pseudo_id UUID, col TEXT);
-- insert data
-- INSERT INTO t6 VALUES (1, md5('1')::uuid, 'First row.');
-- ...
-- insert many rows
INSERT INTO t6 VALUES
(generate_series(10, 10000, 1),
md5(generate_series(10, 10000, 1)::text)::uuid,
'abc abc abc abc abc abc abc abc abc abc abc');
-- create a HASH index
CREATE INDEX t6_hash_idx ON t6 USING HASH(pseudo_id) WITH (fillfactor = 50);
-- inspect size
SELECT pg_size_pretty(pg_total_relation_size('t6_hash_idx'));
-- inspect physical pages
-- page type of any page
SELECT hash_page_type(get_raw_page('t6_hash_idx', 0));
-- infos out of meta page
\x
SELECT * FROM hash_metapage_info(get_raw_page('t6_hash_idx', 0));
-- infos out of primary bucket or overflow bucket pages
SELECT * FROM hash_page_stats(get_raw_page('t6_hash_idx', 1));
SELECT * FROM hash_page_items(get_raw_page('t6_hash_idx', 1)) LIMIT 20;