一、什么是索引

在mysql中,索引是一种特殊的数据库结构,由数据表中的一列或多列组合而成,可以用来快速查询数据表中有某一特定值的记录。通过索引,查询数据时不用读完记录的所有信息,而只是查询索引列即可，索引是帮助Mysql高效获取数据且以排好序的数据结构，直观的说，索引就类似书的目录页，没有目录（即索引）我们就要一页一页的找，有了目录（索引）我们就可以按照目录中标记的页数去相应的页数去查找。

二、为什么要用索引

例如，我们通过查询语句查询一条记录：select * from table where Col2 = 85,如果没有索引的话，那么它将从第一行[1,35]开始找，一行一行的找，直到找到[6,85]这条数据，并且数据存放的位置也不规则，拿取一行记录就需要与磁盘进行一次交互，即IO读取，如果数据多，这种效率将会很低下，只要把这种交互次数控制在一定范围之内，那他的效率将会比一行行查找要高很多，如给col2加索引，来执行select * from table where Col2 = 85，通过二叉树接口，第一次我们查到的是35，85比35大，所以查找右子节点，查到85，与条件种的85为一条数据，所以，这里就只需要两次交互就可以查到。所以索引就诞生了。

三、索引的数据结构

1、二叉树

1.1、二叉树的特点：

　　1、每个节点最多有两个子树，所以二叉树不存在度大于2的节点（结点的度：结点拥有的 子树的数目。），可以没有子树或者一个子树。
　　2.左子树和右子树有顺序，次序不能任意颠倒。
　　3、二叉树支持动态的插?和查找，保证操作在O(height)时间，这就是完成了哈希表不便完成的?作，动态性。但是?叉树有可能出现worst-case，如果　　　　　　　　　　　　 输?序列已经排序，则时间复杂度为O(N)。为什么不用二叉树来作为索引，就是因为二叉树的worst-case，如果输入序列是排好序的，那么二叉树的结构就会变成如下图所示的特殊状态：

所以二叉书并不适合去做索引，遇到这种极端情况，就会导致有索引和无索引效果一样。

2、平衡二叉树

AVL树是严格的平衡二叉树，所有节点的左右子树高度差不能超过1；AVL树查找、插入和删除在平均和最坏情况下都是O(lgn)。AVL实现平衡的关键在于旋转操作：插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时，最多只需要1次旋转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(lgn)。由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛。

3、红黑树

与AVL树相比，红黑树并不追求严格的平衡，而是大致的平衡：只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。从实现来看，红黑树最大的特点是每个节点都属于两种颜色(红色或黑色)之一，且节点颜色的划分需要满足特定的规则。在java8中的HashMap就是使用链表+红黑树。红黑树的缺点就是太高了，如下图所示：

当数据量特别大的时候，树的高度很高，假设你要查找的节点为当前树的叶子节点，那么要查找这个节点，至少要循环h(这棵树的高度)次，所以说，红黑树在这种情况下也并不适用。

4、B-Tree

Tree就是我们常说的B树，它是一种多路搜索树而非二叉树，使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度

在B树中，每个节点包含：

1、本结点所含关键字的个数；

2、指向父节点的指针

3、关键字

4、指向子节点的指针

对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。各结点的关键字和可以拥有的子结点数都有限制，规定m阶B-tree中，根结点至少有2个子结点，除非根结点为叶子节点，相应的，根结点中关键字的个数为1~m-1;非根结点至少有[m/2]([]，向上取整)个子结点，相应的，关键字个数为[m/2]-1~m-1。

B-tree有以下特性:

1、关键字集合分布在整棵树中;

2、任何一个关键字出现且只出现在一个结点中; 所有索引元素不重复

3、搜索有可能在非叶子结点结束;

4、其搜索性能等价于在关键字全集内做一次二分查找;

5、自动层次控制;

6、所有叶节点都在同一层，每个节点最多有m-1个key，并且以升序排列

叶节点具有相同的深度，叶节点的指针为空

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最低搜索性能为:

