一， 索引的本质

帮助mysql高效的获取数据的排好序的数据结构。这里主要讲解mysql下的innodb类型所对应的表中的索引

使用索引的原因：因为这个数据最终是存储在这个磁盘里面的，而磁盘里面并不能保证这个数据的顺序性，因此可以借助于这个索引，让这个数据以键值对的方式存储在一棵树上面，key存这个值，value存这个对应的磁盘地址，这样就类似于一本书的页目录，让其快速找到各个值。

二，索引对应的数据结构的类型

这里主要讲解五种对应的数据类型，分别是hash，二叉树，红黑树，b树，b+树。接下来主要讲解为什么在mysql数据库中，最终使用了b+树作为索引的数据结构，接下来一一讨论其他的数据结构的不足之处以及b+树的优点。

1，hash

对于哈希这种数据结构，只需要对索引进行一次hash计算就可以定位出数据的存储结构，因此很多情况下hash索引要比b+树索引更加高效。如下，这里采用数组加链表的方式，假设hash数组只能存7个数，那么经过hash计算，就是对7进行求余，将相同的值使用尾插法放在后面的链表中。假设找18，那么经过io操作可以直接找到下标为4的数组，并在内存中遍历后面的链表，内存中遍历的时间可以忽略不计，那么默认的时间复杂度为O(1)。

为什么速度这么快还是没有使用使用hash作为底层的数据结构呢？其一，就是hash碰撞了，这里不细说了，学过java集合的人应该没有谁不知道hash碰撞是什么的吧；其二就是一个最主要的原因，hash主要适用于 = 查询 ， 而不适用于范围查询。如查找 10 - 15，那么10在数组3后面的链表中，12在5后面的链表中，依次类推，自然而然就不适用了。因此在最坏的情况下，时间复杂度应该会等于O(n)，并且可能造成索引失效，或者直接走全局索引，因此在mysql中百分之九十九不会轻易适用hash这种数据结构作为索引底层的。

而选择这个b+树的原因是因为在叶子结点加入了双向指针，这样就解决这个范围查找的问题。

2，二叉树

二叉树其特性为，左边值小于根结点，右边值大于根结点。因此在一般的满二叉树或者完全二叉树中，其查找所对应的平均时间复杂度为 log (n)。但是如果存在以下形式，在最坏的情况下，假设每层只有一个对应的右孩子结点，那么次二叉树又相当于一个链表了，那么对应的时间复杂度又是之前的O(n)了。因此，二叉树也不适用于作为作为索引的底层的数据结构。并且随着数据量的增大，导致树的高度很高，因此二叉树不能作为索引的底层。

3，红黑树

由于上面的二叉树会出现每层只有一个结点的情况，那么使用红黑树对其进行改造。红黑树，又被称为平衡二叉树，即存在叶子结点的层相减最大不能超过1。因此在这里，可以将它看做成一棵完全二叉树或者满二叉树。而一棵完全二叉树或者满二叉树所对应的时间复杂度为O log(n)，并且也会随着数据数量的增大会导致红黑树的高度非常的高，因此红黑树也不能作为索引的底层。（想了解红黑树的可以参考一下其他文章）

4，b树

为了改进红黑树，接下来使用了b树。由以前的一个结点存储一个键值对变成了一排连续的地址存储多个键值对。在每个key中，主要存储值。如下图，在第一块连续的地址中，key主要存储15,56,77等值，而对于的value，即为图中的空白部分，则存储下一个连续空间的地址，

并且在每个key中，还带有data这个数据。假设在数据库中，索引15刚好为我们想要找到的值，那么data则表示这个表中的一列数据。就红黑树而言，这样确实可以降低树的高度，并且加快数据的查询效率，但是仍没有用此来作为索引的数据结构底层。

b树的特点：

1，每个叶子结点具有相同的深度，叶结点的指针为空

2，所有的索引元素不重复

3，结点中的数据索引值的大小从左到右递增排序

4，每个连续地址中对应的结点都有对应的data元素

5，b+树

即改造后的b树。当然，其有的好的特点没变，依旧是将一块连续的区间当做一个大结点，大结点由各个小结点的键值对组成。但是相对于b树而言，在一列大小空间有限的连续地址中，在每个结点中加入data，这样会显得非常的浪费空间，并且在大量数据的同时，也会显得树的高度比较高。

