MySQL: B+ 树

[dushaoshuai]

为什么 InnoDB 使用 B+ 树存储数据？

MySQL 要将数据持久化，还要保证在数据量较大时也能有不错的性能。

数据存储在外部存储设备上，我们必须考虑在查询数据时对外部存储设备的访问次数和单次访问时间。将数据从外部存储设备读取到内存中的 I/O 操作是比较耗时的，这个时间一般是固定的（当然可以使用顺序 I/O 代替随机 I/O 来提高性能）。我们可以先着眼于减少 I/O 次数。

从外部存储设备中加载数据，是以页为单位进行加载的。假设查询过程中经历的所有结点都分布在不同页上，要减少 I/O 次数，就要让每结点中包含尽可能多的有用信息（这里指的是关键字，关键字多，可选择的分支多，查询效率高），减小树的高度。

• 二叉查找树每结点只存储一个关键字
• B 树每结点可以存储多个关键字，但是结点中也存储数据
• B+ 树每结点可以存储多个关键字，非叶结点不存储数据（因此树的高度小），所有数据存储在页结点中

除此之外，如果使用 B 树，所有查询必须从根结点开始，如果所有经历的结点都分布在不同页上，就是大量的随机 I/O。而 B+ 树，严格来讲已经不是树了，其所有叶子结点组成了一个双向链表，支持遍历，支持范围查询，支持反向遍历，在叶子结点间按照顺序跳转时能减少随机 I/O 的次数。

参见

• MySQL - page
• MySQL - Backward index scan
• https://draveness.me/whys-the-design-mysql-b-plus-tree/
• 大话数据结构 - 8.8 多路查找树（B 树）
• 数据结构与算法分析 C 语言描述 - 4.7 B 树

[dushaoshuai]

MySQL 文档中关于 B+ 树的一些描述

Index records are stored in the leaf pages of their B-tree or R-tree data structure^1.

Each InnoDB table has a special index called the clustered index that stores row data^2.

How the Clustered Index Speeds Up Queries Accessing a row through the clustered index is fast because the index search leads directly to the page that contains the row data. If a table is large, the clustered index architecture often saves a disk I/O operation when compared to storage organizations that store row data using a different page from the index record^3.