深入理解Mysql的B+树

在 MySQL 里 InnoDB 存储引擎是采用 B+ 树来组织数据的。

如图：

可以得出B+树的特点

• 只有叶子节点（最底层的节点）才存放了数据，非叶子节点（其他上层节）仅用来存放目录项作为索引。
• 非叶子节点分为不同层次，通过分层来降低每一层的搜索量；
• 所有节点按照索引键大小排序，构成一个双向链表，便于范围查询；

?数据页详解

• 在innoDB中的数据是按「数据页」为单位来读写的，也就是说每次I/O的最小单位是页。
• InnoDB 数据页的默认大小是 16KB。

结构的相关作用：

File Header 中有两个指针，分别指向上一个数据页和下一个数据页，连接起来的页相当于一个双向的链表

数据页中的记录按照「主键」顺序组成单向链表，但单向链表检索效率不高。因此数据页中有一个页目录来加速查询，具体查询方式是二分查找。

页目录创建的过程如下：

1. 将所有的记录划分成几个组，这些记录包括最小记录和最大记录，但不包括标记为“已删除”的记录；
2. 每个记录组的最后一条记录就是组内最大的那条记录，并且最后一条记录的头信息中会存储该组一共有多少条记录，作为 n_owned 字段（上图中粉红色字段）
3. 页目录用来存储每组最后一条记录的地址偏移量，这些地址偏移量会按照先后顺序存储起来，每组的地址偏移量也被称之为槽（slot），每个槽相当于指针指向了不同组的最后一个记录。

InnoDB 对每个分组中的记录条数都是有规定的，槽内的记录就只有几条：

• 第一个分组中的记录只能有 1 条记录；
• 最后一个分组中的记录条数范围只能在 1-8 条之间；
• 剩下的分组中记录条数范围只能在 4-8 条之间。

页内查询记录。例如查询15：

• 二分得出槽中间位是 (0+4)/2=2 ，2号槽里最大的记录为 8。因为 15?> 8，所以需要从 2 号槽后继续搜索记录；
• 二分得出槽中间位是 (3+4)/2=3 ，3号槽里最大记录是12。因为15 > 12，所以需要从3号槽后继续搜索记录；
• 二分得出槽中间位是 (4+4)/2=4，4号槽最大记录是16。因为15 < 16，所以数据15在槽4中。
• 从槽3所指向的节点出发查询为15的行记录;

B+ 树查询数据

?B+ 树速查找主键为 6 的记录，以上图为例子：?

• 从根节点开始，通过二分法快速定位到符合页内范围包含查询值的页，因为查询的主键值为 6，在[1, 7)范围之间，所以到页 30 中查找更详细的目录项；
• 在非叶子节点（页30）中，继续通过二分法快速定位到符合页内范围包含查询值的页，主键值大于 5，所以就到叶子节点（页16）查找记录；
• 接着，在叶子节点（页16）中，通过槽查找记录时，使用二分法快速定位要查询的记录在哪个槽（哪个记录分组），定位到槽后，再遍历槽内的所有记录，找到主键为 6 的记录。

ps:在定位记录所在哪一个页时，也是通过二分法快速定位到包含该记录的页。定位到该页后，又会在该页内进行二分法快速定位记录所在的分组（槽号），最后在分组内进行遍历查找

不同的索引类型对应的B+树

索引又可以分成聚簇索引和非聚簇索引（二级索引），它们区别就在于叶子节点存放的是什么数据：

• 聚簇索引的叶子节点存放的是实际数据，所有完整的用户记录都存放在聚簇索引的叶子节点；

• 二级索引的叶子节点存放的是主键值，而不是实际数据。

?因此，如果某个查询语句使用了二级索引，但是查询的数据不是主键值，这时在二级索引找到主键值后，需要去聚簇索引中获得数据行，这个过程就叫作「回表」，也就是说要查两个 B+ 树才能查到数据。不过，当查询的数据是主键值时，因为只在二级索引就能查询到，不用再去聚簇索引查，这个过程就叫作「索引覆盖」，也就是只需要查一个 B+ 树就能找到数据。

?