由 B-/B+ 树看 MySQL索引实现，深入思考两个面试题背后的设计思路

B 树是一种多路自平衡搜索树，它类似普通的二叉树，但是 B 树允许每个节点有更多的子节点。B 树示意图如下：

B 树的特点：

（1）所有键值分布在整个树中 （2）任何关键字出现且只出现在一个节点中 （3）搜索有可能在非叶子节点结束 （4）在关键字全集内做一次查找，性能逼近二分查找算法

B+ 树是 B 树的变体，也是一种多路平衡查找树，B+ 树的示意图为：

从图中也可以看到，B+ 树与 B 树的不同在于：（1）所有关键字存储在叶子节点，非叶子节点不存储真正的 data。（2）为所有叶子节点增加了一个链指针。

面试题1 ：为什么用 B/B+ 树这种结构来实现索引呢？

红黑树等结构也可以用来实现索引，但是文件系统及数据库系统普遍使用 B/B+ 树结构来实现索引。MySQL 是基于磁盘的数据库，索引是以索引文件的形式存在于磁盘中的，索引的查找过程就会涉及到磁盘 IO 消耗，磁盘 IO 的消耗相比较于内存 IO 的消耗要高好几个数量级，所以索引的组织结构要设计得在查找关键字时要尽量减少磁盘 IO 的次数。为什么要使用 B/B+ 树，跟磁盘的存储原理有关。

这里， 局部性原理与磁盘预读 。为了提升效率，要尽量减少磁盘 IO 的次数。实际过程中，磁盘并不是每次严格按需读取，而是每次都会预读。磁盘读取完需要的数据后，会按顺序再多读一部分数据到内存中，这样做的理论依据是计算机科学中注明的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。（1）由于磁盘顺序读取的效率很高(不需要寻道时间，只需很少的旋转时间)，因此对于具有局部性的程序来说，预读可以提高 I/O 效率.预读的长度一般为页(page)的整倍数。（2）MySQL(默认使用InnoDB引擎),将记录按照页的方式进行管理,每页大小默认为16K(这个值可以修改)。Linux 默认页大小为4K。

B-Tree 借助计算机磁盘预读的机制，并使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个结点只需一次 I/O。假设 B-Tree 的高度为 h, B-Tree 中一次检索最多需要 h-1 次 I/O（根节点常驻内存），渐进复杂度为 O(h)=O(logdN)O(h)=O(logdN)。一般实际应用中，出度 d 是非常大的数字，通常超过 100，因此 h 非常小（通常不超过3，也即索引的 B+ 树层次一般不超过三层，所以查找效率很高）。而红黑树这种结构，h 明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的 I/O 渐进复杂度也为 O(h)，效率明显比 B-Tree 差很多。

面试题2 ：为什么 MySQL 的索引使用 B+ 树而不是 B 树呢？

（1）B+ 树更适合外部存储(一般指磁盘存储),由于内节点(非叶子节点)不存储 data，所以一个节点可以存储更多的内节点，每个节点能索引的范围更大更精确。也就是说使用 B+ 树单次磁盘 IO 的信息量相比较 B 树更大，IO 效率更高。（2）MySQL 是关系型数据库，经常会按照区间来访问某个索引列，B+ 树的叶子节点间按顺序建立了链指针，加强了区间访问性，所以B+树对索引列上的区间范围查询很友好。而 B 树每个节点的 key 和 data 在一起，无法进行区间查找。