一，索引数据结构红黑树，Hash，B+树详解

索引是帮助MySQL高效获取数据的排好序的数据结构

                这篇文章主要写一下mysql的底层数据结构以及索引是怎么支撑千万级表的快速查找。直接进入在正题，比如说，我们现在以Col2作为查询条件写一个sql：select * from t  where Col2=89 ，通过这样的一个sql可以发现，mysql在不使用索引的情况下。会进行全表扫描。会从第一条记录开始查询，一共进行6次查找，每次查找都会进行一次IO磁盘查找，这种效率是非常低的。那么Mysql显然如果不使用索引这种效率低到无法想象。所以就引入今天的话题，mysql的底层索引以及实现原理。先抛出结论Mysql底层使用的是B+树索引。

                先不说B+树索引，咱们先一个一个分析。然后在讲为什么使用B+树。这样更有助于理解Mysql为什么使用B+数索引作为底层的索引数据结构，就针对刚才那条sql语句。

select * from t  where Col2=89

                1，我们知道在不使用索引的情况下要进行6次的磁盘IO。那么如果说使用索引的话，到底如何去选择合适的数据结构呢？先来分析一下，如果说使用二叉树数据结构，就像下图显示的这种叶子节点比非叶子节点小的就放在左面，如果大的就放在右面，基于这种数据结构，只要进行两次磁盘IO就可以轻松的去找到89这个磁盘的指针。先说一下二叉树的这种存储方式，首先是以Key-value的形式去存储的。34是或者89是Key，value就是对应的磁盘文件指针。通过value找到那一条数据。

虽然说二叉树的这种索引数据结构可以提高效率。但是存在一个问题。如果说我们的索引是自增的形式呢？此时这种二叉树的数据结构还有效吗？显然是没有效的。以下图为证，因为每次新增加一个元素都是递增的。所以树的高度还是会很高。如果有500万条数据呢？如果我要检索0006这个索引字段，是不是也要经过6次磁盘IO。所以二叉树不能解决这个问题。所以mysql不可能使用这种二叉树的方式。

然后再说说第二个，在这个基础上，我们可以使用红黑树，来达到树的平衡机制，如下图。虽然说这个红黑树解决了递增索引的平衡问题，但是还是不能解决树的高度问题，比如说现在有500万条数据，这个树的高度至少有20个高度。显然也要进行大量的磁盘IO。所以说Mysql也不会使用这种数据结构作为底层的实现。

                    然后再说第三个，有的人可能已经想到了。用B树啊。没错，下面我要说的就是B树这种数据结构，B树是解决二叉平衡树的高度问题，那么是如何解决的呢？如下图：比如说15,56,77.....比如他们是主键索引，先说一下B树索引的特点：叶节点具有相同的深度，叶节点的指针为空。所有索引元素不重复。节点中的数据索引从左到右递增排列。通过这几个特点可知，也就是说，B树索引是默认排好了序的，从左向右是递增的形式，每一个节点可以更多的存储索引，通过增加点个节点的宽度来解决树的高度的问题。每一个节点有多个索引，然后每一个索引都有一个指针，这个指针是指向了下一个节点的地址。并且每一个节点的索引都对应了一个data数据空间，这个data就是对应的一条数据记录。它的工作原理是什么呢？比如说，我要查找49这个记录，那么首先，会进行一次磁盘IO把第一个节点的索引集合load到内存中来，然后跟49进行比较，比如说没找到49，那么就会从左向右进行比较。比如说找到了15和56之间的这个节点指针，那么就会通过这个指针再进行一次磁盘IO把与之对应的那个节点的数据load到内存中来。从左向右找到49.一共进行了2次磁盘IO。就找到了。但是这种B树的数据结构还是有一些小问题的。我们知道每一个小节点是Key-Value形式存储的，那么如果说这个data占用的数据量比较大的话也就意味着占用的空间就会增大，因为mysql的一个节点默认存储是16KB。如果data的数据量大的话，也就意味着，横向的存储的节点就少了。高度还是存在不可控，但是比红黑树的高度肯定要矮一些。所以说mysql对B树进行了一点儿修改，变成了B+树。现在说完了为什么mysql底层使用B+树这种数据结构，我们在来全面的分析一下B+树这种数据结构是在怎么回事儿，以及是如何存储的。

