深入聊聊mysql索引为什么采用B+树结构

本篇文章是mysql的进阶学习，介绍一下mysql使用B+树作为索引数据结构的原因，希望对大家有所帮助！

索引提高查询效率，就像我们看的书，想要直接翻到某一章，是不是不用一页一页的翻，只需要看下目录，根据目录找到其所在的页数即可。【相关推荐：mysql视频教程】

在计算机中我们需要一种数据结构来存储这个目录，常见数据结构有哈希表，二叉查找树，二叉平衡树(AVL)，红黑树，那为什么Innodb和MyISAM选择b+树呢。

1. 哈希表

缺点：

1. 利用hash存储需要将所有的数据文件添加到内存，比较消耗内存空间。
2. hash的查找是等值查询，速度很快，但是各个数据间没有范围规律，但在实际工作中更多的是范围查询，hash就不太合适了。

不能直接说mysql不使用哈希表，而是要根据存储引擎来确定的，Memory存储引擎使用的就是哈希表

2. 二叉查找树

缺点：

1. 如图，极端情况可能会出现倾斜的问题，最后变成链表结构。
2. 造成树节点过深，从而增加查找的IO，而现在IO就是查找的瓶颈

3. 二叉平衡树-AVL

缺点：

1.当数据量很大的时候，为了保持平衡，需要进行1-n次的旋转，这个旋转是比较浪费性能的，插入和删除效率极低，查询效率很高。

2. 只有两个分支，数据量大的时候树的深度依然很深。

4. 红黑树

缺点：

同样是只有两个分支，数据量大的时候深度依然会很深

以上三种二叉树，随着数据的增多，最终都会出现节点过多的情况，而且他们有且仅有2个分支，那么IO的次数一样很多.

怎么解决仅有2个分支而且深度过深，这就有了B树，增加分支

5. B-Tree

如上图：（图中只是画出来一部分，实际上没有限制的，不止p1,p2,p3）

每个节点占用一个磁盘块，一个节点上有两个升序排列的关键字和三个指向子树根节点的指针，指针存储的是子节点所在的磁盘块地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为16和34，p1指针指向的子树的数据范围小于16，p2指针指向的子树的数据范围为16-34，p3指针指向的子树的数据范围大于34。

查找关键字28的过程：

1. 根据根节点找到磁盘块1，读到内存中。【第一次磁盘I/O操作】
2. 比较关键字28在区间(16，34)，找到磁盘块1的指针p2。
3. 根据p2指针找到磁盘块3，读到内存。【第二次磁盘I/O操作】
4. 比较关键字28在区间(25，31)，找到磁盘块3的指针p2。
5. 根据指针p2找到磁盘块8，读到内存。【第三次磁盘I/O操作】
6. 在磁盘块8中的关键字列表中找到关键字28，结束。

缺点：

1. 每个节点都有key，同时包含data，而每个页存储空间是有限的，如果data很大的话会导致每个节点能存储的key的数量变小。
2. 当存储的数据量很大的时候会导致深度变大，增加查询磁盘的io次数，进而影响查询性能。

6. B+树

如上图： 在B+树上有两个头指针，一个指向根节点，另一个指向关键字的最小叶子节点，而且所有叶子节点(及数据节点)之间是一种链式环结构，因此可以对B+树进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始的随机查找。

InnoDB和MyISAM中索引上的差异

1. InnoDB-主键索引

叶子节点存储的是具体的行数据

2. InnoDB-非主键索引

非主键索引的叶子节点存储的是主键值（所以查询数据基本要回表）

3. MyISAM

叶子节点存储的是行数据的地址，额外需要一次寻址，多一次IO

总结：为什么mysql使用的是B+树

• hash表，等值查询是很快的，但是不满足常用的范围查找且相邻的两个值之间没有关系，而且hash比较消耗内存。

• 二叉树/平衡二叉树/红黑树等都是有且仅有2个分支，共性就是数据量大的时候树的深度变深，增加IO的次数。

• B树会在节点上存储数据，这样一页存放的key的数量就会减少，增加树的深度。

• B+树中非叶子节点去除了数据，这样就会增加一页中key的数量，而且叶子节点之间是通过链表相连，有利于范围查找和分页。

最后

以上就是轻松小霸王为你收集整理的深入聊聊mysql索引为什么采用B+树结构的全部内容，希望文章能够帮你解决深入聊聊mysql索引为什么采用B+树结构所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。