为什么 Mysql 索引非得是 B+ 树

前短时间在网上找资料自学了一下mysql索引。写了点笔记。

引言

我们都知道mysql是使用B+树作为索引的数据结构的。但是为什么选择使用B+树呢？

为什么不是其他数据结构？

1) hash散列表

hash表是以键值对存储数据的，通过对key做hash运算从而定位到直接的元素。

可以看出两个特点：一个键对应一个值、对不同键hash运算可能会出现相同的结果（hash碰撞）

因此可以分析出两个原因：

a）hash不能做范围查询，只能做精确查询；而mysql的查询大多数都是范围查询；

b）为了减少hash碰撞，需要执行一个负载因子，也就是说需要空出一些空间，来减少hash冲突，所以当数据量很大时，会浪费较多的空间

2）其他树

1、BST(Binary Search Tree)二分查找树

一种排了序的二叉树，左子节点小于父节点，右子节点大于父节点。

没有平衡策略，如果按从小到大，或者从大到小进行插入，可能到导致BST严重倾斜，甚至变成链表的结构。这样查询性能就非常低了。

2、VAL（取自G. M. Adelson-Velsky和E. M. Landis两位科学家的名字）

该树对BST进行了优化，添加了平衡策略。

但是一旦改变树的结构发生改变，都需要改变。如此大大降低的删除和插入的性能（因为要旋转）；适用于查询非常多的场景。显然不适合mysql；

3、红黑树

对VAL的旋转条件作了修改不会轻易的旋转。引入了红黑两个节点。

根节点为黑色，新插入的节点为红色。

从根节点到任意叶子节点的路径上不能有相邻的两个红节点。

最大高度差不能大于2。

红黑树是一种查询和插入性能都很好的二叉树。（不然jdk8之后也不会在hashmap中添加红黑树来提高链表过长时的查询速度）。

但是红黑树本质上依旧是二叉树，如果数据量非常大的时候，树的高度会非常大，如果运气不好查询一个数据时需要遍历的节点数依然不少。（2的20次方104 8576，也就是说当数据量仅仅过了百万级，遍历的节点次数可能会达到20个）

4、B-Tree(普通的B树)

B树有一个特别的特性就是阶，阶指定了树的每个节点能有几个关键字（也就是存数据的地方），可以有几个分叉；

B树相较于同级二叉树可以存储更多的数据。一个4阶的6层的B树存储的数据量就快达到千万级；

每一次查询遍历的节点数相较于二叉树大大减少；

但是B树将数据都存在每个关键字对应的value中。Mysql页的大小为16kb，在页大小固定的前提小，一个也能取出来的数据量非常少，而每次查询只需要遍历key就好，不需要将数据全部查询出来。

如果使用该结构来存储数据，一次查询会增加很多io（多次去读取），影响性能；

B+树

B+树一直比较特殊的B树，它只将数据存储在叶子节点上，同时每个叶子节点间还是指针相连

B+树的数据都存在叶子节点上，非节点上只需要存关键字（在Mysql中一般是主键，而不用带一行数据）。这样在一个页中就可以存入大量的非叶子节点（也就是更多的主键），如此可以快速定位到指定的数据，然后如果当前页中没有再查少量的几次（或一次）就行了



小结

总之，mysql选择使用B+树作为索引结构，都是为了减少查询和修改的时间。

其实追求最小时间一直都是编程的目标，B+的选择是在诸多数据结构中权衡的结果。

并不是说B+树最好的，只是比较适合罢了。