我们知道，mysql是存储在磁盘上的，每次从mysql查询数据都是进行一次或者多次IO操作。当我们不对mysql的表进行任何优化而执行查找命令select * from tablename where name='xxx'; mysql将从上至下的逐行从磁盘读取数据(顺序查找)，直到找到name=xxx的数据。每次从磁盘读取数据都是一次IO操作，过多的IO操作对cpu来说都是一种资源浪费。当表中数据很多时，就造成mysql慢查询。
往往我们优化mysql性能，最先想到的就是增加索引。那么为什么索引能使mysql性能得到一个或者多个数量级的提升呢？本文我们从原理上来简单概括一下mysql的索引。
1.索引是什么
索引是帮助mysql快速获取数据的一种排好序的数据结构。
2.索引存储了什么
为了省事，假设mysql索引是二叉树的结构来举例说明。当然真实的情况下数据库不会采用二叉树的数据结构而往往是B+树或者红黑树。
为什么不使用二叉树？
当我们将数据递增的字段(如主键)设为索引，由于二叉树的特性，形成的结构将是没有左节点只有右节点，可以理解为二叉树退化成单链表的结构，对我们进行数据查找并不会起到优化的作用。与顺序查找没有任何区别。
如上图所示，将左侧表的Col2字段建立索引，根据二叉树的特点(左叶子小于父节点，右叶子大于父节点)得到索引的数据结构。基于该特性从而大大减少了查询的性能消耗。 索引以key：value的形式存储，key为字段的值，value保存了该行保存在磁盘中的内存地址。
3.索引使用几种数据结构下的对比
常用的几种数据结构：二叉树、红黑树、hash表、B树
3.1）二叉树
上述内容中已经描述了使用二叉树下建立索引的原理和弊端，这里不再阐述。
3.2）红黑树
顺便简单介绍一下红黑树
红黑树也是一种二叉树，但是在二叉树的基础上具有平衡能力。以至于不会出现叶子节点一边增长的情况。
以上述递增数据举例，简单说明红黑树：
当值只有1,2时，插入值3，原本3将在2的右节点，但是红黑树会将原二叉树进行平衡，得到树结构如下所示
以上介绍了红黑树，那么为什么不使用这种方式作为索引的数据结构呢？ 红黑树还是存在缺陷，当表内数据量很大时，红黑树的结构深度依然很多。进行查找还是需要很多次IO操作，造成资源浪费。
3.3）B树
那么面对一个有几百万甚至几千万数据的表，我们依然只希望索引的树结构深度只有3-4层，这样尽可能的减少IO操作，有没有可能呢？ 我们可以使用B树达到这种期望。 B树，又称为多路平衡查找树。B树的思想是：我们知道二叉树每个节点只有一个每次只开辟一个很小的内存空间用来存储，为了减少数的深度，我们可以将每个节点的内存空间增加，从而将单一的节点存储为一串节点。这样能大大的减少数的深度，实现很小的深度容纳千万级的数据内容。
简单介绍一下B树
a. B树需要指定阶数m，即容纳节点的数量。每个节点最大容纳节点数为m-1。
b. B树和二叉树一样，左节点小于父节点，右节点大于父节点，每个节点中的关键字从左至右递增。
c. 所有叶子节点都处于同一层，即跟节点到每个叶子节点深度都一样。
上图为一个B树。节点前后(蓝色位置)都存了子节点的地址。而节点自身key：value存储关键字和data。 这样看起来是大大提高了索引的查询效率，那么为什么mysql索引不采用B树的结构呢？我们来看看下面的场景。 当我们要查询一个范围结果时，比如查询9<=x<=30的结果。按照上图的结构，我们只能一个一个的进行查询，这当然不能满足我们的期望。
3.4）B+树
有没有什么办法能让我们对查询范围结果时，只需要针对边界范围进行一次查找就能快速得到期望结果呢？为了解决这个问题，引入了B+树的结构。B+树结构如下：
简单介绍一下B+树。
B+树可以说是B树的一种改良结构，B+树与B树有许多共同的特点。如上结构图中所示，对比B树，B+树具备的新特点：
- 跟节点和所有子节点只包含关键字(key)而没有data，只有叶子节点存放数据。
- 叶子节点包含所有的数据，并且从左至右递增。
- 叶子节点之间有双向指针，两两叶子节点之间形成了一个双向链表，指向下一个叶子节点或者上一个叶子节点在磁盘中存储的地址。(这点很重要，是实现高效范围查找的核心。)
总结一下一上的介绍，B+树最大的特点：
- 叶子节点包含所有key
- 只有叶子节点包含数据，跟节点和子节点只有key，仅仅是索引而没有数据关联。
- 叶子节点从左至右key递增，并且叶子节点之间有双向指针连接，形成双向链表。
- 左节点小于父节点，右节点大于等于父节点。如上述图中，key=7的节点，左节点为5,6右节点为7,8,9。
基于B+树结构的这些特性，我们不难看出，只要阶数M大小合适，B+树可以满足大量数据时B+树的深度也能保持在一定深度，减少查询时IO的次数，同时基于叶子节点之间的指针和叶子节点之间的顺序性也能通过一次边界查询而得到满足范围的结果，而不用像B树那样进行多次查找的弊端。 故mysql索引采用B+树的结构存储。
3.5）哈希散列
我们或许会想到使用哈希存储索引，基于哈希的特性，无论数据量有多少，我们都只需要一次IO操作便能查找到结果，这样不是更好吗？
mysql中只有memory 引擎才显示的支持哈希索引。 Innodb 支持的哈希索引是自适应的，用户无法进行配置，InnoDB 引擎会根据表的使用情况自动为表生成哈希索引。使用哈希索引的好处在于时间复杂度为 O(1)，因此哈希索引的查询效率要远高于 B树 索引。但是其限制在于：
- 只有精确匹配索引所有列的查询才有效,因为哈希索引是利用索引的所有列的字段值来计算哈希值的。
- 不支持范围查找，只能用户等值比较查询。
- 哈希索引的只包含索引字段的哈希值和指向数据的指针，所以不能使用索引中的值来避免读取行。
- 哈希索引的数据并不是顺序存储的，无法用于排序。
4.总结一下mysql索引查找的流程
为什么mysql查找通过索引的方式能极大的提高查找效率？
通过上述对mysql索引采用的数据结构分析，我们知道是通过增加阶数从而减小树的深度以达到减少IO操作的目的，进而增加cpu操作达到提升效率。
总结一下大致索引查找流程
- 首先mysql会将索引跟节点数据加载到内存中，优先从内存中查找，减少一次IO操作。mysql预设了阶数大小。
- 通过索引查找，跟节点中没有找到，指向的子节点存储位置在磁盘中读取数据，再次进行查找。
- 重复上述过程，直到在叶子节点中找到该索引。
- 若是范围查找，根据找到叶子节点通过链表可直接从磁盘中拿到后续叶子节点的数据，无需进行查找。
- 得到叶子节点绑定的数据后，是可以直接得到结果还是需要再次进行从磁盘中读取数据需要看表的存储引擎是Innodb还是myISAM。
5.对比mysql存储引擎
聊一下常见的数据库表存储引擎Innodb和myISAM的差别。
什么是Innodb和myISAM？
都是mysql数据表的常见的存储引擎(注意是针对mysql数据表而不是数据库)。
其中Innodb是事务型数据库的首选引擎，支持ACID事务，支持行级锁定。InnoDB是为处理巨大数据量时的最大性能设计。
而myISAM是mysql的一种默认存储引擎。它基于更老的ISAM代码，但有很多有用的扩展。
5.1）从数据文件上对比
进入mysql的数据存储路径下，linux默认存储路径：/var/lib/mysql/你的数据库名称
使用myISAM存储引擎的表有3个文件
- xxx.frm：存储表结构内容文件
- xxx.MYI：存储表索引内容文件
- xxx.MYD：存储表数据内容文件
使用Innodb存储引擎的表有2个文件
- xxx.frm：存储表结构内容文件
- xxx.idb：存储表数据内容文件
使用Innodb存储引擎的数据库表数据文件比使用myISAM存储引擎的数据库表数据文件少一个，只有2个。这是因为Innodb使用的是聚集行索引存储形式，故而将索引与表数据整合成为一个文件。而myISAM使用的是非聚集型索引存储形式，索引和表数据是分开存储的。
5.2）从数据结构原理上对比
上面我们引出了聚集型和非聚集型的概念。我们从数据结构上解释一下这两者的区别。 我们已经知道了mysql索引使用的是B+树的数据结构形式，所有叶子节点上关联数据。聚集型和非聚集型的区别就是叶子结点关联的数据的差别。 聚集型：叶子节点上的数据包含了这数据表中这行的所有字段内容。 非聚集型：叶子节点上的数据并不是存储字段的内容，而是存储数据表中这行在磁盘中存储的地址。
Innodb使用的是聚集型，而myISAM使用的是非聚集型。通过上面对聚集型和非聚集型的描述和数据文件上的对比，我们不难理解。当Innodb通过索引进行查询时，当找到索引后便可以立即获取当前行的所有字段内容。而myISAM通过索引进行查找时，只能得到当前索引存储数据在磁盘上的存储地址，需要再进行一步IO读取操作从.MYD文件中读取内容。
myISAM存储引擎数据关联如下，叶子节点中value关联的是该索引行在磁盘中存储的地址。再通过存储地址在磁盘上读取该索引的行数据。myISAM的索引方式也称为“非聚集型索引”。
Innodb存储引擎数据关联如下，叶子节点中value关联的是该索引行的全部字段内容。通过索引查找可以直接得到该数据行的内容。Innodb的索引方式也称为“聚集型索引”。
5.3）从事务上对比
mysql将默认数据表存储引擎由Innodb改为myISAM的主要原因就是因为myISAM不支持事务。
5.4）其他对比
查询行
InnoDB 不保存表的具体行数，执行 select count(*) from table 时需要全表扫描。而MyISAM 用一个变量保存了整个表的行数，执行上述语句时只需要读出该变量即可，速度很快；
锁粒度
InnoDB 最小的锁粒度是行锁，MyISAM 最小的锁粒度是表锁。一个更新语句会锁住整张表，导致其他查询和更新都会被阻塞，因此并发访问受限。这也是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要原因之一；
6.关于索引的建议
6.1）建立索引字段采用有序整型字段
使用整型这点很好理解，整型在排序时更容易排序，而字符串需要一个个字符进行转码比较，消耗性能。另外字符串更加消耗内存空间，使得每个子节点容纳的数量更少，增加树的深度，降低查询性能。
6.2）关于复合索引
对于像主键这样的递增且不重复的字段，建立单个索引就能顺利的查找到目标数据。若是不通过主键但又不能确保唯一字段怎么办？ 针对上述问题，我们可以采用复合索引，即多个索引字段来确保查询数据唯一。 索引当然支持复合索引，我们也建议合理的使用复合索引。在使用复合索引的过程中我们需要注意两点：
- 使用复合索引查询时不能省略第一个索引，否则mysql不会安装索引查找。
- 尽量保持索引的顺序。
首先解释什么是mysql最左前缀原则
假设有上述复合索引结构，分别为：年龄、国家、姓名。当我们通过复合索引查找数据时，mysql会按照复合索引的顺序进行查找。如：优先查找年龄，再查找国家，再查找姓名的逻辑进行。不能跳过前面的索引。
这就是mysql的最左前缀原则。
为什么不能省略前面的索引而直接使用后面的索引？
我们知道B+树的叶子节点是有序的，在复合索引结构中，第二个索引只有在满足第一个索引相同的情况下才是有序的。若没有前面的索引一致，后面的索引便没有顺序性可言。
为什么说尽量保持索引的顺序？
上面我们解释了mysql的最左前缀原则，实际上mysql在进行索引查找时，会对我们的sql进行整理优化。会将我们写的sql根据索引的顺序进行重新排序，mysql的效率资源是非常宝贵的，所以我们在写sql时尽量保持索引的顺序减少mysql的处理。