其中，M为设定的非叶子结点最多子树个数，N为关键字总数;

所以B-树的性能总是等价于二分查找(与M值无关)，也就没有B树平衡的问题;

由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点;删除结点时，需将两个不足M/2的兄弟结点合并。

B树的查询：

B树是二叉排序树的扩展，二叉排序树是二路查找，B-树是多路查找。因为B-树节点内的关键字是有序的，在节点内查找的时候除了顺序查找之外，还可以用折半查找提高效率，B-树的具体查找步骤可以参照折半查找方法。

以查找42为例：

首先获取关键点的关键字进行比较，当前根节点关键字为30，42>30，所以找右子节点，拿到关键字39，45，39<42<45，所以直接找到39和45的中间的节点，拿到40,42,44,因为42=42，所以直接返回关键字和指针信息（如果树结构中没有包含所要查找的节点则返回null）

5、B+Tree（B-Tree变种）

B+树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与二叉树恰好相反。

B+树的

非叶子节点不存储data，只存储索引（冗余），可以放更多的索引，只有叶子节点才存储数据

叶子节点包含所有索引字段

叶子节点增加了一个指向相邻子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成一个有序链表的结构，提高区间访问的性能。

与B树相比它的不同体现在：

(1).如果非叶子节点包含n个关键码，则这个节点有n个子树。

(2).非叶子节点仅包含关键码信息，叶子节点包含关键码以及含有这个关键码的记录的指针。所以查找时，B+树必须到达叶子节点才会命中。

(3).叶子节点包含有兄弟叶子节点的指针，而且叶子节点的关键码值是有序的，有利于遍历。

(4).所有的非叶子节点可看成是索引部分(稀疏索引)

为什么说B+树比B树更适合实际应用中作为操作系统的文件索引和数据库索引

(1)B+树的磁盘读写代价更低

非叶子节点包含的信息更少，如果把同一节点的所有信息放在一个磁盘块中，则可以比B树放入更多的关键码。一次读入内存当中(读一个块)就能读入更多的关键码，所以降低了磁盘I/O总数。

(2)查询效率更加稳定

对任何关键字的查找都必须从根节点走到叶子节点，路径长度相同，所以对每条数据的查询效率相当，在存储相等的关键字上，B+树树的高度会更低。

(3)B树在提高磁盘I/O性能的同时并没有解决元素遍历效率低下的问题。而B+树因为叶子节点有链指针存在，所以遍历叶子节点即可以实现对整棵树的遍历。而在数据库中基于范围的查询是非常频繁的，B+树就能更好的支持。

四、存储引擎索引实现

数据存储引擎是形容数据库表层面的，而不是形容数据库的，我们点击表设计，在选项中证实这一问题。

1、MyISAM存储引擎索引实现

MYISAM基于ISAM存储引擎，并对其进行扩展。它是在web、数据仓储和其他应用环境下最常用的存储引擎之一。MYISAM拥有较高的插入、查询速度，但不支持事务和外键。所以对事务完整性没有要求或者以SELECT、INSERT为主的应用基本上都可以使用这个引擎来创建表。?数据文件和索引文件可以放置在不同的目录，平均分布 IO，获得更快的速度。要指定索引文件和数据文件的路径，需要在创建表的时候通过 DATA DIRECTORY 和 INDEX DIRECTORY 语句指定，也就是说不同 MyISAM 表的索引文件和数据文件可以放置到不同的路径下。文件路径需要是绝对路径，并且具有访问权限。

MYISAM存储引擎的索引

1)MyISAM默认使用B+Tree索引，只把索引载入内存，存储的是数据的索引

2)MyISAM数据库中的数据是按照插入的顺序保存，在每个索引节点中保存对应的数据行的地址，理论上说主键索引和其他索引是一样的。

3)MYISAM的索引文件和数据文件是分离的(非聚集)

MYD文件存的是表的数据

MYI文件存的是表的索引

frm文件存的是表的结构

2、INNODB存储索引实现

