索引是什么？

索引是对表中一列或多列数据有序排列的一种数据结构。由此可见，索引是一种有序的数据结构，作用是为了快速定位要查找到数据。

mysql索引采用什么样的数据结构

mysql中索引数据结构有两种，一种是hash索引，一种是BTree。

从mysql的官网可以看到mysql存储引擎对这两种索引的支持情况：

https://dev.mysql.com/doc/refman/5.7/en/create-index.html

hash索引

hash索引平时使用较少，常用的存储引擎中只有MEMORY Storage Engine显示支持了hash索引。

hash索引是将数据的hash值存在一个hash表里（个人理解类似于java中的HashMap），hash表是无序的，这样的数据结构更适用于精确匹配，无法进行范围查找，同时由于hash值是通过数据全部内容计算而来的，因此无法进行部分匹配。但是精确查找的情况下时间效率为O（1），效率是很高的。

BTree索引

BTree是我们工作中最常用到的索引数据结构，BTree的索引数据结构实际上是B+Tree，为什么要采用B+Tree而不是BTree呢？

我们先了解一下BTree和B+Tree的区别

BTree的结构如下图所示：

 由上图可以看出BTree的每个节点都包含索引和数据，索引是有序的。

B+Tree结构如下图所示：

 可以看出，B+Tree跟BTree的结构是比较相似的，区别在于：

B+Tree只有叶子节点上存储键值和数据，非叶子节点只存键值，从而在相同空间的情况下每一层的非叶子节点可以存储更多的键值，有效降低树的高度，减少I/O次数，更好的提高查询效率。此外B+Tree的叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

InnoDB存储引擎中默认页的大小为16KB，一般表的主键类型为INT（4个字节）或BIGINT（8个字节），指针类型也一般为4或8个字节，因此一页中可以存储的键值为：16KB/16B,为方便计算，约为1000个，那么三层的B+Tree存储的索引节点可以达到1000*1000*1000个。

Innodb存储引擎设计的索引数据是常驻内存的，通过索引查找数据一般1-3次磁盘I/O即可。

Innodb与Myisam存储引擎对于索引的不同存储方式

myisam数据在计算机上存储的文件如下图

.frm文件存的表结构，.MYD文件存储的是表数据，.MYI文件存储的是索引，因此Myisam存储引擎中的索引和数据是分开存储的，索引结构B+Tree的叶子节点中存储的是该行数据的磁盘地址。

Innodb在计算机上存储的文件如下：

 其中.frm文件存储的是表结构信息，.ibd文件存储的是索引和数据。

在InnoDB中，会根据主键索引的顺序排列数据，没有主键索引会选择一列不重复数据作为主索引，若没有找到不重复数据，InnoDB会创建隐藏列充当主索引，因此建议创建表最好指定主键，主键最好采用int或bigint类型，会有更高效率。

在InnoDB中，创建其他索引的话，索引中存的是主键值，然后根据主键值查找到数据。

组合索引和最左匹配原则

创建组合索引时，数据库底层给组合索引排序时，会先根据第一个字段排序，第一个字段相同的，根据第二个字段排序，以此类推，因此第一个字段在总体上是有序的，后面的字段在前一个字段一样的基础上有序，总体上是无序的，因此当使用where条件查找数据时，直接使用第二个字段作为条件是不会使用到索引的。