前言

MySQL索引的建立对于MySQL的高效运行是很重要的，索引可以大大提高MySQL的检索速度。打个比方，如果合理的设计且使用索引的MySQL是一辆兰博基尼的话，那么没有设计和使用索引的MySQL就是一个人力三轮车。

拿汉语字典的目录页（索引）打比方，我们可以按拼音、笔画、偏旁部首等排序的目录（索引）快速查找到需要的字。

MySQL官方对索引的定义：索引是帮助MySQL高效获取数据的数据结构

作用：快速检索

本质：数据结构

本文我们就来简单介绍下索引的数据结构

推荐一个网址：（数据结构可视化）可以帮助我们看到数据结构的变化以及流动的过程

二叉查找树

二叉查找树也称为有序二叉查找树，满足二叉查找树的一般性质，是指一棵空树具有如下性质：

1、任意节点左子树不为空,则左子树的值均小于根节点的值；

2、任意节点右子树不为空,则右子树的值均大于于根节点的值；

3、任意节点的左右子树也分别是二叉查找树；

4、没有键值相等的节点；

例：

上图为一个普通的二叉查找树，从小到大的顺序排序输出：15、20、30、50、60、70。

对上述二叉树进行查找，如查键值为30的记录，先找到根，其键值是50，50大于30，因此查找50的左子树，找到20；而30大于20，再找其右子树；一共找了3次。

局限性：

一个二叉查找树是由n个节点随机构成，所以，对于某些情况，二叉查找树会退化成一个有n个节点的线性链

因为树的高度越高，查询效率就会越低，为了维护树的高度以及平衡性，就引出了新的定义-AVL树（平衡二叉树）

AVL树（平衡二叉树）

AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。

从上面是一个普通的平衡二叉树，这张图我们可以看出，任意节点的左右子树的平衡因子差值都不会大于1。

局限性：

由于维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树。

红黑树

一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是red或black。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树(由于是弱平衡，可以推出，相同的节点情况下，AVL树的高度低于红黑树)，相对于要求严格的AVL树来说，它的旋转次数变少，所以对于搜索、插入、删除操作多的情况下，我们就用红黑树。

2）性质

1、每个节点非红即黑；

2、根节点是黑的；

3、每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的；

4、如果一个节点是红的,那么它的两儿子都是黑的；

应用：

1、广泛用于C++的STL中，Map和Set都是用红黑树实现的；

2、著名的Linux进程调度Completely Fair Scheduler，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间；

3、IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查；

4、Nginx中用红黑树管理timer，因为红黑树是有序的，可以很快的得到距离当前最小的定时器；

5、Java中TreeMap的实现；

B树

B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉，B树每个内节点有多个分支)，与红黑树相比，在相同的的节点的情况下，一颗B/B+树的高度远远小于红黑树的高度(在下面B/B+树的性能分析中会提到)。B/B+树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成，而CPU的速度非常快，所以B树的操作效率取决于访问磁盘的次数，关键字总数相同的情况下B树的高度越小，磁盘I/O所花的时间越少。

一个m阶B树性质：

⑴ 树中每个结点至多有m个孩子；

⑵ 除根结点和叶子结点外，其它每个结点至少有m/2个孩子；

⑶ 若根结点不是叶子结点，则至少有2个孩子；

⑷ 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息；

B+树

B+树是应文件系统所需而产生的一种B树的变形树（文件的目录一级一级索引，只有最底层的叶子节点（文件）保存数据）非叶子节点只保存索引，不保存实际的数据，数据都保存在叶子节点中。所有的非叶子节点都可以看成索引部分！

性质：

1.根节点至少有两个子结点。

2. 非叶子结点不保存数据，只保存关键字，只起到索引的作用。

3. 非叶子结点的关键字全部存在于叶子结点。

4. 叶子结点存储所有关键字和数据，叶子结点按照关键字从小到大顺序链接。

5.每一个父节点的元素都出现在子结点中，是子结点的最大（最小元素）。

B 树和B+树性能的比较

B+树是基于B树的一种变体，有着比B树更高的查询性能，B+树的每一个叶子节点都带有指向下一个节点的指针，形成一个有序链表

另外B+树h还有一个特点，这个特点实在索引之外，却是至关重要的特点，那就是卫星数据（指的是索引元素所指向的数据记录，比如数据库中的的某一行。在B树中，无论中间节点还是叶子节点都带有卫星数据）的位置

而在B+树中，只有叶子节点带有卫星数据，其余节点仅仅是索引，没有任何数据关联

B+树的好处主要体现在查询性能上。我们可以通过单行查询和范围查询去做分析。

在单行查询时，B+树会自动向下逐层查找节点，最终匹配到叶子节点。比如我们查找的是元素3

看起来虽然和B树差不多，但是

1.首先B+树中间节点没有卫星数据，所以同样大小的磁盘页就可以存储更多的节点，这就意味着在数据量相同情况下，B+树的结构比B树更加‘矮胖’，查询次数也会更少

2.其次B+树的查询必须查找到叶子节点，而B树只要找到匹配元素即可，无论是匹配元素在中间节点还是叶子节点。这就导致了B树的查询并不稳定（最好情况只查根节点，最坏情况查到叶子节点)。B+树每一次查找都是稳定的

范围查询：

B树做范围查询只能依靠繁琐的中序遍历（ 序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。）。比如要查询3-11的元素

B树的范围查找过程：

而B+树的范围查询只需要在链表上做遍历

所以综上所述：

B+树比B树的优势有三个：

1.IO次数少；

2查询稳定；

3范围查询简便