索引算法全景对比与选型指南

分割线

索引类型全景对比

如果把索引看成一个「数据定位算法」，那么不同索引本质上是在 空间占用、写入成本、查询能力、存储介质特性 之间做权衡.

索引类型等值查询范围查询排序模糊搜索写入成本空间占用典型数据库
Hash⭐⭐⭐⭐⭐❌❌❌⭐⭐⭐⭐⭐Redis、Memcached
B-Tree⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐❌⭐⭐⭐⭐⭐⭐MySQL、PostgreSQL
B+Tree⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐❌⭐⭐⭐⭐⭐⭐InnoDB、SQLite
Bitmap⭐⭐⭐⭐⭐❌❌❌⭐⭐⭐⭐⭐⭐Oracle、ClickHouse
FullText⭐⭐⭐❌❌⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐Elasticsearch、MySQL
Trie⭐⭐⭐❌⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐搜索引擎、输入法
R-Tree⭐⭐⭐⭐⭐⭐❌❌⭐⭐⭐⭐⭐GIS 数据库
LSM Tree⭐⭐⭐⭐⭐⭐⭐⭐⭐❌⭐⭐⭐⭐⭐⭐⭐⭐RocksDB、LevelDB
HNSW⭐⭐⭐⭐❌❌向量检索⭐⭐⭐⭐⭐⭐⭐Milvus、Qdrant
IVF-PQ⭐⭐⭐❌❌向量检索⭐⭐⭐⭐⭐⭐FAISS、Milvus

这张表是指南性质的对照表，不是评分榜。实际选型时还要结合数据量、读写比例、硬件条件来定.

分割线

关系型数据库与 B+Tree

为什么关系型数据库基本都选 B+Tree

核心原因：机械硬盘时代的物理限制.

访问一次机械硬盘数据 = 寻道时间 + 旋转延迟 + 读取时间:

操作HDD
寻道5~10ms
旋转2~5ms
读取 4KB0.01ms

95% 以上时间浪费在寻道。因此数据库设计目标变成：尽量减少磁盘访问次数。

于是出现了 B-Tree 系列.

B-Tree

阶数为 4 的示例:

       [20]
    /        \
[5,10]      [30,40]

特点: 数据可以存储在所有节点，查询过程中可能提前命中.

缺点: 叶子节点不连续。范围查询 where age between 20 and 50 需要不停回溯树结构，效率低.

B+Tree

B+Tree 的改进:

         [20]
       /      \
    [10]     [30]

叶子:
[1,2,3,4]
    ↓
[5,6,7,8]
    ↓
[9,10,11]

真正数据全部在叶子节点。内部节点只存 key + child pointer.

因此同样 4KB 页，B-Tree 只能存约 100 个 key，B+Tree 能存 约 300 个 key，树高明显降低.

以 1000 万行数据为例:

Root
 └─ Level1
     └─ Level2
         └─ Leaf

只需 4 次 IO 就能定位到目标.

MySQL InnoDB、PostgreSQL、SQLite 默认全部采用 B+Tree.

为什么 HDD 特别适合 B+Tree

假设页大小为 16KB，一次读取获取一个节点，节点里可能有上千个 key.

一次随机 IO = 获得上千个索引信息

极大减少寻道次数。这正是 B+Tree 成为磁盘数据库霸主的原因.

分割线

SSD 时代与 LSM Tree

SSD 出现后发生了什么

SSD 的性能特征:

操作HDDSSD
随机读10ms0.05ms
顺序读200MB/s7GB/s
IOPS1001,000,000+

随机读代价骤降，B+Tree 不再是唯一选择。LSM Tree 开始流行.

LSM Tree

代表实现: RocksDB、LevelDB、TiKV.

核心思想: 不要立即更新磁盘.

写入流程:

Memory (MemTable)
  ↓ Flush
SSTable (Level 0)
  ↓ Compaction
SSTable (Level 1)
  ↓ Compaction
SSTable (Level 2)

结构分层:

