1 索引简介
1.1 索引定义
索引是帮助MySQL高效获取数据的数据结构。更通俗的说，数据库索引好比是一本书前面的目录，能加快数据库的查询速度。
一般来说索引本身也很大，不可能全部存储在内存中，因此索引往往是存储在磁盘上的文件中的（可能存储在单独的索引文件中，也可能和数据一起存储在数据文件中）。
索引的优点：
可以提高数据检索的效率，降低数据库的IO成本，类似于书的目录；
通过索引列对数据进行排序，降低数据排序的成本，降低了CPU的消耗。
索引的缺点：
索引会占据磁盘空间；
索引虽然会提高查询效率，但是会降低更新表的效率。比如每次对表进行增删改操作，MySQL不仅要保存数据，还有保存或者更新对应的索引文件。
1.2 索引的数据结构
1.2.1 Hash表
Hash表，在Java中的HashMap，TreeMap就是Hash表结构，以键值对的方式存储数据。我们使用Hash表存储表数据Key可以存储索引列，Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高，时间复杂度为O(1)；但是不支持范围快速查找，范围查找时还是只能通过扫描全表方式。
显然这种并不适合作为经常需要查找和范围查找的数据库索引使用。
1.2.2 二叉查找树
每个节点最多有2个分叉，左子树和右子树数据顺序左小右大。
这个特点就是为了保证每次查找都可以这折半而减少IO次数，但是二叉树就很考验第一个根节点的取值，因为很容易在这个特点下出现我们并发想发生的情况“树不分叉了”，这就很难受很不稳定。
显然会出现上图这种不稳定的情况，我们在选择设计上必须要避免。
1.2.3 平衡二叉树
平衡二叉树是采用二分法思维，平衡二叉查找树除了具备二叉树的特点，最主要的特征是树的左右两个子树的层级最多相差1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡，不会出现左子树很高、右子树很矮的情况。
使用平衡二叉查找树查询的性能接近于二分查找法，时间复杂度是 O(log2n)。查询id=6，只需要两次IO。
就这个特点来看，可能各位会觉得这就很好，可以达到二叉树的理想的情况了。然而依然存在一些问题：
时间复杂度和树高相关。树有多高就需要检索多少次，每个节点的读取，都对应一次磁盘IO操作。树的高度就等于每次查询数据时磁盘IO操作的次数。磁盘每次寻道时间为10ms，在表数据量大时，查询性能就会很差。（1百万的数据量，log2n约等于20次磁盘IO，时间20*10=0.2s）
平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高。
1.2.4 B树
MySQL的数据是存储在磁盘文件中的，查询处理数据时，需要先把磁盘中的数据加载到内存中，磁盘IO 操作非常耗时，所以我们优化的重点就是尽量减少磁盘 IO 操作。访问二叉树的每个节点就会发生一次IO，如果想要减少磁盘IO操作，就需要尽量降低树的高度。那如何降低树的高度呢？
假如key为bigint=8字节，每个节点有两个指针，每个指针为4个字节，一个节点占用的空间16个字节（8+42=16）。
因为在MySQL的InnoDB存储引擎一次IO会读取的一页（默认一页16K）的数据量，而二叉树一次IO有效数据量只有16字节，空间利用率极低。为了最大化利用一次IO空间，一个简单的想法是在每个节点存储多个元素，在每个节点尽可能多的存储数据。每个节点可以存储1000个索引（16k/16=1000），这样就将二叉树改造成了多叉树，通过增加树的叉树，将树从高瘦变为矮胖。构建1百万条数据，树的高度只需要2层就可以（10001000=1百万），也就是说只需要2次磁盘IO就可以查询到数据。磁盘IO次数变少了，查询数据的效率也就提高了。
这种数据结构我们称为B树，B树是一种多叉平衡查找树，如下图主要特点：
B树的节点中存储着多个元素，每个内节点有多个分叉。
节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点都储存数据。
父节点当中的元素不会出现在子节点中。
所有的叶子结点都位于同一层，叶节点具有相同的深度，叶节点之间没有指针连接。
假如我们查询值等于10的数据。查询路径磁盘块1->磁盘块2->磁盘块6。
第一次磁盘IO：将磁盘块1加载到内存中，在内存中从头遍历比较，10<15，走15的左路节点P1，到磁盘寻址磁盘块2。
第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头遍历比较，7<10，走7的右路节点P2，到磁盘中寻址定位到磁盘块6。
第三次磁盘IO：将磁盘块6加载到内存中，在内存中从头遍历比较，8<10，10=10，找到10，取出data。如果data存储的行记录，取出data，查询结束。如果存储的是磁盘地址，还需要根据磁盘地址到磁盘中取出数据，查询终止。
相比二叉平衡查找树，在整个查找过程中，虽然数据的比较次数并没有明显减少，但是磁盘IO次数会大大减少。同时，由于我们的比较是在内存中进行的，比较的耗时可以忽略不计。B树的高度一般2至3层就能满足大部分的应用场景，所以使用B树构建索引可以很好的提升查询的效率。
B树虽然看着很理想，但它依然存在可以优化的地方：
B树不支持范围查询的快速查找，你想想这么一个情况如果我们想要查找10和35之间的数据，查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高；
如果data存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。
1.2.5 B+树
B+树，作为B树的升级版，在B树基础上，MySQL在B树的基础上继续改造，使用B+树构建索引。B+树和B树最主要的区别在于非叶子节点是否存储数据的问题。
B树：非叶子节点和叶子节点都会存储数据。
B+树：只有叶子节点才会存储数据，非叶子节点至存储键值。叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表。
B+树的最底层叶子节点包含了所有的索引项。从下图可以看到，B+树在查找数据的时候，由于数据都存放在最底层的叶子节点上，所以每次查找都需要检索到叶子节点才能查询到数据。所以在需要查询数据的情况下每次的磁盘的IO跟树高有直接的关系，但是从另一方面来说，由于数据都被放到了叶子节点，所以放索引的磁盘块锁存放的索引数量是会跟这增加的，所以相对于B树来说，B+树的树高理论上情况下是比B树要矮的。B+树一定是检索到叶子节点才能取到数据，而B树在索引中数据满足了当前查询语句所需要的全部数据，此时只需要找到索引即可立刻返回，不需要检索到最底层的叶子节点。
等值查询：
假如我们查询值等于9的数据。查询路径磁盘块1->磁盘块2->磁盘块6。
第一次磁盘IO：将磁盘块1加载到内存中，在内存中从头遍历比较，9<15，走15的左节点P1，到磁盘块2。
第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头遍历比较，7<9<12，走7的右节点P2，到磁盘中寻址定位到磁盘块6。
第三次磁盘IO：将磁盘块6加载到内存中，在内存中从头遍历比较，在第三个索引中找到9，取出data，如果data存储的行记录，取出data，查询结束。如果存储的是磁盘地址，还需要根据磁盘地址到磁盘中取出数据，查询终止。（这里需要区分的是在InnoDB中Data存储的为行数据，而MyIsam中存储的是磁盘地址。）
范围查询：
假如我们想要查找9和26之间的数据。查找路径是磁盘块1->磁盘块2->磁盘块6->磁盘块7。
首先查找值等于9的数据，将值等于9的数据缓存到结果集。这一步和前面等值查询流程一样，发生了三次磁盘IO。
查找到15之后，底层的叶子节点是一个有序列表，我们从磁盘块6，键值9开始向后遍历筛选所有符合筛选条件的数据。
第四次磁盘IO：根据磁盘6后继指针到磁盘中寻址定位到磁盘块7，将磁盘7加载到内存中，在内存中从头遍历比较，9<25<26，9<26<=26，将data缓存到结果集。
主键具备唯一性（后面不会有<=26的数据），不需再向后查找，查询终止。将结果集返回给用户。
可以看到B+树可以保证等值和范围查询的快速查找，MySQL的索引就采用了B+树的数据结构。
2 MySQL的索引实现
2.1 MyISAM索引
2.1.1 主键索引
MyISAM的数据文件和索引文件是分开存储的，索引存储在.MYI的索引文件中，数据文件存储在.MYD的数据文件中。MyISAM使用B+树构建索引树时，叶子节点中存储的键值为索引列的值，数据为索引所在行的磁盘地址。
根据主键等值查询数据：select * from user where id = 28;
先在主键树中从根节点开始检索，将根节点加载到内存，比较28<75，走75的左节点P1。（1次磁盘IO）
将左子树节点加载到内存中，比较16<28<47，走47节点的左路P2。（1次磁盘IO）
检索到叶节点，将节点加载到内存中遍历，比较16<28，18<28，28=28。查找到值等于28的索引项。（1次磁盘IO）
从索引项中获取磁盘地址，然后到数据文件中获取对应整行记录（1次磁盘IO），将记录返给客户端。
磁盘IO次数：3次索引检索+记录数据检索。
根据主键范围查询数据：select * from user where id between 28 and 47;
先在主键树中从根节点开始检索，将根节点加载到内存，比较28<75，走75的左路P1。（1次磁盘IO）
将左子树节点加载到内存中，比较16<28<47，走47左路P2。（1次磁盘IO）
检索到叶节点，将节点加载到内存中遍历比较16<28，18<28，28=28<47。查找到值等于28的索引项。
根据磁盘地址从数据文件中获取行记录缓存到结果集中。（1次磁盘IO）
我们的查询语句时范围查找，需要向后遍历底层叶子链表，直至到达最后一个不满足筛选条件。向后遍历底层叶子链表，将下一个节点加载到内存中，遍历比较，28<47=47，根据磁盘地址从数据文件中获取行记录缓存到结果集中。（1次磁盘IO）
最后得到两条符合筛选条件，将查询结果集返给客户端。
磁盘IO次数：4次索引检索+记录数据检索。
2.1.2 辅助索引
在MyISAM中,辅助索引和主键索引的结构是一样的，没有任何区别，叶子节点的数据存储的都是行记录的磁盘地址。只是主键索引的键值是唯一的，而辅助索引的键值可以重复。
查询数据时，由于辅助索引的键值不唯一，可能存在多个拥有相同的记录，所以即使是等值查询，也需要按照范围查询的方式在辅助索引树中检索数据。
2.2 InnoDB索引
2.2.1 主键索引（聚簇索引）
每个InnoDB表都有一个聚簇索引 ，聚簇索引使用B+树构建，叶子节点存储的数据是整行记录。一般情况下，聚簇索引等同于主键索引，当一个表没有创建主键索引时，InnoDB会自动创建一个ROWID字段来构建聚簇索引。InnoDB创建索引的具体规则如下：
在表上定义主键PRIMARY KEY，InnoDB将主键索引用作聚簇索引。
如果表没有定义主键，InnoDB会选择第一个不为NULL的唯一索引列用作聚簇索引。
如果以上两个都没有，InnoDB 会使用一个6 字节长整型的隐式字段 ROWID字段构建聚簇索引。该ROWID字段会在插入新行时自动递增。
除聚簇索引之外的所有索引都称为辅助索引。在中InnoDB，辅助索引中的叶子节点存储的数据是该行的主键值都。 在检索时，InnoDB使用此主键值在聚簇索引中搜索行记录。
InnoDB的数据和索引存储在一个.ibd的文件中。InnoDB的数据组织方式是聚簇索引。
主键索引的叶子节点会存储数据行，辅助索引只会存储主键值。
根据主键等值查询数据：select * from user_innodb where id = 28;
先在主键树中从根节点开始检索，将根节点加载到内存，比较28<75，走75的左路P1。（1次磁盘IO）
将左子树节点加载到内存中，比较16<28<47，走47节点的左路P2。（1次磁盘IO）
检索到叶节点，将节点加载到内存中遍历，比较16<28，18<28，28=28。查找到值等于28的索引项，直接可以获取整行数据。将该记录返回给客户端。（1次磁盘IO）
磁盘IO数量：3次。
根据主键范围查询数据：与等值查询前三部完全一致，会多一步步骤4。
需要向后遍历底层叶子链表，直至到达最后一个不满足筛选条件。向后遍历底层叶子链表，将下一个节点加载到内存中，遍历比较，28<47=47，然后将47对应的整行数据与28对应的整行数据一起返回。（1次磁盘IO）
磁盘IO数量：4次。
2.2.2 辅助索引
除聚簇索引之外的所有索引都称为辅助索引，InnoDB的辅助索引只会存储主键值而非磁盘地址。索引结果如下图。
底层叶子节点的按照（age，id）的顺序排序，先按照age列从小到大排序，age列相同时按照id列从小到大排序。
使用辅助索引需要检索两遍索引：首先检索辅助索引获得主键，然后使用主键到主索引中检索获得记录。
画图分析等值查询的情况：select * from t_user_innodb where age=19;
根据在辅助索引树中获取的主键id，到主键索引树检索数据的过程称为回表查询。
磁盘IO数：辅助索引3次+获取记录回表3次。
3 总结
了解了MySQL下两种索引的数据结构后，可以有以下结论：
InnoDB是聚簇索引，使用B+树作为索引结构，数据文件是和（主键）索引绑在一起的（表数据文件本身就是按B+Tree组织的一个索引结构），必须要有主键，通过主键索引效率很高。但是辅助索引需要两次查询，先查询到主键，然后再通过主键查询到数据。因此，主键不应该过大，因为主键太大，其他索引也都会很大。
MyISAM是非聚集索引，也是使用B+树作为索引结构，索引和数据文件是分离的，索引保存的是数据文件的指针。主键索引和辅助索引是独立的。
InnoDB推荐使用自增ID作为主键,自增ID可以保证每次插入时B+索引是从右边扩展的，可以避免B+树和频繁合并和分裂（对比使用UUID）。如果使用字符串主键和随机主键，会使得数据随机插入，效率比较差。