【Mysql】B+树索引

你这份总结整体是对的，核心可以理解成一句话：

MySQL InnoDB 用 B+ 树做索引，是为了尽量减少磁盘 I/O，并且同时支持等值查询和范围查询。

下面我按你的内容重新串起来解释。

1. 为什么索引要考虑“磁盘 I/O”？

数据库的数据不是全部放在内存里的，很多数据存在磁盘上。

InnoDB 读写磁盘的基本单位是页 Page，默认大小是16KB。

也就是说：

一次磁盘 I/O ≈ 读取一个 16KB 的页

而 B+ 树的一个节点，通常也对应一个页。

所以查询时大概是：

访问根节点页 ↓ 访问中间节点页 ↓ 访问叶子节点页

如果树高是 3，那么通常需要读 3 个页，也就是大约 3 次磁盘 I/O。

不过注意一点：根节点和部分中间节点可能被缓存到内存中，所以真实磁盘 I/O 次数可能比树高少。但从理论上理解，树越低，I/O 越少。

2. 为什么不用哈希表？

哈希表适合：

select*fromuserwhereid=10;

这种等值查询。

因为哈希表可以根据 key 快速定位 value，理想情况下时间复杂度是：

O(1)

但是哈希表不适合范围查询，比如：

select*fromuserwhereidbetween10and100;

因为哈希表里的数据不是有序的。

所以它很难快速找到：

10、11、12、13 ... 100

只能一个个扫描。

因此哈希表适合等值查询，但不适合作为数据库通用索引结构。

3. 为什么不用普通二叉树？

二叉树每个节点最多只有两个子节点。

比如：

8 / \ 4 12 / \ / \ 2 6 10 14

如果数据量很大，树的高度会比较高。

比如几百万、几千万条数据，二叉树层级可能很多。

而数据库查询时，每经过一层，就可能需要一次磁盘 I/O。

所以二叉树的问题是：

树太高 → 磁盘 I/O 次数多 → 查询慢

数据库更希望树“矮胖”，不是“瘦高”。

4. 为什么 B 树比二叉树好？

B 树是多叉树，一个节点可以有很多个子节点。

比如一个节点中可以存很多 key：

[10 | 20 | 30 | 40]

它可以分出多个区间：

小于10 10到20 20到30 30到40 大于40

所以 B 树比二叉树更“矮”。

假设一个节点能分出几百个分支，那么几千万条数据可能也只需要 3~4 层。

这就减少了磁盘 I/O。

但是 B 树有一个问题：

B 树的非叶子节点也存储真实数据记录。

比如：

非叶子节点： [id = 10, name = 张三, age = 20, address = ...]

问题来了：一页只有 16KB，如果非叶子节点里面放了完整记录，那么一个节点能放下的 key 就少了。

也就是说：

节点空间被真实数据占用了 ↓ 一个节点能存的索引 key 变少 ↓ 分支因子变小 ↓ 树的高度变高 ↓ 磁盘 I/O 增加

所以 B 树虽然比二叉树好，但还不是最适合数据库索引。

5. 为什么 B+ 树更适合？

B+ 树的核心设计是：

非叶子节点只存索引 key 叶子节点存完整数据

比如：

[30 | 60] / | \ [10,20] [30,40,50] [60,70,80]

上面的[30 | 60]只是用来导航的，不存真实记录。

真实记录都在最下面的叶子节点里。

这样做有两个好处。

好处一：非叶子节点能放更多 key，树更矮

因为非叶子节点只放索引，不放整行数据，所以一页 16KB 可以放很多索引 key。

例如索引 key 是 bigint，占 8 字节，再加上子节点指针，一条目录项可能十几字节。

那么一个 16KB 页可以存很多目录项。

所以 B+ 树的分支因子很大。

分支因子大意味着：

每一层能定位的数据范围更大 ↓ 树的高度更低 ↓ 查询需要的磁盘 I/O 更少

这就是 B+ 树适合数据库索引的最核心原因。

好处二：叶子节点之间有链表，范围查询快

B+ 树的叶子节点之间是有序连接的，InnoDB 中叶子节点之间是双向链表。

比如：

[1,2,3] <-> [4,5,6] <-> [7,8,9] <-> [10,11,12]

如果执行：

select*fromuserwhereidbetween4and10;

