数据库索引底层怎么实现

数据库索引的“底层实现”通常可以从数据结构、存储方式、查找过程三个层面来理解。下面以最常见的 B+ 树索引（关系型数据库默认） 为主，并补充 Hash、其他索引类型。

一、最主流：B+ 树索引（MySQL InnoDB / Oracle / PostgreSQL 默认）

1. 为什么用 B+ 树，而不是二叉树或红黑树？

• 数据库数据量大，必须减少磁盘 IO
• B+ 树是多路平衡查找树
  • 树高很低（通常 3~4 层即可存千万级数据）
  • 一次 IO 能读很多 key

2. B+ 树结构（核心特征）

• 非叶子节点：只存 key + 指针（不存数据）
• 叶子节点：
  • 存 key + 数据（或数据行指针）
  • 叶子节点之间用双向链表连接
• 所有查询最终都落到叶子节点

        [10, 20, 30]
       /     |      \
  [1-9]  [11-19]  [21-29]  [31-...]
   ↓        ↓        ↓        ↓
(叶子链表: 1→5→9→11→19→21→29→31)

3. 查找过程（底层视角）

1. 从根节点读入内存（一次磁盘 IO）
2. 在节点内二分查找，确定下一层指针
3. 逐层向下，直到叶子节点
4. 在叶子节点找到数据或行指针

InnoDB 中，叶子节点存的是 聚簇索引：整行数据
二级索引：叶子节点存 索引列 + 主键值

二、Hash 索引（Memory / Redis / 部分场景）

实现方式

• 对索引列做 hash 函数
• 存 hash值 → 数据位置

特点

✅ 等值查询 O(1)
❌ 不支持范围查询
❌ 不支持排序
❌ 有哈希冲突

MySQL Memory 引擎、Redis 底层就是 Hash

三、其他常见索引底层实现

1. LSM Tree（写多读少）

• HBase、Cassandra、LevelDB
• 写：先写内存（MemTable）
• 后批量刷磁盘（SSTable）
• 读：多层合并查找

✅ 写入极快
❌ 读稍慢

2. 位图索引（OLAP）

• 每个取值一个 bit 向量
• 适合低基数列（性别、状态）

✅ 多条件 AND/OR 极快
❌ 不适合高并发写

四、InnoDB 索引的物理存储

• 数据按 页（16KB） 存储
• 索引 = 页组成的 B+ 树
• 页内有：
  • 槽位（slot）
  • 行记录
  • 指针

五、一句话总结

数据库索引的本质：
用“额外空间 + 特定数据结构”，把“全表扫描”变成“少量磁盘 IO 的有序查找”

如果你愿意，我可以：

• 画 B+ 树 vs 二叉树 IO 对比
• 讲 为什么 InnoDB 必须用聚簇索引
• 结合 SQL 为什么走 / 不走索引 讲底层原因