**

** MySQL作为目前市面上流行的几大关系型数据库之一，也是目前国内主流的关系型数据库，在我们的业务开发中，有着举足轻重的地位。平时工作中，想必你也听说过MySQL各种优化，索引，作为MySQL优化的重要手段之一，除了能够为需要的表创建索引外，你对其底层结构及原理了解多少？下面咱们就从索引开始踏上探索MySQL之旅吧！ **

** 索引，是MySQL最常用的核心功能之一，它是一种已经排好序的数据结构。索引相当于书的目录，能够帮助MySQL高效地获取数据。说白了，索引就是一种数据结构。我们知道，查询是数据库的最常用和最重要的功能之一，为了加快查询，此时索引就起作用了。索引常用的数据结构有：二叉树、红黑树（平衡二叉查找树）、Hash表、B-Tree/B+Tree等。了解MySQL的都知道，其索引底层采用的是B+Tree结构，B+Tree是B-Tree的变种。B-Tree（B是Balance的意思）就是平衡树的意思。初学者可能对B-Tree/B+Tree不太了解，下面我们先来了解一下B-Tree及其变种B+Tree。 1、B-Tree的介绍 如下是一张B-Tree的结构图： 主要特点： a、 每个节点中存储着多个元素，元素包含键值和数据；节点中的键值按照从小到大排列，即从左往右递增排列； b、 所有索引元素不重复，父节点（父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点）中的元素不会出现在子节点中； c、 所有的叶子节点（没有子节点的节点叫做叶子节点或叶节点；同理没有父节点的节点叫做根节点）都位于同一层，叶节点具有相同的深度（节点的深度=根节点到这个节点所经历的边的个数，比如：图中叶子节点的深度都为2），叶节点的指针为空，叶节点之间没有指针相连接。 每个节点占用一个盘块的磁盘空间，节点上有两个按照升序排序的关键字和三个指向子节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子节点的数据的范围域。比如以上图的根节点为例，关键字为17和35，p1指针指向的子节点的数据范围小于17，p2指针指向的子节点的数据范围为17~35，p3指针指向的子节点的数据范围大于35。 查找数据的过程： 比如我们查找15的过程大致如下： a、据根节点找到磁盘块1，读入内存； b、比较15与（17,35），发现15小于17，找到磁盘块1中的指针p1； c、根据指针p1指针找到磁盘块2，读入内存； d、比较15与区间（8,12），发现15大于12，于是找到磁盘块2的指针p3； e、根据指针p3找到磁盘块7，读入内存； f、盘块7中的关键字列表中找到15。 通过分析上面的过程，我们发现要查找到我们需要的15需要3次磁盘I/O操作（即步骤a、c和e），和3次内存查找操作（即步骤b、d和f）。由于3次比较查找操作是在内存中进行且列表为有序列表，因此比较查找操作是很快的，可以忽略不计。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。排除网络和硬件条件，磁盘I/O操作次数越少查找效率就越高。 但是B-Tree也有缺点，比如：1）不支持范围查询的快速查找；如果我们想要查找区间（15，20）的数据，先查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率就会变慢。2）空间占用较大；如果data存储的是行记录，行的大小随着列数的增多，所占空间会变大。一个页中可存储的数据量就会变少，树相应就会变高，磁盘I/O次数就会变多。 正因为B-Tree有以上缺点才有了B+Tree的出场。 2、B+Tree的介绍 如下是一张B+Tree的结构图：

主要特点： a、 非叶子节点不存储数据data只存储键值，只有叶子节点才会存储数据data； b、 叶子节点包含所有的索引字段； c、 为了提高区间的访问性能，叶子节点之间使用双向指针进行连接，使所有的叶子节点形成了一个双向且有序的链表结构 查找数据的过程： 等值查询跟B-Tree查询过程一直；这里我们主要看一下范围查找；比如我们查找（15，28）的数据；其过程如下： a、 首先按照B-Tree中的逻辑查找到值等于15的数据，将值等于15的数据缓存到结果集，此时需要三次磁盘I/O操作； b、 查找到15之后，由于底层的叶子节点是一个有序的双向链表结构，我们就可以直接从15开始向后遍历筛选所有符合筛选条件的数据； c、 根据磁盘5的后继指针寻址定位到磁盘块6和磁盘块7，将磁盘块6和7加载到内存中，在内存中从头遍历比较查找，然后将data缓存到结果集中。 因此，B+Tree既继承了B-Tree的优点，又保证了等值和范围的快速查询操作。 以上便是MySQL索引底层采用的B+Tree结构的详解。在介绍索引的开头部分，我们也说过，索引常用的底层数据结构有：二叉树、红黑树（平衡二叉查找树）、Hash表、B-Tree/B+Tree等。上面也介绍了B+Tree相对于B-Tree的优点，下面我们也介绍一下其他几种数据结构的优缺点，来分析MySQL为什么只用B+Tree作为索引常用的底层数据结构。 **

** 要回答这个问题，我们得从B+Tree的优点，和其他几种结构的缺点来论证。 1、Hash表的介绍 Hash表，即散列表；如下是一张hash实现的原理图： 它利用的是数组支持按照下标随机访问数据的特性，它其实是数组的一种扩展，有数组演化而来。在存储数据的过程中，通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当按照键值查询元素时，用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。 主要特点： a、 通常对索引的key进行一次hash计算就可以定位出数据存储的位置，在等值查询时效率很高，时间复杂度为O(1)，因此很多时候Hash索引要比B+Tree索引高效； b、 仅能支持等值“=”和“IN”查询，不支持范围快速查询； c、有hash冲突问题，需要通过开放寻址法或链表法来解决。 hash表不支持范围快速查找使得其使用的场景有限，比如适用于K/V内存数据库，不像B+Tree支持场景多。因此hash不太适合作为MySQL索引底层数据结构。 2、二叉树 如下是一张二叉树结构图：

二叉树，即每个节点最多有两个分叉，也就是两个子节点，分别是左子节点和右子节点，其顺序一般是左小右大。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。二叉树的增删查操作复杂度和树的高度成正比，其遍历查找的时间复杂度为O(n)，理想状态下可以达到O(logn)；在极端情况下二叉树可能会构建成为一个单向链表结构，查找时相当于全表扫描；如下图：

二叉树的缺点决定了其不太适合作为MySQL索引的底层结构。 3、红黑树 先来看一张红黑树的结构图：

红黑树是一个近似平衡的二叉树。因为二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于log2n的情况，从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到O(n)；为了解决这个问题，因此出现了平衡二叉查找树，要求树中任意一个节点的左右子树的高度相差不能大于1；在插入删除数据时通过左旋/右旋操作保持二叉树的平衡，让整棵树看起来比较“对称”，也就是平衡的意思，避免出现左/右子树过高，另一子树过矮而打破树平衡的情况。 虽然红黑树通过各种手段来尽量达到树的平衡，其缺陷也决定了其没有B+Tree更适合MySQL底层索引结构： a、 操作复杂度和树的高度成正比，红黑树的高度近似log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是O(logn)； b、 不支持范围查询的快速查找，范围查询时需要从根节点多次遍历，查询效率很差。 看完hash表、二叉树、红黑树的简单介绍，你是否明白了它们不太适合作为MySQL的索引底层数据结构？！ 至此，MySQL索引底层数据结构也就介绍完了，如有缺漏或不对的地方还请各位指正，下节我们继续介绍MySQL的索引知识。