索引

分类: 编码创建于: 6/18/2025

好的，我们来深入了解一下数据库索引的原理。

什么是索引？

最简单的类比就是一本书的目录或字典的部首查字表。

  • 没有目录的书: 你需要从头到尾翻阅每一页才能找到你想要的信息。
  • 有目录的书: 你可以快速通过目录找到对应的章节页码，然后直接翻到那一页，大大节省时间。

在数据库中，索引就是一种特殊的数据结构，它存储了表中一列或多列的值，并维护这些值到对应数据行物理位置的映射关系。它的主要目的是提高数据检索的速度。

索引的基本原理

当你在某个列上创建索引时，数据库系统并不会改变原始数据的存储方式。它会额外创建一个独立的数据结构，通常是**B-Tree（B-树）**或其变种（如 B+树），来存储索引列的值和指向原始数据行的指针。

1. 常见索引结构：B-Tree (B树) 和 B+Tree (B+树)

这是最常见和最广泛使用的索引数据结构。

  • B-Tree (B树):

    • 特点: 所有节点（包括非叶子节点和叶子节点）都存储键值和指向数据记录的指针。
    • 优点: 查找时，一旦找到键值，就可以立即获取数据，可能比B+树的平均查找路径短。
    • 缺点: 非叶子节点也存储数据指针，导致单个节点能存储的键值数量减少，树的高度可能略高；范围查询效率不如B+树，因为叶子节点之间没有指针相连。

  • B+Tree (B+树) - PostgreSQL、MySQL (InnoDB) 等关系型数据库主要使用：

    • 特点:
      • 所有数据都存储在叶子节点上：非叶子节点只存储键值用于导航，不存储数据指针。
      • 叶子节点之间通过指针相连：形成一个有序链表。
      • 非叶子节点中的键值是其子节点中的最大或最小键值。
    • 查找过程: 从根节点开始，根据要查找的键值，遍历非叶子节点，最终到达叶子节点。在叶子节点中找到对应的键值，然后通过叶子节点存储的数据指针获取完整的数据行。
    • 优点:
      • 更少的磁盘I/O: 非叶子节点不存储数据指针，可以存储更多的键值，从而降低树的高度，减少磁盘I/O次数。这是最重要的优势，因为磁盘I/O是数据库操作中最慢的部分。
      • 高效的范围查询: 由于叶子节点通过指针相连，一旦找到范围的起始点，就可以通过顺序遍历叶子节点链表来高效地获取所有范围内的记录。
      • 更适用于磁盘存储: B+树的结构使其对磁盘块的利用率更高。
    • 缺点: 查找特定值时，可能需要遍历到叶子节点才能获取数据（B树可能在非叶子节点找到）。

2. 索引的存储

索引通常以文件形式存储在磁盘上，与表数据文件是分开的。当数据库启动时，部分索引可能会被加载到内存中以加速访问，但完整的索引结构仍然存在于磁盘上。

索引如何提高查询速度？

当执行 SELECT * FROM users WHERE username = 'john_doe'; 这样的查询时：

  1. 没有索引: 数据库需要执行全表扫描 (Full Table Scan)。它会从磁盘上读取 users 表的每一行数据，然后逐一检查 username 列是否等于 'john_doe'。这在表很大的时候会非常慢，因为需要大量的磁盘I/O。

  2. 有索引 (username 列上有索引):

    • 数据库会先访问 username 列的索引（B+树）。
    • 通过索引的快速查找机制（类似于二分查找），它能迅速定位到 'john_doe' 这个键值在索引中的位置。
    • 索引的叶子节点存储了 'john_doe' 对应的数据行的物理地址（或主键值，如果是聚集索引）。
    • 数据库根据这个地址直接跳转到磁盘上对应的位置，读取该行数据。
    • 这大大减少了需要读取的数据量和磁盘I/O，从而显著提高了查询速度。

索引的分类

  • 主键索引 (Primary Key Index):
    • 为表的主键自动创建的索引。
    • 特点：唯一且非空，通常是聚集索引（后面会解释）。
  • 唯一索引 (Unique Index):
    • 确保索引列的值是唯一的。如果该列插入重复值，会报错。
    • 可以包含 NULL 值（如果列允许 NULL）。
  • 普通索引 (Non-Unique Index / B-Tree Index):
    • 最常见的索引类型，允许重复值。
  • 复合索引 (Composite Index / Multi-Column Index):
    • 在多个列上创建的索引，例如 (col1, col2, col3)。
    • 查询时，只有当查询条件覆盖了索引的最左前缀时，复合索引才能被有效利用。例如，WHERE col1 = 'A' 或 WHERE col1 = 'A' AND col2 = 'B' 可以使用 (col1, col2, col3) 索引，但 WHERE col2 = 'B' 则不能直接使用。
  • 全文索引 (Full-Text Index):
    • 用于文本内容的模糊搜索，如 LIKE '%keyword%'。
  • 哈希索引 (Hash Index):
    • 基于哈希表实现，只适用于等值查询（=），不能用于范围查询或排序。写入速度快，但适用场景有限。PostgreSQL 提供了哈希索引。
  • 表达式索引 (Expression Index):
    • 基于某个函数的计算结果或表达式创建索引，例如 CREATE INDEX ON users ((lower(email)));。

聚集索引 vs 非聚集索引 (主要针对某些数据库，如SQL Server、MySQL的InnoDB)

  • 聚集索引 (Clustered Index):
    • 它决定了数据行在磁盘上的物理存储顺序。
    • 一个表只能有一个聚集索引。
    • 通常，主键会自动成为聚集索引。
    • 优点: 范围查询效率极高，因为它物理上是连续的。直接从索引叶子节点就可以获取所有数据，无需再次回表。
    • 缺点: 数据插入、更新和删除可能涉及到物理页的重排，开销较大。
  • 非聚集索引 (Non-Clustered Index):
    • 索引的逻辑顺序与数据行的物理存储顺序无关。
    • 一个表可以有多个非聚集索引。
    • 非聚集索引的叶子节点存储的是索引列的值和指向实际数据行的行定位符 (Row Locator)，这个定位符通常是聚集索引的键值或者物理地址。
    • 缺点: 查询时，如果仅仅通过非聚集索引找到了键值，还需要一次“回表”操作，即根据行定位符再次去查找原始数据行，这会增加一次I/O。

PostgreSQL 的索引机制：
PostgreSQL 默认的所有索引都是非聚集索引。这意味着即使是主键索引，它也不会改变数据的物理存储顺序。PostgreSQL 的数据文件 (.sql 文件或数据目录下的文件) 是以堆（heap）结构存储的，记录的顺序通常是插入的顺序。所有索引都独立于数据存储，通过存储 (键值, 行ID/TID) 的方式来指向堆中的实际数据。

索引的缺点

虽然索引能显著提高查询速度，但它也有一些缺点：

  1. 占用磁盘空间: 索引本身是数据结构，需要额外的磁盘空间来存储。
  2. 降低写入性能: 当对表进行 INSERT、UPDATE、DELETE 操作时，除了修改表中的数据，还需要同步更新相关的索引结构。这会增加写入操作的开销。
  3. 查询优化器开销: 数据库的查询优化器在执行查询时，需要评估是否使用索引，以及使用哪个索引。这本身也需要一定的计算开销。
  4. 维护成本: 索引需要定期维护，例如重建（REINDEX）以减少碎片，虽然现代数据库通常有较好的自动管理机制。

总结

索引是数据库性能优化的基石。理解其底层原理有助于你更合理地设计数据库模式，并为关键查询创建恰当的索引，从而在查询效率和写入性能之间取得平衡。