InnoDB存储引擎提供了具有提交、回滚和崩溃恢复能力的事务安全。但是对比MYISAM的存储引擎，InnoDB写的处理效率差一些并且会占用更多的磁盘空间以保留数据和索引。但是由于其其他方面的优势，在5.5版本之后，MYSQL的默认引擎变成了InnoDB.

2.1InnoDB索引实现(聚集)

InnoDB表只有一个聚集索引

表数据文件本身就是按B+Tree组织的一个索引结构文件，聚集索引-叶子节点包含了完整的数据记录

InnoDB存储引擎存储数据库数据，一共有两个文件

frm文件：表的结构

ibd文件: 数据和索引存储文件。数据以主键进行聚集存储，把真正的数据保存到叶子节点中

接下来我们能也从几个问题当中去了解InnoDB索引引擎

1、为什么建议InnoDB表最好建主键？

因为在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的Key是数据库的主键，因此InnoDB表数据文件本身就是主索引。综上所述，InnoDB数据文件本身要按主键聚集，所以InnoDB要求表必须有主键(MYISAM可以没有，因为数据和索引是分开的)，如果没有指定，那么Mysql系统会自动选择一个所有元素均不相等的列作为主键，如果不存在这种列，则Mysql自动为InnoDB表生成一个隐含字段作为主键，这个字段长度未6个字节，类型为长整型。

2、为什么推荐使用整型的自增主键？

因为B+Tree再找数据的时候会去比较大小，整型数值比大小要相对简单和快速，且索引节点占的内存会更小。再有就是主键id是非自增的，这个时候就会导致页分裂,也会导致B+树节点分裂。

什么是页分裂：

首先来一张数据页的图

上面就是数据也的结构了，两个数据页之间会有指针指向上一个和下一个数据页，形成一个双向链表，（也就是InnoDB中B+Tree的叶子节点）在数据页中存储的就是一行行数据了，每个数据行之间会有单向指针连接，组成一个单向链表，假设你不停的往表里插数据，那么刚开始就会在一个数据页里面插入数据，比如说我们在左侧的数据页中插入数据，先插入主键id为1，3，5的数据，数据越来越多，我们就要搞另外一个数据页，这个数据页里面我们就插入了主键id为2，4，6的数据，关键点来了，当我们使用索引的时候，最基本的条件就是后面数据页中的数据行主键值要都大于前一个数据页中数据行的主键值，所以，当我们发现后一个主键id要小于前一页的主键id值，我们就要进行数据挪动，从而满足索引的基本要求，这个过程就是页分裂如下图所示：

1）为了索引更快找到数据所以进行页分裂有以下几个作用：

读操作：对索引来说，其实就是通过平衡二叉树不断减少要筛选的数据，而主键值就是筛选的标准，以尽快定位到我们需要的数据。

写操作：在平衡二叉树中，假设插入的数据的主键是自增长的，那么根据二叉树算法会很快的把该数据添加到某个节点下，而其他节点不用动；但是如果插入的是不规则的数据，那么每次插入都会改变二叉树之前的数据状态。从而导致了页分裂。直白一点来讲就是为了更快的找到需要的数据。

那么从B+树的角度来看也可以看出，当插入非自增的数据时，B+树也会进行分裂，详情如下个动图所示：

3、为什么非主键索引结构叶子节点存储的是主键值？

我们用col3这个列建索引，注意：InnoDB表只有一个聚集索引

为了节省存储空间，为了保证数据的一致性，减少他的复杂度，减少了出现行移动或者数据页分裂时二级索引的维护工作（当数据需要更新的时候，二级索引不需要修改，只需要修改聚簇索引，一个表只能有一个聚簇索引，其他的都是二级索引，这样只需要修改聚簇索引就可以了，不需要重新构建二级索引）否则，你就需要在每个索引文件中进行数据更新。

五、联合索引的底层存储结构

然后我们建立联合索引

alter table user add index idx_name_age (name,age)