B+树，首先看一下B+树有哪些特点：1首先非叶子节点是不存储data数据的。而且节点是可以重复的。只存储索引(冗余)，可以放更多的索引，叶子节点包含所有索引字段。叶子节点用指针连接，提高区间访问的性能。然后我们说一下存储结构，比如说，我们用的是主键索引，一个整形的索引Key大概占8B的字节空间，然后与之对应的指向下一个节点的指针占用6B，（这是计算基底层规定的指针大小）。也就说6+8=14B。然后Mysql规定一个节点可以存储16KB，也就是说这一个节点能存储多少个索引呢？用16KB/14B=1170个。一个节点就是1170个索引，那么每一个与之对应的下一个节点还是1170个。那你可能会说。你的叶子节点，有data数据，假设一个data存储是1KB肯定够了。那么一个节点存储16个。那么我们算一下。可以存储多少数据。我直接说结果是1170*1170*16=21902400条数据。这也就是为什么，B+树索引这么牛逼的原因。2千多万条数据，只要进行3次磁盘IO就可以解决。其实实际上，第一层的节点，会被加载到内存里。所以说，只要进行2次磁盘IO就足够了。如果数据超过2千万条应该就要做分表操作了。这里不做介绍。了解了这些之后咱们再说说，B+树索引下面的指针，为什么会有这个指针，而且B+树的叶子节点是双向的指针，说这个问题之前，先做一点儿铺垫，我们只mysql中，除了B+树锁引以外还有一种hash索引，就是说在查找的时候，先对这个索引进行一次hash运算。每一个索引值经过hash算法之后，会和磁盘文件指针形成一个映射关系。通过这个关系就可以快速定位到那个索引所在的磁盘文件指针。所以hash索引是最快的。跟多少数据量也没有关系。但是hash索引有一个弊端，如果是范围查找那hash索引就没用了。索引我们百分之90的情况下用的都是B+树索引。那么再说，叶子节点上的双向链表指针的作用，就是说当我们用范围查找的时候，把叶子节点load到内存之后，通过这个指针可以快速的进行范围查找。起到的作用就是用来进行范围查找的。B+树索引到现在就写清楚了。下面咱们再说说Mysql的存储引擎。

二：Mysq存储引擎索引实现

mysql提供了多种存储引擎，我只介绍两种，一种是Myisam和innoDB引擎。myisam存储引擎是索引文件和数据文件是分离的(非聚集)。

mysiam存储引擎有三个文件一个是frm文件，一个是myi文件，一个是myd文件。myd文件存储是数据，myi存储是索引关系，frm存储是表的结构大概可以这样理解。mysiam存储引擎比如说我们查询49，经过两次磁盘IO以后，拿到叶子节点对应的data，其中data存储的是myd文件的磁盘文件指针。拿到这个磁盘文件指针以后。就可以找到myd文件磁盘文件指针所在的行。这样就可已找到数据了。

再来说一下innodb引擎。innodb是聚集索引，叶子节点存储的是一整行的数据，表数据文件本身就是按B+Tree组织的一个索引结构文件，聚集索引-叶节点包含了完整的数据记录。而且，innodb引擎只有两个数据库文件一个是frm，一个bid文件。索引结构和数据存储在一个文件里。下面这张图的例子是主键索引。然后在看看非主键索引的存储结构是什么样的？在说非主键索引结构之前先提两个问题：为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？先说第一问题，如果说innoDB没有主键的话，那么mysql会因为要满足B+树的结构就会去找你的唯一索引列，找不到就会生成一个类似于Rowid的东西。第二个问题，为什么是整形而且自增，因为如果不是整形的话，第一个因为存储空间可能会变大，假设你存储的是字符串，而且在进行节点插入的时候，两个节点直接会进行比较大小，我们知道B+树是从左向右递增的形式。如果是整形就不需要ASCII的计算了。也提高了效率。然后为什么是递增呢？如果说我现在有个几点是10，那么刚好我要存储一个8的节点，那么此时我发现10的这个节点正好存满了16KB。那么此时Mysql为了满足B+树的结构就会进行结构分裂。性能会下降。所以要求是递增。

innodb非主键索引的存储结构：非主键的索引叶子节点的data存储的是主键，为什么要这么做呢？因为如果说我们有主键索引，又有非主键索引的情况下，我们又要维护主键索引又要维护非主键索引，当我们insert的一条数据的时候，必须主键索引和非主键索引的数据同时维护完了才可以写入数据表。那么这种情况就有可能产生类似于分布式事务的问题，所以mysql基于这个问题，选择了非主键索引的data值存储的是主键。说白了。你的主键索引数据维护好了。我只要引入你的id就可以了。保证了一致性，也保证了节省空间的问题。缺点是做了2次磁盘IO。但是效率依然是很高的。

最后再说一下联合索引的概念。为什么要使用联合索引呢？如果说有三个索引，那么每一个索引单独建立的话，就会建立三个索引树，很费空间，如果使用联合索引，就会降低空间，我们知道B+树的存储结构是从左向右一次递增，并且排好序的。如果是联合索引首先会先根据第一个字段进行排序，从左向右，如果第一个字段相等，那么就会根据第二字段进行从左向右的排序，以此类推。