EP 6.1：如何在毫秒级搜索10亿行

Source: Dev.to

问题：全表扫描

想象一个拥有 100 万本书的图书馆。如果你想找《了不起的盖茨比》，而这些书没有任何组织，你只能一本一本地查看，直到找到为止。在数据库中，这就是 全表扫描（线性时间复杂度）。

随着数据库从几千行增长到几百万行，你的 SELECT 查询会变得非常慢，最终超时并导致应用崩溃。

索引

索引是一种独立的数据结构，它存储列数据的排序版本，并附带指向主表中实际行的指针（引用）。大多数关系型数据库（如 PostgreSQL 和 MySQL）使用 B‑Tree（平衡树）结构。

B‑Tree 索引的工作原理

1. 根节点 – 搜索从顶部节点开始。
2. 决策 – 系统将你的值（例如 User ID = 505）与节点中的值进行比较，并决定向左还是向右走。
3. 叶子节点 – 你到达树的底部，那里包含数据在磁盘上的精确位置。

这将搜索从 O(n) 降至 O(log n)。搜索 100 万行突然只需要大约 20 次“跳转”。

类比

把索引想象成教科书背后的索引：

• 你查找关键词 “负载均衡”。
• 索引告诉你它在第 42 页。
• 你直接跳到第 42 页，而不必阅读前面的 41 页。

索引类型

聚集索引（主键）

• 表本身在物理上按照此顺序排序。
• 每个表只能有 一个 聚集索引。

非聚集索引

• 你在 email、created_at 等列上额外创建的索引。
• 它们存放在与主数据分离的“文件夹”中，并指向聚集索引。

复合索引

如果你的查询总是类似于：

WHERE country = 'India' AND city = 'Mumbai'

一个同时覆盖 两个 列的单一索引要比数据库尝试合并两个独立索引快得多。

专业提示： 复合索引的列顺序很重要。(city, country) 与 (country, city) 并不相同。

权衡

• 读写平衡： 索引加快读取（SELECT），但会减慢写入（INSERT/UPDATE/DELETE）。
• 写入惩罚： 每次插入新行时，数据库必须在与该表关联的每棵 B‑Tree 中找到正确位置并重新平衡树。
• 存储成本： 索引占用磁盘空间；在超大表上，索引有时会比数据本身更大。

实践指南

• 为外键建索引： 这会显著加快 JOIN 操作。
• 覆盖查询： 如果你的索引已经包含 SELECT 所需的全部数据（例如只索引 email 并且只查询 email），数据库甚至不需要访问主表。这称为 仅索引扫描（index‑only scan）。
• 避免低基数列： 对像 gender（仅有 M/F/O 三个值）这样的列建索引通常没有意义，因为数据库仍需扫描表的大部分。
• 使用 EXPLAIN ANALYZE 监控： 在添加索引之前，用 EXPLAIN 运行查询，查看数据库是执行顺序扫描还是使用已有索引。

最佳实践

索引是提升数据库性能的最强大工具，但使用它们要像加盐一样：放太多会毁掉整道菜。

1. 首先为 WHERE 子句、JOIN 条件和 ORDER BY 语句中使用的列建立索引。
2. 监控写入延迟，并根据需要进行调整。