索引是帮助MySQL高效获取数据的排好序的数据结构，联合索引想当然的就是已经排好序的B+树结构，我们这里使用了一个三个字段的联合索引，那么他是如何存储的呢？带着这个问题我们一起取了解一下联合索引的存储结构。

1、索引最左前缀原理

通常我们在建立联合索引的时候，也就是多个字段建立索引，mysql都会让我们选择索引的顺序，比如我们想在a,b,c三个字段建立一个联合索引，我们可以选择自己想要的优先级，a、b、c,或者是b、a、c 或者是c、a、b等顺序。为什么数据库会让我们选择字段的顺序呢？不都是三个字段的联合索引么？这里就引出了数据库索引的最左前缀原理。

mysql建立多列索引（联合索引）有最左前缀的原则，即最左优先，如：

如果有一个2列的索引(col1,col2),则已经对(col1)、(col1,col2)上建立了索引，当然在红黑树中，也是排好序来维护此索引；

如果有一个3列索引(col1,col2,col3)，则已经对(col1)、(col1,col2)、(col1,col2,col3)上建立了索引；

select * from table where c = '1'

这个sql语句是不会走index1索引的，

select * from table where b =‘1’ and c ='2'

这个语句也不会走index1索引。

比如：索引index1:(a,b,c)有三个字段，我们在使用sql语句来查询的时候，会发现很多情况下不按照我们想象的来走索引。

什么语句会走index1索引呢？

答案是：

select * from table where a = '1'
select * from table where a = '1' and b = ‘2’
select * from table where a = '1' and b = ‘2’ and c='3'

我们可以发现一个共同点，就是所有走索引index1的sql语句的查询条件里面都带有a字段，那么问题来了，index1的索引的最左边的列字段是a，是不是查询条件中包含a就会走索引呢？

select * from table where a = '1' and c= ‘2’

这个sql语句呢？

这也是最左前缀原理的一部分，索引index1:(a,b,c)，只会走a、a,b、a,b,c 三种类型的查询，其实这里说的有一点问题，a,c也走，但是只走a字段索引，不会走c字段。我们可以发现一个共同点，就是所有走索引index1的sql语句的查询条件里面都带有a字段，那么问题来了，index1的索引的最左边的列字段是a，是不是查询条件中包含a就会走索引呢？

那么这是为什么呢？

如上图所示，我们给(name,age,id)三列建联合索引，你们可以发现，在name相等的情况下（篮框部分），age字段（红框部分）的数据是有序的，但是放在整张表中看去，age字段(红框部分)的数据是乱序，何为索引？索引是帮助MySQL高效获取数据的排好序的数据结构，而age字段放在整张表中已经是乱序，已经不符合索引的原理，例如我想找到age为12的数据，如果是排好序的，我就在找到他以后就不需要再继续往下找了，因为后面的都是比我大的，但是在乱序的情况下，我就需要全表扫描进行寻找，有索引和无索引效果一样的，所以

select * from table where a = '1'
select * from table where a = '1' and b = ‘2’
select * from table where a = '1' and b = ‘2’ and c='3'

只有上述三句会走联合索引，三个字段以此类推...

附：

1、回表：

通过非主键索引查询数据时，会先查找到主键索引，然后再到主键索引上去查找对应的数据，这个过程叫做回表

2、联合索引和覆盖索引

联合索引：指索引中包含多个列

覆盖索引：指的是从索引中可以得到所有想要查询的列

比如

select id，age from user where name = ‘a’ and age = 12

联合索引是说的是where后面的部分，即查询条件；覆盖索引是说的select后面的部分，即查询列。
假设我们有id(主键)，age，adderss,name这四个字段，且age，name两列为联合索引的两个列

select id，age from user where name = ‘a’ and age = 12。

这是覆盖索引，因为不会回表查询。

因为联合索引的叶子节点就包括联合索引中包含的列（age，name）还有主键(id)，所以不需要回表。

select id，address from user where name = ‘a’ and age = 12

这不是覆盖索引，因为会回表查询。address并不存在于联合索引的叶子节点之中，所以需要根据主键值进行回表查询