数据库索引底层结构

数据库索引的底层结构主要取决于数据库类型（关系型 / NoSQL）和具体实现，但核心目标都是：加速数据检索、减少磁盘 I/O。下面按主流结构系统讲解。

一、为什么需要索引结构？

• 数据存储在磁盘，顺序扫描代价高
• 索引本质是有序的数据结构 + 定位机制
• 好的索引结构要兼顾：
  • 查询效率（O(log n) 或接近）
  • 插入/删除效率
  • 磁盘友好（减少随机 I/O）

二、关系型数据库主流索引结构

1. B+ Tree（最常见）

代表：MySQL InnoDB、PostgreSQL、Oracle、SQL Server

结构特点

• 多路平衡查找树（非二叉树）
• 所有数据都在叶子节点
• 叶子节点通过双向链表连接
• 非叶子节点只存键值（索引）

示例逻辑

        [10, 20]
       /    |    \
 [1-9]  [10-19] [20-29]

优点

• 树矮（阶数大，磁盘块存得多）
• 范围查询极快（叶子链表）
• 适合磁盘存储（一页一节点）

为什么不是 B Tree？

• B Tree 数据在各层，范围查询差
• B+ Tree 非叶子不存数据 → 单页能放更多键

2. Hash 索引

代表：MySQL Memory 引擎、部分 NoSQL

结构

• 哈希表
• key → 桶 → 数据位置

优点

• 等值查询 O(1)

缺点

• 不支持范围查询
• 哈希冲突
• 不适合排序

3. R Tree（空间索引）

用于：地理信息、多维数据

• 矩形边界嵌套
• 如：PostGIS、MySQL 空间索引

4. 全文索引（倒排索引）

用于：LIKE ‘%xx%’、搜索引擎

• 词 → 文档列表
• Elasticsearch / MySQL FULLTEXT

三、InnoDB 索引的特别之处（重点）

1. 聚簇索引（Clustered Index）

• 主键即数据
• 叶子节点存整行数据
• 如果没有主键：
  • 用唯一索引
  • 否则隐式生成 row_id

2. 二级索引

• 叶子节点存：索引列 + 主键值
• 回表：通过主键再查聚簇索引

四、NoSQL 常见索引结构

五、LSM Tree（写密集场景）

代表：HBase、Cassandra、RocksDB

核心思想

• 写内存（MemTable）
• 定期刷盘（SSTable）
• 后台合并（Compaction）

优点

• 写入极快
• 适合日志、时序数据

缺点

• 读可能多次
• 用 Bloom Filter 优化

六、一句话总结

大多数关系型数据库用 B+ Tree，因为它最平衡；
写多读少用 LSM Tree；
等值用 Hash；
搜索用倒排。

如果你愿意，我可以进一步讲：

• B+ Tree 插入/分裂过程
• 为什么 MySQL 用 B+ 而不是红黑树
• 索引失效场景
• 如何设计高效索引