通俗易懂介绍mysql索引为什么使用B+树？

    通俗易懂告诉你mysql索引为什么使用B+树？回答这个问题之前先考虑两个问题：
    1.mysql为什么使用索引？
    2.支持索引的数据结构都有哪些？

1.mysql为什么使用索引？

    持久化存储的数据都是存储于磁盘，而从磁盘中进行读写数据都是IO操作，相对于内存数据读取，IO操作很容易出现性能瓶颈问题，为了提升数据io数据读取的性能问题，就有了索引的概念。官方介绍中索引是提升数据库读取性能的数据结构。对索引最通俗易懂、最直观的解释就是好比是新华字典中每个首字母，如果想从厚厚的一本字典中找到一个汉字，从第一页开始一直找到最后一页显然是很耗时的。但是先确定好要能找的字的第一个首字母，范围就一下子缩小了，所消耗的时间也减少了很多，这就是索引的好处。当然实际上mysql并不是按照这种实现的，不过有异曲同工之处。至于mysql中具体的索引是怎么起作用的继续往下看！

2.支持索引的数据结构都有哪些？

    常见的并且有助于提升查询速度的数据结构有一下几种：
哈希表
二叉树
红黑树
B树
B+树
依次说一下每种数据结构的优缺点。
哈希表
    哈希存储都不陌生，就是按照K-V键值对的方式进行读取，可以根据key直接获取value值。对于等值查询，哈希查询速度很快，但是对于范围查询的场景，哈希索引并不适合，也需要每条数据都进行查询然后判断是否符合范围，相当于全表扫描，所以不是合适的索引数据类型。

二叉树
    结构特点：每个节点下面最多有两个子节点，左侧子节点大于父节点，右侧子节点小于父节点。简单来讲优点就是缩小查找的范围，减少读取的次数。下面模拟插入指定数据：15 10 17 12 9 21 16，存储之后的数据结构为：

二叉树动态插入展示
比如说查找12，只需要对比两次就可以找到12.查找速率确实能提升。但mysql为什么没有使用二叉树，原因是可能会出现“链表”数据结构，此种结构相当于“全表扫描”。比如说需要存储连续的数据：

红黑树
    红黑树实际上也算是二叉树的一种，也有人称之为平衡二叉树，主要的优点是解决普通二叉树可能存在的单链表结构。存储相同数据的存储图如下：

可以看出数据存储的位置基本上一致。主要看下对于连续数据存储的情况：

红黑树动态插入展示
可以发现红黑树解决了二叉树存储可能出现的链表结构。但是mysql为什么索引不用红黑树？原因在于红黑树的问题在树的高度问题，数据量增多，树的高度就会增加，每层树的读取时就相当于一次IO操作，显然也不是最好的数据结构。继续往下看。
B树
    可以说B树的出现主要是解决红黑树中树高度过高导致磁盘IO读取次数过高的问题。首先说一下mysql中磁盘最小的存储单位为页，存储大小为16Kb,相当于人民币的分。页中存储多个节点，
每个节点由三部分组成：索引字段值、字段值所对应的行详细数据、行数据所在的磁盘地址。数据结构图如下：

B+树
    mysql中使用存储引擎是B+数，原因是B+树相对于B树，非叶子节点不存储行详细数据，仅储存索引字段值以及所在磁盘的地址值，会存在冗余重复的索引字段值，优点在于每页存储单位中能存储更多的索引信息，形成的B数会更加矮小更胖。参考图如下：

逻辑图如下:

假设主键为bigint类型，主键bigint占用8个字节，指针地址占用6个字节，8+6=14，所以我们可以得出，一页能存放的指针个数为16k/(8+6)约等于1170。单条行记录大小约为1k，那么一个page能存储的行记录数为16k/1k=16，所以树高3层为1170117016约等于2190w数据，完美解决树高导致IO读取次数过高问题。
说明:文章中动态页面为国外某学校网站地址,支持多种数据结构演示,地址:https://www.cs.usfca.edu/~galles/visualization/,关于索引添加之后的数据摆放顺序可以参考网站演示.