MySQL底层索引结构分析

Mysql底层索引结构分析

mysql数据库底层所采用的是B+树，那么B+树的索引结构，又是怎么推导出来的呢？为什么Mysql选用B+树作为索引结构，而不是二叉树，平衡二叉树，红黑树或是B树呢？今天来分别学习一下这些树的结构。

一、二叉树

二叉树应该是我们学习数据结构的一开始就接触的树结构。二叉树的性质就是左子树的所有节点的值小于当前根结点，右子树的所有节点的值大于当前根结点。假设二叉树作为索引结构，要比一条一条遍历要效率要高不少。

举个简单的例子：

{width=90%}

说明：假设根据用户的id创建索引，从小到大，那么现在我要查找id为20的用户信息，通过二叉树，我们只需要比较4次，就可以找到该用户，而如果不建立索引，通过一条一条数据行遍历，那么就会需要9次，由此我们可以看出建立索引要比不建立索引至少效率提高一倍。

注：但是二叉树也会存在弊端，就是遇见最坏的情况，所有的结点变成了一条线性链表。因此平衡二叉树可以有效的防止这种最坏的情况出现。尽管如此，mysql却并没有选择平衡二叉树作为索引结构，那么说明还有更好的索引结构。请继续往下看~

二、红黑树

红黑树是一种自平衡二叉树，因为伴随着某一个结点的增加删除，会自适应的调整当前树的结构，使之满足任意两个节点之间的层次差不大于2，也就是小于等于2.我们应该知道平衡二叉树应该任意两个节点之间的层次不超过1，所以红黑树不能算是一棵严格的平衡二叉树。

红黑树的性质：

① 根结点为红色或者黑色。

② 所有的叶子结点都为黑色（叶子结点为Null）

③ 如果一棵二叉树为红黑树，那么其子树也为红黑树

④ 任意两个结点间的层次差不能大于2

⑤ 每条路径都包含相同的黑色结点个数

{width=80%}

为上图添加2个值为3的结点，红黑树会根据其性质做适当的翻转，调整，在插入和删除的情况下，效率要好于平衡二叉树。但是查找的情况下，因为红黑树在结点相同的情况下，层次要比平衡二叉树高，所以查询的效率要稍微低于平衡二叉树。通过翻转来提高查找删除效率。

{width=80%}

三、B树

B树相较于二叉树，平衡二叉树，红黑树来说，结构发生了一些改变。B树允许一个结点中存放多个关键字，而这些结点中多了一个空间域，存放data，可以是当前行所在的磁盘文件指针地址，也可以是当前行的数据。为什么要要存放多个结点呢？我们应该晓得一棵树的层次越浅，查找的性能就越高。如果存在千万级的数据量，使用平衡二叉树的话，树的深度会非常深，所需要读取磁盘IO的次数将会非常多，因为读取数据会以磁盘块的形式读取，而不是一条一条的读取，这就导致查找的效率也不是很高。而B树就很好的弥补了平衡二叉树的这种缺陷。

{width=80%}

{width=80%}

我们通过图可以看见，我设定了每个结点中的关键字最大不超过4，每个关键字都会带上data域。

说明：

假设我要查找88这个元素，那么首先将0015关键字放进内存中与0088比较，在磁盘上找到0024和0076所在的结点，然后将其们放入内存与0088比较，比较得出0088和0089这个页，然后将其们放进内存，比较得出88，最后，找到88所对应的data，进入相应的磁盘文件读取该数据行，返回结果。

这个过程总共比较了3次，外加三次次磁盘IO读取，在B树中查找结点实在磁盘上进行的，而在结点中找关键字是在内存中进行的，因此相比于平衡二叉树来说效率会更高。那么为什么mysql选用的是B+树作为索引结构，而不是B树呢？别急，请看下面介绍B+树~

四、B+树

B+树听起来就像是B树的升级版，实事也是如此，B+树对B树的改进主要在于将所有非叶子节点中的data域去除了，这样做可以增加索引个数，这里给大家简单的计算下索引个数，假设我存储的索引类型为int整型，大小也就是4B（不包含data），而Mysql底层规定的指针大小为6B，每一页的大小为16k，那么索引个数为16k/(6B+4B)个索引，如果加上了data，会变得更小。

注：

每个结点中存放的关键字多了，层数自然就会相对于B树更浅了。同时一次磁盘IO读取的磁盘块中的索引结点也会更多，有效的减少了磁盘IO，提高了查找效率。

{width=80%}

通过图，我们可以清晰的看出B树和B+树的差异。

五、Mysql中的两种索引结构

mysql中建立索引的时候，有两种可以选择的索引，分别为B+树和hash，通常我们选择B+树作为索引结构，而不是用hash，因为hash创建索引结构存在几个弊端：

① hash查找单个索引的时间复杂度为0(1),但无法查找范围内的数据

② 针对索引使用order by的时候，hash不支持排序

③ 当数据量非常大的时候，哈希冲突也就更加明显。

六、Mysql中的两种存储引擎

Mysql中同样穿在两种存储引擎，分别为innodb和mylsam，两者的区别主要是data域上的区别以及产生的不同的效果

mylsam的data域上存放的当前行的磁盘文件索引地址，也就是找到了该索引，要进行一次磁盘IO读取该行所对应的数据。

Innodb的data域上存放的是当前行的数据信息，将数据和索引放在了同一个文件下，因此减少了mylsam中的所需要的一次磁盘IO读写，也相应的提高了查找效率。毕竟磁盘的读取速度要比内存慢很多很多。

七、为什么要设计主键，并且为整型？主键为什么要自增？

① 首先如果你不创建主键，mysql会自动为你创建一个主键，主键常常用作索引，因此在索引比较的时候，整型的数据比较大小要比字符串按位比较大小效率快得多。

② 主键自增带来的好处是范围查找以及插入的效率。主键自增的话，索引的排列顺序将会是依次增加的，根据上面的B+数中的图，我们也可以发现，所有的叶子节点之间用了指针相连，这样查找大于某个索引值的数据集的话，就很方便，因为它是按顺序排列的嘛。但是如果不是自增的话，加入我之前已经插入了50这个索引，现在我要插入46这个索引，假设一个页只能够存储4个字节，而之前50这个领域（包含自己）内已经存在了4个字节，此时我要插入46是不是得将这个已经满的页给分裂成两个子页，重新组合，这样就可能破坏了树的结构。