B+ 树可以先定位到4所在的叶子节点，然后沿着链表往后扫：

4 → 5 → 6 → 7 → 8 → 9 → 10

这就很适合范围查询。

而哈希表不支持这种有序扫描。

6. B 树和 B+ 树的关键区别

你可以这样记：

最重要的是：

B+ 树把非叶子节点变成“目录” 叶子节点才是真正的数据区

这就像一本书：

目录页：只放章节标题和页码 正文页：放具体内容

如果目录页也放大量正文内容，那么目录就变厚了，查找效率就低了。

7. 聚集索引是什么？

在 InnoDB 中，表数据本身就是按照主键组织成一棵 B+ 树的。

这棵树叫：

聚集索引，也叫主键索引

它的叶子节点存的是：

主键值 + 整行记录

例如表：

student(id,name,age)

如果id是主键，那么主键索引树大概是：

非叶子节点： [id] 叶子节点： [id, name, age]

也就是说，真正的数据行就在主键索引树的叶子节点上。

所以 InnoDB 表必须有聚集索引。

如果你没有设置主键，InnoDB 会按规则选择：

1. 优先使用主键作为聚集索引 2. 如果没有主键，选择第一个非空唯一索引 3. 如果都没有，InnoDB 会生成一个隐藏的 row_id 作为聚集索引

你总结里少了第三点，可以补上。

8. 二级索引是什么？

除了主键索引以外，其他索引都叫二级索引，也叫辅助索引。

比如：

createindexidx_ageonstudent(age);

这个age索引就是二级索引。

二级索引也是一棵 B+ 树。

但是它的叶子节点存的不是整行数据，而是：

索引列 + 主键值

比如age是二级索引：

二级索引 idx_age 的叶子节点： [age, id]

为什么要存主键值？

因为 InnoDB 真正的数据在主键索引树里。

二级索引查到之后，还需要用主键去主键索引树里找完整记录。

9. 什么是回表？

假设有表：

student(id,name,age)

其中：

id 是主键 age 是二级索引

执行：

selectid,age,namefromstudentwhereage=1;

查询过程是：

第一步：去 age 二级索引树中查 age = 1 查到叶子节点，得到 id 第二步：拿这个 id 去主键索引树中查 找到整行记录，拿到 name

第二步就叫：

回表

因为它从二级索引树，又“回到”主键索引树查完整数据。

也就是：

二级索引树 → 主键值 → 主键索引树 → 整行数据

回表会增加查询成本，所以能避免就尽量避免。

10. 什么是覆盖索引？

还是这个表：

student(id,name,age)

age是二级索引。

执行：

selectid,agefromstudentwhereage=1;

这时候只需要查：

id 和 age

而age二级索引的叶子节点里本来就有：

age + id

所以不需要再去主键索引树查整行数据。

这就叫：

覆盖索引

意思是：

查询需要的字段，已经被当前索引覆盖了

所以不需要回表。

11. 回表和覆盖索引对比

回表查询

selectid,age,namefromstudentwhereage=1;

查询字段：

id、age、name

二级索引idx_age里有：

age、id

但是没有：

name

所以必须回表。

查询路径：

age 二级索引树 → 找到 id → 主键索引树 → 找到 name

覆盖索引查询

selectid,agefromstudentwhereage=1;

查询字段：

id、age

二级索引idx_age里正好有：

age、id

所以不需要回表。

查询路径：

age 二级索引树 → 直接得到 id 和 age

12. 最后用一句话总结

B+ 树索引可以这样理解：

B+ 树是一种“矮胖、有序、叶子节点链表连接”的多叉树。

InnoDB 用它做索引，是因为：

1. 非叶子节点只存索引，分支因子大，树高低，磁盘 I/O 少 2. 叶子节点有序并通过链表连接，范围查询快 3. 聚集索引的叶子节点存整行数据 4. 二级索引的叶子节点存索引列 + 主键值 5. 二级索引查完整数据可能需要回表 6. 查询字段都在索引里时，就是覆盖索引，可以避免回表

你可以把 InnoDB 的索引理解成：

主键索引：直接存数据的 B+ 树 二级索引：先找到主键，再通过主键找数据的 B+ 树

最关键的区别就是：

聚集索引叶子节点 = 整行数据 二级索引叶子节点 = 主键值