理解Mysql索引的原理和数据结构有助于我们更好的使用索引以及进行SQL优化，索引是在存储引擎层面实现的，所以不同的引擎实现的索引也有一定的区别，但是在生产环境中，我们最常用的就是InnoDB引擎和B树索引，OK，那本文要讨论的重点也同样是 InnoDB引擎下的B树索引 。
创新互联的客户来自各行各业，为了共同目标，我们在工作上密切配合，从创业型小企业到企事业单位，感谢他们对我们的要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。专业领域包括网站制作、网站设计、电商网站开发、微信营销、系统平台开发。
我们建立一个表来进行测试，表的DDL如下所示，我们要关注的是表t_book上的主键索引id和name author publish_date三列组成的索引test_index。
Mysql中的B树索引是使用B+树实现的，关于B+树的数据结构个人认为美团点评技术博客中Mysql索引原理及慢查询优化一文中介绍的非常详实，B+树的数据结构如下图所示。
图中浅蓝色块即磁盘块，根节点磁盘块中存储17和35两个数据，其中指针P1指向小于17的数据，指针P2指向大于17小于35的数据，指针P3指向大于35的数据。显然通过B+树索引查询数据与B+树的高度有关，如上图的B+树索引查找一个叶子节点的数据只需要三次磁盘IO，对于Mysql来说三层的B+树可以索引上百万的数据，这对于查询效率的提升是巨大的。
总结起来Mysql中B树索引有以下关键特点：
Mysql中的B树索引有两种数据存储形式，一种为聚簇索引，一种为二级索引。
InnoDB一般会使用表的主键来作为聚簇索引，如果一个表没有主键（不建议这么玩）InnoDB会选用一个唯一非空索引来代替，如果没有这样的索引，InnoDB会隐式建立一个聚簇索引。聚簇的含义即是数据行和相邻的键值紧凑的存储在一起，占据一块连续的磁盘空间，因此通过聚簇索引访问数据可以有效减少随机IO，通常使用聚簇索引查找比非聚簇索引查找速度更快。以我们建立的表t_book为例，聚簇索引即为自增主键id，其B树索引数据结构可以用下图来表示。
聚簇索引有以下关键特点：
InnoDB的B树索引中除了聚簇索引，就都是二级索引了，二级索引的含义是索引的叶子节点除了存储了索引值，还存储了主键id，在使用二级索引进行查询时，查找到二级索引B树上的叶子节点后还需要去聚簇索引上去查询真实数据，但是这里有一种特殊情况，即查询所需的所有字段在二级索引中都可以获取，此时就不需要再去回表查数据了，这种情况就是索引覆盖（EXPLAIN中EXTRA列中会出现USING INDEX，本文只关注索引结构，不详细讨论索引覆盖等技术的使用，如果深入理解索引的数据结构，索引覆盖等技术也没有那么神秘）。
在我们的测试表t_book中，test_index即为二级索引，由于我们把除了主键id所有的列都作为一个联合索引，所以在这个表上的查询都可以使用索引覆盖技术，但是具体生产环境中也不建议总是采用这种做法，索引列的增加也会增大插入更新数据时的索引更新成本，具体的优化要视具体情况决策。t_book上的二级索引test_index的索引结构由下图表示。
通过以上结构，我们可以推断出二级索引的以下关键特点：
索引覆盖：
最左前缀匹配：
二级索引可以说是我们在Mysql中最常用的索引，通过理解二级索引的索引结构可以更容易理解二级索引的特性和使用。
最后聊点轻松的索引结构，哈希索引就是通过哈希表实现的索引，即通过被索引的列计算出哈希值，并指向被索引的记录。
哈希索引有如下特性：
Mysql索引原理及慢查询优化
高性能Mysql 第三版
正常MySQL底层存储索引默认使用的是B+树,但是如果设立了分区表的情况下,他的底层是如何进行存储的呢?
查看MySQL对应的自己电脑上面的安装目录下,是有一个ibd文件,用innblock和bcview两个小工具，(github上可以搜到),便可以实现对ibd文件的查看,通过对比着没有设立分区的表的ibd文件,就可以看出来
分区表会将索引分成分区个个数的索引树来存储索引，也就是分开存储。
本节课主要关注InnoDB，但是这里讨论的原理对于任何支持聚簇索引的存储引擎都是适用的。
叶子节点包含了全部数据，其他节点只包含索引列。InnoDB将通过主键聚集数据，也就是说上图中的“被索引的列”就是主键列。如果没有定义主键，InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引InnoDB会隐式定义一个主键来作为聚簇索引。
如果主键比较大的话，那辅助索引将会变的更大，因为 辅助索引的叶子存储的是主键值；过长的主键值，会导致非叶子节点占用占用更多的物理空间
所以建议使用int的auto_increment作为主键
主键的值是顺序的，所以 InnoDB 把每一条记录都存储在上一条记录的后面。当达到页的最大值时，下一条记录就会写入新的页中。一旦数据按照这种顺序的方式加载，主键页就会近似于被顺序的记录填满。
聚簇索引的数据的物理存放顺序与索引顺序是一致的，即：只要索引是相邻的，那么对应的数据一定也是相邻地存放在磁盘上的。如果主键不是自增id，那么可以想 象，它会干些什么，不断地调整数据的物理地址、分页，当然也有其他一些措施来减少这些操作，但却无法彻底避免。但，如果是自增的，那就简单了，它只需要一 页一页地写，索引结构相对紧凑，磁盘碎片少，效率也高。
因为MyISAM的主索引并非聚簇索引，那么他的数据的物理地址必然是凌乱的，拿到这些物理地址，按照合适的算法进行I/O读取，于是开始不停的寻道不停的旋转。聚簇索引则只需一次I/O。（强烈的对比）
不过，如果涉及到大数据量的排序、全表扫描、count之类的操作的话，还是MyISAM占优势些，因为索引所占空间小，这些操作是需要在内存中完成的。
MyISM使用的是非聚簇索引， 非聚簇索引的两棵B+树看上去没什么不同 ，节点的结构完全一致只是存储的内容不同而已，主键索引B+树的节点存储了主键，辅助键索引B+树存储了辅助键。表数据存储在独立的地方，这两颗B+树的叶子节点都使用一个地址指向真正的表数据，对于表数据来说，这两个键没有任何差别。由于 索引树是独立的，通过辅助键检索无需访问主键的索引树 。
所以说，聚簇索引性能最好而且具有唯一性，所以非常珍贵，必须慎重设置。 一般要根据这个表最常用的SQL查询方式来进行选择，某个字段作为聚簇索引，或组合聚簇索引 ，这个要看实际情况。
聚簇索引和非聚簇索引的数据分布有区别，主键索引和二级索引的数据分布也有区别，通常会让人感到困扰和以外，下面通过一个列子来讲解InnoDB和MyISAM是如何存储数据的：
该表的主键取值1~10000，按照随机顺序插入并使用optimize table命令做了优化。换句话说，数据在磁盘上的存储方式已是最优，但行的顺序是随机的。列col2的值是从1~100之间随机赋值，所以有很多重复的值。
MyISAM的数据分布很简单，所以先介绍它。MyISAM按照数据插入的顺序存储在磁盘上，如下图所示：
在行的旁边显示行号，从0开始递增。因为行是定长的，所以MyISAM可以从表的开头跳过所需的字节找到需要的行。
col2上的索引
事实上，MyISAM中主键索引和其他索引在结构上没有什么不同。主键索引就是一个名为PRIMARY的唯一非空索引。
InnoDB支持聚簇索引，所以使用不同的方式存储同样的数据。
第一眼看上去，感觉和前面的没什么区别，但是该图显示了整个表，而不是只有索引。因为在InnoDB中，聚簇索引就是表，所以不像MyISAM那样需要独立的行存储，这也是为什么MyISAM索引和数据结构是分开的。
聚簇索引的每一个叶子节点都包含了主键值。事务ID、用于事务和MVCC的回滚指针以及所有的剩余列。如果主键是一个列前缀索引，InnoDB也会包含完整的主键列和剩下的其他列。
还有一点和MyISAM不同的是，InnoDB的二级索引和聚簇索引很不相同。InnoDB的二级索引的叶子节点中存储的不是“行指针”，而是主键值，并以此作为指向行的“指针”。这样的策略减少了当出现行移动或者数据页分裂时二级索引的维护工作。使用主键值当作指针会让二级索引占用更多的空间，换来的好处是，InnoDB在移动时无需更新二级索引中的这个“指针”。
我们在来看一下 col2索引 。
每一个叶子节点包含了索引列（这里是col2），紧接着是主键值（col1），上图我们省略了非叶子节点这样的细节。InnoDB非叶子节点包含了索引列和一个指向下一级节点的指针。
最后，以一张图表示InnoDB和MyISAM保存数据和索引的区别。
前面讲过，最好使用AUTO_INCREMENT自增列来聚集数据，避免随机的、不连续的、值分布范围大的列做聚簇索引，特别是对于I/O密集型的应用。例如，从性能角度考虑，使用UUID来作为聚簇索引则会很糟糕：他使得聚簇索引的插入变得完全随机，这是最坏的情况，使得数据没有任何聚集特性。
为了演示这一点，我们做两个基准测试：
1、使用证书ID插入userinfo表，和uuid作为主键的userinfo_uuid表
userinfo_uuid表跟userinfo表除了主键给为UUID，其他字段都一样
测试这两个表的设计，首先在一个有足够内存容纳索引的服务器上向这两个表各插入100万条记录。然后向两个表继续插入300万数据，使索引的大小超过服务器的内存容量。测试结果如下：
向UUID主键插入行不仅花费的时间更长，而且索引占用的空间也更大。这一方面是由于主键字段更长，另一方面毫无疑问是由于页分裂和碎片导致的。
为了明白为什么会这样，来看看往第一个表中插入数据时，索引发生了什么变化。
自整型主键插入
因为主键是顺序的，所以InnoDB把每一条记录都存在上一条记录的后面。当达到页的最大容量后，下一条记录就会写入到新的页中。一旦数据按照这种顺序的方式加载，主键页就会近似于被顺序的记录填满，这也正是所期望的结果。
UUID插入
因为新行的主键值不一定比之前插入的大，所以InnoDB无法简单的总是把新行插入到索引的最后，而是需要为新的行寻找合适的位置，通常是已有数据的中间位置，并且分配空间。这会正价很多的额外工作，并导致数据分布不够优化。
缺点：
把这些随机值载入到聚簇索引后，也许需要做一次OPTIMIZE TABLE来重建表并优化页的填充。
结论 ：使用InnoDB时应尽可能地按主键顺序插入数据，并且尽可能地单调增加聚簇键的值来插入新行。
首先说说索引的 优点 ：最大的好处无疑就是提高查询效率。有的索引还能保证数据的唯一性，比如唯一索引。
而它的 坏处 也很明显：索引也是文件，我们在创建索引时，也会创建额外的文件，所以会占用一些硬盘空间。其次，索引也需要维护，我们在增加删除数据的时候，索引也需要去变化维护。当一个表的索引多了以后，资源消耗是很大的，所以必须结合实际业务再去确定给哪些列加索引。
再说说索引的基本结构。一说到这里肯定会脱口而出：B+树！了解B+树前先要了解二叉查找树和二叉平衡树。 二叉查找树 ：左节点比父节点小，右节点比父节点大，所以二叉查找树的中序遍历就是树的各个节点从小到大的排序。 二叉平衡树 ：左右子树高度差不能大于1。B+树就是结合了它们的特点，当然，不一定是二叉树。
为什么要有二叉查找树的特点？？ 因为查找效率快，二分查找在这种结构下，查找效率是很快的。 那为什么要有平衡树的特点呢？ 试想，如果不维护一颗树的平衡性，当插入一些数据后，树的形态有可能变得很极端，比如左子树一个数据没有，而全在右子树上，这种情况下，二分查找和遍历有什么区别呢？而就是因为这些特点需要去维护，所以就有了上面提到的缺点，当索引很多后，反而增加了系统的负担。
接着说B+树。 它的结构如下 ：
可以发现，叶子节点其实是一个 双向循环链表 ，这种结构的好处就是，在范围查询的时候，我只用找到一个数据，就可以直接返回剩余的数据了。比如找小于30的，只用找到30，其余的直接通过叶子节点间的指针就可以找到。再说说其他特点： 数据只存在于叶子节点 。当叶子节点满了，如果再添加数据，就会拆分叶子节点，父节点就多了个子节点。如果父节点的位置也满了，就会扩充高度，就是拆分父节点，如25 50 75拆分成：25为左子树，75为右子树，50变成新的头节点，此时B+树的高度变成了3。它们的扩充的规律如下表，Leaf Page是叶子节点，index Page是非叶子节点。
再说说B树 ，B树相比较B+树，它所有节点都存放数据，所以在查找数据时，B树有可能没到达叶子节点就结束了。再者，B树的叶子节点间不存在指针。
最后说说Hash索引 ，相较于B+树，Hash索引最大的优点就是查找数据快。但是Hash索引最大的问题就是不支持范围查询。试想，如果查询小于30的数据，hash函数是根据数据的值找到其对应的位置，谁又知道小于30的有哪几个数据。而B+树正好相反，范围查询是它的强项。
附录： Hash到底是啥？？ 哈希中文名散列，哈希只是它的音译。 为啥都说Hash快？？ 首先有一块哈希表（散列表），它的数据结构是个数组，一个任意长度的数据通过hash函数都可以变成一个固定长度的数据，叫hash值。然后通过hash值确定在数组中的位置，相同数据的hash值是相同的，所以我们存储一个数据以后，只需O(1)的时间复杂度就可以找到数据。 那hash函数又是啥？？ 算术运算或位运算，很多应用里都有hash函数，但实际运算过程大不一样。这是Java里String的hashCode方法：
publicint hashCode() {
}
还有一个问题，hash函数计算出来的hash值有可能存在碰撞，即两个不同的数据可能存在相同的hash值，在MySQL或其他的应用中，如Java的HashMap等，如果存在碰撞就会以当前数组位置为头节点，转变成一个链表。
说到这里也清楚了为啥Java中引用类型要同时重写hashCode和equals了。两个对象，实例就算一模一样，它们的hash值也不相等， 为啥不相等？？ 默认的Object的hashCode方法会根据对象来计算hash值的，实例相同，但它们还是两个不同的对象啊，所以我们重写hashCode时，最简单的方法就是调用Object的hashCode方法，然后传入该引用类型的属性，让hashCode方法只根据这几个属性来计算，那么实例相同的话，它们的hash值也会相等。等hashCode比较完后，如果相等再比较实例内容，也就是equals，确保不是hash碰撞。
索引的分类
如果我们指定了一个主键，那么这个主键就是主键索引。如果我们没有指定，Mysql就会自动找一个非空的唯一索引当主键。如果没有这种字段，Mysql就会创建一个大小为6字节的自增主键。如果有多个非空的唯一索引，那么就让第一个定义为唯一索引的字段当主键，注意，是第一个定义，而不是建表时出现在前面的。
对于辅助索引来说，它们的B+树结构稍微有点特殊，它们的叶子节点存储的是主键，而不是整个数据。所以在大部分情况下，使用辅助索引查找数据，需要二次查找。但并不是所有情况都需要二次查找。比如查找的数据正好就是当前索引字段的值，那么直接返回就行。这里提一句，B+树的key就是对应索引字段的内容。
而辅助索引又有一些分类：唯一索引：不能出现重复的值，也算一种约束。普通索引：可以重复、可以为空，一般就是查询时用到。前缀索引：只适用于字符串类型数据，对字符串前几个字符创建索引。全文索引：作用是检测大文本数据中某个关键字，这也是搜索引擎的一种技术。
注意，聚集索引、非聚集索引和前面几个索引的分类并不是一个层面上的。上面的几个分类是从索引的作用来分析的。聚集、非聚集索引是从索引文件上区分的。主键索引就属于聚集索引，即索引和数据存放在一起，叶子节点存放的就是数据。数据表的.idb文件就是存放该表的索引和数据。
辅助索引属于非聚集索引，说到这也就明白了。索引和数据不存放在一起的就是非聚集索引。在MYISAM引擎中，数据表的.MYI文件包含了表的索引， 该表的 叶子节点存储索引和索引对应数据的指针，指向.MYD文件的数据。
索引的几点使用经验
经常被查询的字段；经常作为条件查询的字段；经常用于外键连接或普通的连表查询时进行相等比较字段；不为null的字段；如果是多条件查询，最好创建联合索引，因为联合索引只有一个索引文件。
经常被更新的字段、不经常被查询的字段、存在相同功能的字段
MySQL的Innodb存储引擎的索引分为聚集索引和非聚集索引两大类
特点：B+树叶子节点存储行数据
一个表中，必须有一个聚集索引，只能有一个聚集索引，Innodb通常把一个表的主键索引作为聚集索引，如果没有主键InnoDB会选择一个唯一索引代替。如果没有这样的索引，InnoDB会隐式的定义一个主键来作为聚集索引，这个字段为6个字节，类型为长整形。
利用主键索引查找行数据是最快的，建议使用自增主键原因是利于索引树的构建（主键自增写入时新插入的数据不会影响到原有页，插入效率高；但是如果主键是无序的或者随机的，那每次的插入可能会导致原有页频繁的分裂，影响插入效率）
特点：B+树叶子节点存储主键ID
一个表中可以有多个非聚集索引，每个非聚集索引即是一棵B+树
通过非聚集索引查找数据时，需要先在非聚集索引上找到主键ID，再从聚集索引获取行数据，这个过程就称之为回表
B树索引中的B树实际上是B+树，至于为什么使用B+树而不使用B树或者红黑树的原因在另外的文章中有提及。
特点：
特点：类似JDK中的HashMap，但无法支持范围查询
特点：使用的算法仍然是B树索引，不同的就是索引列的值必须唯一
对于普通索引来说，查找到满足条件的第一个记录后，需要查找下一个记录，直到碰到第一个不满足条件的记录。
对于唯一索引来说，由于索引定义了唯一性，查找到第一个满足条件的记录后，就会停止继续检索，提升索引性能
另外插入行时会构建该唯一索引，假如索引值重复将插入失败，适合业务上做唯一性检验
通过建立倒排索引，可以极大的提升检索效率,解决判断字段是否包含的问题，但是业务上一般都不采用这种索引，而是使用ES处理全文搜索需求
仅对某个特定字段建立的索引，如(biz_id)
对多个字段建立的索引，如(biz_id,type)
