B+树存储结构

B+树存储结构

是的,InnoDB 的聚簇索引 B+Tree 中,只有叶子节点(最底层)保存完整数据记录,非叶子节点(根节点和中间节点)只保存索引信息用于导航查找。

假设有一个三层 B+Tree:

[根节点] 100 | 200 | 300 / | \ / | \ [中间节点] [中间节点] [中间节点] 50|80 150|180 250|280 / | \ / | \ / | \ [叶子节点][叶子节点][叶子节点]...

第一层(Root 根节点)

存储:

主键值(索引键) + 子节点页指针

例如:

100 | 200 | 300

表示:

id < 100 100 <= id < 200 200 <= id < 300 id >= 300

以及对应子节点所在的数据页地址。

不存完整数据。


第二层(非叶子节点)

存储:

索引键 + 下一层页指针

例如:

50 | 80

表示:

id < 50 50 <= id < 80 id >= 80

仍然不存完整数据。


第三层(叶子节点)

聚簇索引叶子节点:

(id=1,name=Tom,age=18) (id=2,name=Jack,age=20) (id=3,name=Lucy,age=22)

存储的是:

整行记录

例如:

主键 其它列 事务信息 隐藏列

为什么非叶子节点不存完整数据?

为了提高"扇出(Fan Out)"。

假设:

情况1:非叶子节点只存 key

id

一个16KB页可以放:

1000多个key

树会非常矮:

1000 1000 × 1000 = 100万 1000 × 1000 × 1000 = 10亿

三层就能管理十亿条记录。


情况2:非叶子节点存完整数据

例如:

id name phone address ...

每条记录变大。

16KB页可能只能放:

几十条

树高度会迅速增加。

查询磁盘IO次数也增加。

所以B+Tree设计成:

非叶子节点 只存索引键 叶子节点 存真实数据

聚簇索引查找过程

例如:

SELECT * FROM user WHERE id = 150;

执行过程:

Root 100 | 200 | 300 ↓ Middle 150 | 180 ↓ Leaf (id=150,name=Tom,...)

查找路径:

根节点 ↓ 中间节点 ↓ 叶子节点

找到数据。


如果是普通索引呢?

例如:

create index idx_name on user(name);

叶子节点就不一样了。

Tom -> 1 Jack -> 2 Lucy -> 3

叶子节点保存:

name + 主键id

而不是完整数据。

因此:

select * from user where name='Tom';

需要:

name索引树 ↓ 得到 id=1 ↓ 主键索引树 ↓ 得到完整记录

这就是回表。


面试一句话总结

InnoDB 的 B+Tree 中,根节点和中间节点只保存索引键值以及子节点页指针,用于缩小查找范围;只有叶子节点才保存数据。对于聚簇索引,叶子节点保存完整行记录;对于二级索引,叶子节点保存索引列值和主键值,因此查询时可能需要回表。