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-树更具优势。