创建索引很容易。几乎每个开发者在某个时刻都创建或使用过索引，无论是直接还是间接。但知道索引什么只是方程的一部分。更困难的问题是理解索引如何在底层工作。

索引不是表面层的优化。它是数据结构的问题。索引组织、存储和检索数据的方式直接影响读写操作的性能。不同的数据结构表现不同。

  • 有些可能擅长范围扫描
  • 有些针对精确匹配查找优化
  • 其他专为全文搜索或地理空间查询构建

这些决策影响从查询计划到 I/O 模式再到负载下消耗内存量的一切。

当查询变慢或系统开始与磁盘 I/O 挣扎时，索引结构通常处于问题核心。选择不当的索引格式可能导致低效访问路径、不必要的膨胀或缓慢插入。相反，良好对齐的结构可以将暴力扫描转变为精确查找。

在本文中，我们将介绍支持数据库索引的核心内部数据结构。每个部分将介绍结构如何工作、解决什么问题、在哪里表现最好，以及携带什么限制。

B-Tree 索引

B-Tree 索引使用平衡树结构，其中键和数据指针存在于内部和叶子节点中。它们支持通过有序遍历进行高效的范围和点查询。

工作原理

  • 内部节点包含键和指向子节点的指针
  • 叶子节点包含键和数据指针
  • 树保持平衡，所有叶子节点在同一层级

适用场景

  • 范围查询（BETWEEN、>、<）
  • 排序操作（ORDER BY）
  • 精确匹配查找

限制

  • 对于低基数列效率较低
  • 写入操作需要维护树平衡

B+ Tree 索引

B+ Tree 索引将所有数据指针存储在叶子节点中，而内部节点只包含键来引导搜索。叶子节点链接以通过顺序访问进行快速范围查询。

工作原理

  • 内部节点只包含键（无数据指针）
  • 所有数据指针在叶子节点
  • 叶子节点通过链表连接

适用场景

  • 范围查询（比 B-Tree 更好）
  • 顺序扫描
  • I/O 效率关键场景

限制

  • 单点查找可能比 B-Tree 稍慢
  • 需要额外的叶子节点遍历

Hash 索引

Hash 索引对搜索键应用哈希函数以直接定位包含数据指针的桶。它们针对相等搜索优化，但不适用于范围查询。

工作原理

  • 对键应用哈希函数
  • 直接定位到桶
  • 桶包含指向数据行的指针

适用场景

  • 精确相等查询（=）
  • 主键查找
  • 高基数列

限制

  • 不支持范围查询
  • 哈希冲突可能影响性能
  • 不支持排序操作

Bitmap 索引

Bitmap 索引使用位数组为每个可能值表示列值，允许通过位运算进行快速过滤。它们理想用于低基数分类数据。

工作原理

  • 为每个唯一值创建位图
  • 每个位对应一行
  • 位 = 1 表示该行有此值

适用场景

  • 低基数列（性别、状态等）
  • 数据仓库
  • 复杂布尔查询

限制

  • 高基数列效率低
  • 写入操作昂贵（需要更新多个位图）
  • 不适合 OLTP 系统

Inverted 索引

Inverted 索引将每个唯一术语映射到包含该术语的行 ID 列表，实现快速全文搜索。

工作原理

  • 为每个术语创建条目
  • 每个条目包含文档/行 ID 列表
  • 支持快速术语查找

适用场景

  • 全文搜索
  • 文档检索
  • 关键词搜索

限制

  • 需要额外存储
  • 更新昂贵
  • 不适合精确匹配查询

本文为学习目的的个人翻译，译文仅供参考。

原文链接：Database Index Internals: Understanding the Data Structures。

版权归原作者或原刊登方所有。本文为非官方译本；如有不妥，请联系删除。