Mysql索引的基本原理
索引的目的就是提高查询效率，其基本原理就是通过不断的缩小数据的范围来筛选出最终想要的结果。但是对于数据库这样一种数据存储结构非常复杂，同时查询方式又相当灵活的系统来说这样看似简单的问题也会变得异常复杂。以前数据结构课程学过很多优化查找性能的数据结构，比如搜索树，其查找时间复杂度是lgN，但是搜索树的时间复杂度是所有数据均在内存中，这样查找操作的耗时主要在cpu，所以才关注它的时间复杂度。但是数据库中的数据都存放在磁盘上，而一次磁盘的IO操作相当于40万次cpu操作，也就是说数据库的性能瓶颈在IO上面，所以除了优化查询的时间复杂度以外很重要的一点是控制IO操作的次数。由于IO操作相当昂贵，所以操作系统也作了优化，即根据局部性原理，每次IO操作都会加载磁盘个上这块数据所在的整个页，至于具体一页有多大的数据，取决于特定的操作系统，一般是4K到8K。也就是说我们多次读取一页的数据实际上才发生了一次IO操作。
有一种数据结构就是考虑了上述种种需求，利用了种种原理设计出来的，就是mysql的索引所使用的数据结构: B+树。
浅蓝色的块就是一个磁盘快，其中包含数据项和指针，如磁盘块1中包含数据项17和35,和指针 P1,P2,P3, P1指向所有小于17的数据所在的磁盘块，P2指向17和35之间的数据所在的磁盘快，P3指向大于35的磁盘块。真实的数据只存储在叶子节点中，非叶子节点只存储指引搜索方向的数据项和指针，不存储真实数据。如果要查询90，那么首先将磁盘快1加载到内存中，根据磁盘块1的数据项和指针确定90应该在磁盘块4中查找，于是从把磁盘快4加在到内存中，再次将搜索范围缩小至磁盘快11，此时返现磁盘快11已经是叶子节点，因此对磁盘块11中的数据做二分查找，最终返回查找结果，总计发生三次IO。实际上数据库实现时会把靠近树根的几层节点常驻内存，不需要发生IO操作，之后的三层B+树可以表示上百万的数据，如果上百万的数据查询只需要三次IO操作，性能提高将是巨大的。
从这个图可以看出B+树的搜索性能取决于树的高度，而在数据量一定，磁盘块个数一定的情况下树的高度则取决于每个磁盘块中存储的数据个数，又在磁盘块大小一定的情况下，每个磁盘块中存储的数据个数则取决于数据的大小。由于B+树中非叶子节点不存储真实数据，只存储指明真实数据方向的数据项和指针，指针大小一定，所以数据项越小，一个磁盘快中存储的数据项就越多，而这个数据项的大小则就是索引类型的大小，也就是说优化查询的第一步就是减小索引的长度。
B+树的数据项是复合数据结构，这也就是组合索引实现的原理，对于复合数据B+树将会先按照第一列的数据划分不同的数据块，指示方向，第一列相同时再依次按照剩下的列划分数据块，指示方向。比如一个复合数据项(name,age,gender)，查询(bob,22,F)的时候，B+树会优先比较name来确定下一步的搜索方向。如果name相同则依次比较age和gender，那么如果要查询(22,F)这样的数据会发生什么呢？我们的辛辛苦苦建立的这些数据项和指针就完全起不到任何作用了，因为只有name相同的情况下才会按照age来划分数据块，并且指示搜索方向。现在name都不知道，我们就更不知道age,gender的方向了。
从这个数据结构也可以看出，只有当查询具体值的时候指示数据范围的数据项和数据位置的指针才能被高效利用，如果按照范围来查询，可能会垮多个块，当初利用B+树来减少IO次数的思想到此也就不再适用了，反而可能会增加复杂度。因此对于范围查询，mysql只会根据索引进行一次范围查询然后不再利用剩下的索引。
关于优化
在弄清楚了mysql索引的原理之后，优化也就有根有据了。主要有以下几点原则:
-
最左匹配原则， 对于组合索引,
mysql会从左到右使用索引进行匹配，直至遇到范围查询(<,>,between,like)就停止索引匹配，在匹配到的数据中进行全扫描。例如对于复合索引(a,b,c,d)查询a=1 and b=2 and c >3 and d=4，其中d是用不到索引的,要想这个查询使用到索引，可以将索引调整为(a,b,d,c)。 - 索引字段尽量小，这样可以减小搜索树的高度，从而提高查询效率。
- 索引字段的区分度尽量大，如果索引字段重复性相当高，索引的存在甚至可能会降低查询效率。
- 索引不能参与计算，可以看出叶子节点的数据项和指针指示的都是最终数据本身的方向，如果参与计算之后计算的结果不一定和最终数据本身方向相同，因此不会遇到索引。
-
尽量扩展索引，而不是新增索引，一是因为新增索引存储成本更高，而且
mysql对每个查询只会用到一个索引(uinion查询除外)，因此合适的组合索引查询效率比多个单值索引效率要高。 -
对于
join操作，永远小结果集驱动大结果集 ,第一次锁定小的结果集本身查询效率可能就高一点，而且这个结果集在后面的过滤中区分度页更高，同时小的结果集内存占用也更小。
