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;