而b+树为了解决这个问题，在接下来连续区间都使当前结点作为当前节点的指针所对应的下一片区域的头结点，即第一片区域有15，那么15对应的value所对应的区域的头结点也为15，这样的话直到叶子结点才会出现索引15所对应的在表中的data。

因此b+树的data都是在叶子节点上的，因此每一个连续地址可以存更多地键值对，并且降低了树的高度，也就加快了查询了效率。并且在叶子结点里面，包含了表中的所有的数据，数据从左到右依次递增。

在范围查询这一块，每个叶子结点组成一个循环的链表，这样轻松的解决了b树要重新回到根结点遍历的问题，提高区间的访问性能，支持范围查询，这样也加快了查询的效率

6，b树和b+树的区别和联系

6.1，相同点

1，都是由多个大的区间组成，并且每个区间都是连续，并且由多个键值对组成的

2，每个连续的区间里面结点的值的大小都是从小到大排序好的

3，每个结点由键值对组成，每个key对应的就是索引值，每个value对应的就是下一块区间的存储地址，就是对应的磁盘物理地址

4，每个页目录的大小都是16kb。

6.2，不同点

1，b树的data则是存储在每个区间所对应的结点上，并且每个结点不能重复；而b+树将data放入到叶子结点，这样也将导致对应的连续区间的头结点为上一个区间的结点，上图可以清晰的表示。

2，b树的所有的叶子节点上没有循环链表，并且叶子节点的指针指向null，而b+树的所有的叶子节点上组成了一个循环列表。

7，b+树的查询方式

将第一层中全部的数据通过磁盘io交互操作全部查到内存中，再利用二分查找，将下一个对应的磁盘地址找出，通过磁盘地址将下一个连续区间的值全部找出，再把要找的值依次对比，里面的值都是从小到大排序的，并且在内存中查找，所以查找的时间可以忽略不计，然后一直重复，直到找到叶子结点，将对应的data找到。

已知每一页目录的大小为16kb，那么假设id为int类型占8字节，指针占6字节，那么一页大概可以存储16k除14等于1142个数据，树的第二层大概可以有1142个页目录，假设第三层为叶子结点，那么叶子结点存储了data数据域，假设每个值为1kb，那么第三层的每个页目录可以存储16个数据，那么在三层高度的情况下，b+树可以存储1142x1142x16，大概可以存储2000w条数据。

即理论上2000w条数据用索引优化也是不会太慢的，忽略根目录在内存中查找的有序结点时间，即只需要经过3次的io交互，即可查询到对应的值，当然一般在数据超过2000万时，一般都会选择分库分表了！

当然，可以提前将第一块连续的区间放入到内存中，其实就是将对应的地址放入到内存中，这样也可以加快查询的效率。

因此，b+树就成为了最适合索引的数据结构了！

三，为什么更加建议使用自增主键

首先自增主键，其值都是偏小，相对于uuid或者其他的业务id来说，自增主键可以省略大量的空间；其实最主要还是因为该索引的底层为b+树，最后再形成这个树会进行一个从大到小的排序，如果用其他的id，如uuid在插入数据时比较大小的效率会比较慢。

以uuid为例子，截取uuid的前32位，其主要有一些 ‘-’ 或者 字母数字等组成。带有字母和’-'的组成的uuid在b+树的索引中，在比较大小时还需要经过 ascll 的转换，这里在分区间块时，由于在插入到数据时所有的数据都是需要经过排序的，这样会造成排序时间的浪费以及性能的损耗。

如下图，data以及循环链表等指针均省略。在这个b+树中，存储8,9的那个连续区间块满了，那我要存储一个为14的数据，该怎么存？由于这个主键id所对应的值一定是在叶子结点的，15这个节点所对应的连续区间里面的值都要大于等于15，而由于不采用自增id，所以在8,9那个区域存满数据的情况下，就只能页分裂了

就会出现以下情况，会将14取代原来15的位置，并将15后移到14后面，从而来平衡新的结点，这样的话就可以在查询时利用b+树的新特性了，从而实现高效的查询了！

要是在这个基础上再就加入一个13，由于上面的结点为3,8,14的那一个区域里面的结点满了，又要平衡新的结点，那么就会出现大结点断裂以及新结点的出现，并且可能出现新的分页

这就解释了为什么在使用主键时建议使用自增主键了，完全是为了更加符合b+树的结构以及特性。并且以防出现大结点的断裂，重新平衡结点。

四，总结

画图难受，丑还累！