首先，MySql 支持多种存储引擎，最为常用的是 innodb，MyIsam 也需要了解，其他的存储引擎包括 Archive 等等都要又个印象。
各种存储引擎对于索引的支持也不相同，总结下来，MySql 的索引主要由三种类型，B 树索引，Hash 索引，全文索引。我们只关注 BTree 索引，因为这是我们平常使用 MySql 时主要的打交道的方式。
MySql 中的 B 树索引的物理文件大多是以 Balance Tree 的结构来存储的，也就是所有的实际的数据都存放于 Tree 的叶子节点中，到任何一个叶子节点的最短路径长度都是完全相同的。各个数据库或者存储引擎都会对 B 树索引的存储结构稍加改造，比如 innodb 的 B 树索引实际使用的 B+ 树，也就是在 B 树的结构上做了很小的改动。除了在每一个叶子节点上存放索引的相关信息之外，还存储了只想该叶子节点的后一个叶子节点的指针信息（增加了顺序访问），这也是为了加快检索多个相邻的叶子节点的效率考虑。
什么是索引定义：索引是为了帮助 MySql 高效获得数据的数据结构。
目的：索引的目的当然是为了快速找到对应的数据了。就比如我们查字典，一定是按照首个字母或者拼音去找而不是翻遍整个字典。
索引原理
索引的原理就是通过不断的缩小范围从而筛选出想要的结果从而避免对整个文件的查找。同时把随机的事件变为顺序的事件，也就是我们总是通过同一种查找方式来锁定数据。
数据库的索引更为复杂，因为不仅面临着等值查询，还有范围查询（<，>，between），模糊查询（like），并集查询（or），多值匹配（in）等等。我们回想字典的例子，能不能把数据分成段，然后分段查询那？比如将 1000 条数据中的 1 到 100 分为第一段，101 到 200 分为第二段...... 这样查第 105 条数据只需要查第一段就可以了。如果是 10000 条那，怎么分段？稍微有算法基础的同学可能会想到搜索树，平均复杂度是 logN，性能不错，但是有时为了提高性能，会把部分数据读入内存中来计算，我们知道访问磁盘的成本大概是访问内存的十万倍左右，所以简单的搜索树并不能满足复杂的应用场景。
B+ 树索引结构
上面我们说过简单的搜索树并不能满足数据库的使用场景。我们需要索引做什么那？那就是每次查找数据时能把磁盘 IO 次数控制在一个很小的数量级，最好是常数数量级。因此，一个高度可控的多路搜索树 b+ 树产生了。
每个磁盘块中包含几个数据项（深蓝色）和指针（黄色），磁盘块1 包含数据项 17 和 35，包含指针 P1，P2，P3，P1 表示小于 17 的磁盘块，P2 表示在 17 和 35 之间的磁盘块，P3 表示大于 35 的磁盘块。
真实的数据存在于叶子节点即 3，5，9，10，13，15，28，29，36，60，75，79，90，99。非叶子节点不存储真实数据，只存储搜索方向的数据项。
B+ 树的查找过程
如果我们想要查找 29，那么首先会把磁盘1 家在到内存，此时发生一次 IO，内存中用二分查找确定 29 在 17 和 35 之间，锁定磁盘块 1 的 P2 指针，加载磁盘块 3 到内存，发生第二次 IO。然后锁定磁盘块 8，发生第三次 IO，找到了 29。结束查询，总共发生三次 IO。3 层的 B + 树可以表示上百万的数据，所以上百万的数据的查询只需要三次 IO 就可以完成了，如果没有索引，每个数据项都要发生一次 IO，那么就需要百万次的 IO，成本非常高。
MySql 的索引实现MySql 中，索引是存储引擎级别的概念，不同的存储引擎对索引的实现方式是不同的。我们主要针对 MyISAM 和 InnoDB 两个存储引擎的索引实现来讨论。
MyISAM 索引实现
MyISAM 引擎使用的是 B+ 树作为索引结构，叶子节点的 data 域存放的是数据记录的地址。
假设我们以 Col1 为主键，那么上图就是 MyISAM 表的主键索引。MyISAM 存储引擎中，主键索引和辅助索引在结构上是没有任何区别的，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复。我们来看建立在 Col2 上的辅助索引。