Memory
  ↓
SST1
SST2
SST3
SST4

写入几乎顺序，对 SSD 极其友好.

B+Tree vs LSM Tree

项目B+TreeLSM
随机读⭐⭐⭐⭐⭐⭐⭐⭐
范围查询⭐⭐⭐⭐⭐⭐⭐⭐
写入⭐⭐⭐⭐⭐⭐⭐⭐
更新⭐⭐⭐⭐⭐⭐⭐
HDD 适配⭐⭐⭐⭐⭐⭐
SSD 适配⭐⭐⭐⭐⭐⭐⭐⭐⭐
OLTP⭐⭐⭐⭐⭐⭐⭐⭐
日志系统⭐⭐⭐⭐⭐⭐⭐

B+Tree 读快写慢，LSM Tree 写快读慢。选型就是在这两者之间找平衡.

分割线

专用索引

Hash 索引

原理:

hash(key) → bucket → value
-- O(1) 查询
SELECT * FROM users WHERE user_id = 1001;

直接通过 hash 函数定位到桶，速度极快.

致命缺点: 不支持范围查询.

-- ❌ Hash 索引完全没法处理
SELECT * FROM users WHERE id > 1000;

hash 后的结果毫无顺序关系，只能做等值查询.

Bitmap 索引

适合低基数字段: 性别、地区、状态等.

构造方式 — 每个取值一个位图:

男: 101001001
女: 010110110

查询:

SELECT * FROM users WHERE gender = '男' AND region = '浙江';

直接位运算:

101001001
& 位图(浙江)
→ 结果

速度极快。常见于 ClickHouse、数据仓库、OLAP 场景.

全文索引 (Inverted Index)

搜索引擎的核心机制.

假设三篇文章:

Doc1: 我爱中国
Doc2: 中国制造
Doc3: AI中国

建立倒排索引:

中国 → [1,2,3]
制造 → [2]
AI   → [3]

结构:

Term → Posting List → Document IDs

查询"中国 AI":

[1,2,3] ∩ [3] = [3]

应用: Elasticsearch、Solr、Lucene，以及 PostgreSQL 的 GIN、MySQL FullText.

向量索引 (HNSW / IVF-PQ)

传统 B+Tree 和 Hash 都要求有明确的 key，但向量查询是"找最相似"：

768 维向量 → 最近邻 (TopK)

没有明确 key，需要近似最近邻索引 (ANN).

HNSW

代表: Milvus、Qdrant.

结构:

Layer3
  ●

Layer2
 ● ● ●

Layer1
●●●●●●●

从高层跳跃式逼近目标，复杂度约 O(log N).

代价是内存巨大。经验值: 1TB 向量数据约需 1.3~2TB RAM.

IVF-PQ

用于超大规模向量场景，通过量化压缩降低内存占用。FAISS 原生支持.

比 HNSW 省内存但召回率略低，适合"足够好"而非"必须最精确"的场景.

分割线

场景选型指南

场景最优索引
MySQL 业务库B+Tree
PostgreSQL 业务库B+Tree
Redis 缓存Hash
日志系统LSM
时序数据库LSM
ClickHouse 分析库Bitmap + MergeTree
Elasticsearch 搜索Inverted Index
GIS 地图R-Tree
Milvus 向量库HNSW
超大规模向量库IVF-PQ
500GB 论文 RAGHNSW + SSD 缓存

对于 500GB 论文做 RAG 的场景，实际上已经不是传统数据库索引问题，而是:

原始 PDF → Chunk → Embedding → 向量索引 (HNSW) → TopK 召回

最贵的资源不是 SSD，而是 HNSW 图索引占用的内存。很多生产环境会采用混合架构:

  • 文档存储: PostgreSQL / 对象存储
  • 元数据索引: B+Tree
  • 向量索引: HNSW
  • 冷数据层: SSD
  • 热层缓存: RAM

单一条索引解决不了所有问题，现实世界都是组合拳.

分割线

借物表

暂无.