b-tree和b+tree以及mysql为什么使用了b+树

最近写了一些mysql的博客，但是对于索引的数据结构一致没有深入的描述过。所以就有了这一篇文章。

b tree和b-tree就是一个玩意

应该很多人都看到过b树和b-树，还有b+树，不了解的小伙伴还以为这是三个东西，但是其实b树和b-树就是一种事物的两种称呼而已。

b树（Balanced Tree）多路平衡查找树

对比于二叉树来说，可以认为他是多叉的。其图如下

 

其特点如下：

 

• 所有关键字和数据分布在整个树中。
• 任何关键字出现且只出现在一个节点中。
• 因为数据在节点上，所以搜索有可能在非叶子节点结束。
• 在关键字全集内做一次查找，性能逼近二分查找算法。

B+Tree (B+树是 B 树的变体，也是一种多路查找树)

相对于b-树来说，他的最大的特点是：

• 其非叶子节点不存储数据，只存储关键字，所有数据都存储在叶子节点上。
• b+树为所有叶子节点增加了一个链指针，指向下一条数据。这意味着所有的数据都是按关键字的顺序存储的。很适合查找范围数据。
• 每一个叶子页到根的距离相同

 

 

mysql为什么使用了b+树而不是b-树

 

• 由于非叶子节点不存储 data，所以一个存储页可以存储更多的非叶子节点，也就是说使用 b+树单次磁盘 I/O拿到的同大小存储页中包含的信息量相比 b-树更大，所以减少了同样数据量下每次查询的io次数。
• MySQL 是关系型数据库，经常会按照区间来访问某个索引列，B+树的叶子节点间按顺序建立了链指针，加强了区间访问性，所以 B+树对索引列上的区间范围查询很友好。而 B 树每个节点的 key 和 data 在一起，无法进行区间查找。

 

 

附1：mysql的页读取使用了局部性原理，我们不止一次的提到过

计算机中所有的缓存系统的设计，基本都依赖于著名的局部性原理（访问一个数据的时候，有很大可能会访问到与他相邻的数据）。注意：这并不是一个普适性原理，是因为设计计算机的先辈大牛们发现了有局部性原理，才设计出了各种缓存来加速访问。但是理论上来说，一段代码写的如果足够烂，完全可以彻底废掉所有依赖局部性原理而设计的缓存系统。

 

附2：机械磁盘的顺序读和随机读

很多文章在讲mysql的时候，经常会说到磁盘io的问题。这里涉及到一个现象就是很少有人说磁盘到底是什么磁盘。因为随着技术变革，机械磁盘已经慢慢的被固态盘代替，再简单的只说磁盘io已经不那么严谨了。我们来对比一下机械磁盘的顺序读和随机读与固态硬盘的顺序读和随机读的区别

 

机械硬盘：读取数据，受到其物理结构限制，读取数据需要先摆臂，然后等待磁盘旋转到指定位置，再进行读取。如果频繁的更改读取地址，将会大大增加其总的读取速度。而顺序的读写，至少能省略大部分摆臂时间。所以普遍认为是顺序io比随机io性能高很多。

 

固态硬盘：因为其寻址是电子选址，依靠的是主控的地址传输和数据传输。相对来说随机读并没有像机械硬盘损失那么多时间。但是每次的单独选址和传递，也需要时间。所以依然是顺序io比随机io更快。但是相对来说，速度损失没有那么明显。

 

mysql的数据都是存放在磁盘中的，所以能利用顺序io来预读数据是最好的选择。b+树因为其非叶子节点占用空间比b树要小，所以查找的时候，随机io的次数也更少。往往很少次预读存储页就可以拿到所有飞叶子节点。进行查找后再去叶子节点拿数据就好了。当然如果你的mysql服务器能上固态盘的话，请不要犹豫，他会给你带来立竿见影的效果。