一文读懂 MySQL 索引 _生活百科

1 索引简介1.1 什么是 MySQL 的索引官方定义：索引是帮助 MySQL 高效获取数据的数据结构
从上面定义中我们可以分析出索引本质是一个数据结构，他的作用是帮助我们高效获取数据，在正式介绍索引前，我们先来了解一下基本的数据结构
2 索引数据结构2.1Hash 索引Hash 索引是比较常见的一种索引，他是通过计算出记录对应的 hash 值，然后根据计算结果，存储在对应位置。查询的时候也是根据 hash 值快速找到位置。他的单条记录查询的效率很高，时间复杂度为1 。但是，Hash索引并不是最常用的数据库索引类型，尤其是我们常用的Mysql Innodb引擎就是不支持hash索引的。
hash 索引在等值查询时速度很快，但是有以下两个问题

不支持范围查询
hash 冲突，当两条记录的 hash 值相同时，就产生了 hash 冲突，需要在后面用链表存储起来

文章插图
2.2 二叉树2.2.1 经典二叉树1、一个节点只能有两个子节点
2、左子节点的值小于父亲节点值，右子节点的值大于父亲节点的值，采用二分查找，速度较快

文章插图
经典二叉树会出现一个极端例子，就是链表，节点数据越来越大。这种情况下，二叉树搜索性能就会降低

文章插图
2.2.2 平衡二叉树平衡二叉树又称AVL树。它可以是一颗空树，或者具有以下性质的二叉排序树：

它的左子树和右子树的高度之差(平衡因子)的绝对值不超过1
它的左子树和右子树都是一颗平衡二叉树。

数字 1-6 在平衡二叉树中图示如下：

文章插图
2.3 B 树B树属于多叉树又名平衡多路查找树，可以有多叉，有如下特点
（1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
（2）子节点数：非叶节点（根节点和枝节点）的子节点数 >1、且子节点数量<=M 、且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；
（3）关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数如ceil(1.1)结果为2);
（4）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外，也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

文章插图
MySQL 中 B 树存储结构如下：

文章插图
2.4 B+ 树B+树是在B树的基础上又一次的改进，其主要对两个方面进行了提升，一方面是查询的稳定性，另外一方面是在数据排序方面更友好。MySQL 索引的底层数据结构采用的就是 B+ 树
（1）B+树的非叶子节点不保存具体的数据，而只保存关键字的索引，而所有的数据最终都会保存到叶子节点。因为所有数据必须要到叶子节点才能获取到，所以每次数据查询的次数都一样，这样一来B+树的查询速度也就会比较稳定，而B树的查找过程中，不同的关键字查找的次数很有可能都是不同的（有的数据可能在根节点，有的数据可能在最下层的叶节点），所以在数据库的应用层面，B+树就显得更合适。
（2）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。因为叶子节点都是有序排列的，所以B+树对于数据的排序有着更好的支持。