索引（在MysQL中也叫键）是存储引擎用于快速找到记录的一种数据结构，索引对于良好的性能十分关键
索引基础
在MySQL中，存储引擎用类似的方法使用索引，其先在索引中找到对应值，然后根据匹配的索引记录找到对应的数据行。MySQL在索引上按值进行查找，然后返回包含所有该值的数据行。
索引可以包含一个列或者多个列的值，如果索引包含多个列，要注意列的顺序，因为索引是满足最左前缀匹配的。
索引的类型
在MySQL中，索引是在存储引擎层实现的而不是服务器层实现的。所有没有统一标准：不同存储引擎的索引的工作方式是不一样的，而且也不是所有的存储引擎都支持所有类型的索引。
B-Tree索引
如果没有特别的说明，在MySQL中说索引，多半是指B-Tree索引。在NDB集群存储引擎里使用了T-Tree结构，它名字是BTREE，而InnoDB则是采用B+树。（事实上很多存储引擎采用的都是B+Tree，这里注意不要和B树搞混了，这里不讨论各种数据结构具体实现和区别，感兴趣自行了解一下，或者等我哪天有空更）
存储引擎以不同的方式使用B-Tree，所以性能也可能不同。例如MyISAM使用前缀压缩技术使得索引更小，而InnoDB则按照原数据格式进行存储。再如MyISAM索引通过数据的物理位置引用被索引的行，而InnoDB则根据主键引用被索引的行。
B-Tree能够快速的访问数据，因为存储引擎不需要全表扫描来获取需要的数据，取而代之的是从索引的根节点开始进行搜索。B-Tree的叶子节点比较特别，它们指向的是被索引的数据，而不是其他节点页。B-Tree对索引列是顺序组织存储的，所以很适合查找范围数据。
可以使用使用B-Tree的情况：全值匹配，最左前缀，列前缀，范围值，精确匹配某一列并范围匹配另一列，只访问索引的查询。
索引失效：使用全表扫描比使用索引快，条件中有or，不满足最左匹配，条件中有like%，where字符串没有加引号，如果使用MEMORY/HEAP表，并且where条件中不使用“=”进行索引列，那么不会用到索引。
哈希索引
哈希索引，基于哈希表实现，只有精确匹配索引所有列查询才有效。对于每一行数据，都会计算一个哈希码，哈希码是一个较小的值，并且不同行计算出来也不同，哈希索引将哈希码存在索引里，同时在哈希表中保存指向每个数据行的指针。
在MySQL中，Memory引擎是显示支持哈希索引的。这也是Memory引擎默认的索引类型，Memory也是支持B-Tree的。有一点需要注意的是，Memory是支持非唯一哈希索引的，这还是比较独特的。（通俗来说，就是如果多个列的哈希值相同，索引会采用链的方式存放多个记录指针到同一个哈希目录，这其实是处理哈希冲突的一种方式，当然处理哈希冲突并不是只有这一种方法，这种方法的好处是快速处理哈希冲突，不好处就是查询时候比较麻烦，尤其是链很长以后，可能要对链进行一定的操作，ps：我不清楚现在的Memory索引是怎么处理的，按照书中的意思，这个链是没有任何优化的，但是如果在Java1.8以后在链长度到8以后就会转红黑树了）当然因为索引只需要存储对应哈希值，索引结构就会十分紧凑，这也让哈希索引查找的速度非常快。当然哈希索引也有它的限制：
- 哈希索引值只包含哈希值和行指针，而不存字段值。
- 哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序。
- 哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。
- 哈希索引只支持等值比较查询，不支持范围查询。
- 通常来说哈希索引都很快，但是哈希冲突很多的话就需要查找列中索引行指针
- 如果哈希冲突很多的话，一些索引维护的代价也很高。
在NDB集群引擎也支持唯一哈希索引，且在NDB集群引擎中作用非常特殊（就这，不在这本书的范围，说实话，看这本书之前，我连NDB都没听过，NDB大体上是一个用于分布式计算的MySQL集群，我分布式知识暂时有些匮乏，惭愧）
InnoDB引擎有一个特殊的功能叫做“自适应哈希索引”。如果InnoDB注意到某些索引值被引用得非常频繁时，就会在内存中基于B-Tree索引之上再创建一个哈希索引。这是一个完全自动，内部的行为，用户无法控制，不过如果有必要可以完全关闭这个功能。
当然也可以手工创建哈希索引。思路很简单：在B-Tree上创建一个伪哈希索引，与真正的哈希索引不同，因为还是使用B-Tree查找，但是它使用的是哈希值而不是key本身进行索引查找。这样就需要在查询where子句时手动指定使用哈希函数。这样的优点是会在一定程度上提升性能，缺点是需要维护哈希值。如果采用这种方式，记住不用使用SHA1()和MD5()作为哈希函数。因为这两个哈希函数计算出来的哈希值是非常长的，可能导致得不偿失。SHA1()和MD5()是强加密函数，设计目标是最大限度消除冲突。当然，就会有产生哈希冲突的可能性，这时候就需要再把对应值加到后面做判断即可。(数据越多，产生哈希冲突的概率就会越大)
空间索引（R-Tree）
MyISAM表支持空间索引，可以用作地理数据存储。这类索引无须前缀查询。空间索引会从所有维度来索引数据。查询时可以有效使用任意维度来组合查询。（这个索引是真的没用过，之前看过好些书，关于空间索引都是一笔带过，我现在也不太理解“空间”这个概念）
全文索引
全文索引是一种特殊类型的索引，它查找的是文本中的关键词，而不是直接比较索引中的值。
索引的优点
总结如下：
- 索引大幅度减少了服务器需要扫描的数据量
- 索引可以帮助服务器避免排序和临时表
- 索引可以将随机I/O变为顺序I/O
三星原则：
- 一星：索引将相关的记录放到一起
- 二星：索引中的数据顺序和查找的排序一致
- 三星：索引中的列包含了查询需要的全部列
高性能的索引策略
正确地创建和使用索引是实现高性能的基础。
独立的列
如果查询中列是不独立的，则MySQL就不会使用索引。
例如：
select actor_id from sakila.actor where actor_id + 1 = 5;
凭肉眼很容易看出WHERE中的表达式其实等价于actor_id = 4，但是MySQL无法自动解析这个方程，这完全是用户行为。我们应该养成简化where条件的习惯，始终将索引列单独放在比较符号的一侧。
前缀索引和索引选择
有时候需要索引很长的字符列，这会让索引变大且变慢。通常可以索引开始部分的字符，这样可以大大节约索引空间，从而提高索引效率。但是这样会降低索引选择性。（索引选择性是指，不重复的索引值和数据表的记录总数的比值，通常情况下，索引选择性越高，查询效率就越高）
一般情况下某个列前缀的选择性也是足够高的，足以满足查询性能。对于BLOB，TEXT或者很长的VARCHAR类型的列，必须使用前缀索引，因为MySQL不允许索引这些列的完整程度。
所以，关键点就在平衡长度和选择性。保持高的选择性情况下，能尽可能短。前缀应该足够长，以使得前缀索引的选择性接近整个列。为了决定这个长度，需要找到最常见的值的列表，然后和最常见的前缀列表进行比较。（具体情况具体分析，没有统一的定长，尽可能使得前缀索引的选择性接近整个列，而前缀又最短）
虽然前缀索引是一种能使得索引变小，但是前缀索引也有缺陷，MySQL无法使用前缀索引做ORDER BY和GROUP BY，也无法使用前缀索引做覆盖扫描。
多列索引
关于多列索引，有个常见的认识错误：为每个列创建独立索引，或者按照错误的顺序创建多列索引。在多个列上建立独立的单列索引大部分情况下并不能提高MySQL的查询性能。MySQL引入了一种叫“索引合并”的策略，一定程度上可以使用表上的多个单列来定位指定的行。MySQL查询能够同时使用两个单列索引进行扫描，并将结果合并。这种算法有三个变种：OR条件的联合，AND条件的相交，组合前两种的联合以及相交。
索引合并策略有时候是一种优化结果，但实际上更多时候说明了表上的索引建的很糟糕：
- 当出现服务器对多个索引做相交操作时（通常多个AND），这说明需要建立一个包含多个相关列的索引，而不是多个单独列的索引。
- 当服务器需要多个索引做联合操作时（通常多个OR），通常需要消耗大量CPU和内存资源在算法的缓存，排序和合并操作上。
- 更重要的是，优化器不会把这些计算到“查询成本”中，优化器只关心随机页面读取。这会导致查询成本被“低估”，导致执行计划还不如全表扫。
如果在EXPLAIN中看到有索引合并，应该好好检查一下查询和表结构，看是不是已经是最优的。
选择合适的索引列顺序
我们遇到的最容易引起困惑的问题就是索引列的顺序。在多列B-Tree中，是按照最左列进行排序，之后是第二列，等等。所以，索引可以按照升序或者降序进行扫描，以满足精确符合列顺序的ORDER BY，GROUP BY和DISTINCT等子句查询需求。所以，多列索引的顺序很重要。
当不需要考虑排序和分组时，将选择性最高的列放在前面通常是很好的。第二就是选择全局基数小的在前面。这些是经验法则以及在大多数情况下是有用的，但是要注意不要假设平均情况下的性能也能代表特殊情况下的性能，要考虑特殊情况是否会摧毁整个应用的性能。
聚簇索引
聚簇索引并不是一种单独的索引类型，而是一种数据存储的方式。具体细节依赖于其实现方式，但InnoDB的聚簇索引是在B-Tree中保存的。
如果没有定义主键，InnoDB会选择一个唯一的非空索引替代。如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。聚簇索引可能对性能有帮助，也可能会导致问题产生，所以一定要仔细思考聚簇索引，尤其是将表的存储引擎从InnoDB切换到其他引擎的时候（反过来也一样）
聚集的数据有一些重要的优点：
- 可以把相关数据保存在一起。
- 数据访问更快，聚簇索引将索引和数据保存在一个B-Tree中（了解B+树的话就会明白，叶子节点存的是数据，非叶节点存的是索引）。
- 使用覆盖索引扫描的查询可以直接使用页节点中的主键值。
如果在设计表和查询时能充分利用上面的优点（老实说，这里我也没怎么明白，怎么充分利用上面优点来设计），就能极大提升。但是，也是有些许缺陷的：
- 聚簇索引最大限度地提高了I/O密集型应用的性能，但如果数据全部都放在内存中，则访问的顺序就没那么重要了，聚簇索引也就没什么优势了。
- 插入速度严重依赖于插入顺序（按主键顺序插是InnoDB中最快的）。但如果不是按照主键顺序加载数据，那么在加载完成后最好使用OPTIMIZE TABLE命令重新组装一下。
- 更新聚簇索引列的代价很高，因为会强制InnoDB将每个被更新的行移动到新的位置。
- 基于聚簇索引的表插入新行，或者主键被更新导致移动的时候，可能会产生“页分裂”问题。（页分裂，在插入时会产生的一种情况，删除时则可能会发生页合并，了解B+树的话，这个就不难理解。如果插入一个已满的页，会把原来的页分成两个（这里不是操作系统层面那个页），分裂就会导致占更多的空间，具体还是参考B+树）
- 聚簇索引可能导致扫描全表变慢，尤其是行比较稀疏，或者由于分裂导致数据存储不连续。
- 二级索引（非聚簇索引）可能比想象的更大，因为在二级索引的叶子节点包含了引用在行的主键列。
- 二级索引需要两次索引查找，而不是一次（二级索引叶节点保存的并不是指向行的物理位置，而是行的主键值，这里查了两次而不是一次，但在InnoDB中有自适应哈希索引能够减少这样的重复工作）。
在InnoDB中按主键顺序插入行
如果正在使用InnoDB表并且没有什么数据需要聚集，那么可以定义一个代理键作为主键，这种主键的数据应该和应用无关，最简单的方法就是使用AUTO_INCREMENT自增列。这样可以保证数据行是按顺序写入的。
当然新插入的主键值不一定比之前插入的打，所以通常情况下，是需要找到合适的位置，通常是已有数据的中间，并且分配空间。这就会有许多额外的工作，以及一些缺点：
- 写入的目标页可能已经刷到磁盘上并从缓存中移除，或者是还没有被加载到缓存中，InnoDB在插入之前不得不先找到并从磁盘读取目标页到内存中，会导致大量的随机I/O
- 因为写入是乱序，InnoDB不得不频繁刷新地做分页
- 由于频繁的页分裂，页会变得稀疏并被不规则地填充，所以最后会有碎片
在使用InnoDB时应该尽可能地按照主键顺序插入数据，并尽可能地使用单调递增的聚簇键的值来插入新行。
覆盖索引
通常大家都会根据查询的WHERE条件来创建合适的索引，不过这只是索引优化的一个方面。设计优秀的索引应该考虑整个查询。索引确实是一种查找数据的高效方式，但是MySQL也可以使用索引来直接获取列的数据，这样就不再需要读取数据行。
覆盖索引是非常有用的工具，能够极大的提高性能。考虑一下如果查询只需要扫描索引而无须回表，会有很多好处：
- 索引条目通常远小于数据行的大小，所以如果只需要读取索引，MySQL能极大地减少数据访问量。
- 因为索引是按照列值顺序存储的，所以对于I/O密集型的范围查询会比随机从磁盘读取每一行要少的多。
- 一些存储引擎如MyISAM在内存中只缓存索引，数据依赖于操作系统缓存，因此要访问数据需要一次系统调用。
- 由于InnoDB的聚簇索引，覆盖索引对InnoDB表特别有用，InnoDB的二级索引在叶子节点中保存了行的主键。
并不是索引的索引都可以成为覆盖索引，覆盖索引必须要存储索引列的值，而哈希索引，空间索引和全文索引等都不存储索引列的值，所以MySQL只能对B-Tree索引做覆盖索引。在大多数存储引擎中，覆盖索引只能覆盖那些只访问索引中部分列的查询。
使用索引扫描来做排序
MySQL有两种方式生成有序的结果：一种是排序，另一种是按索引列顺序扫描。如果EXPLAIN出来的type值为“index”则说明是使用了索引扫描做排序（注意和Extra列的“Using index”区分，Extra那个表示的是覆盖索引）。按索引顺序读取的速度通常要比顺序地全表扫描慢，尤其是在I/O密集型的工作负载时。
MySQL可以使用同一个索引既满足排序，又用于查找行。因此，如果有可能，设计索引时应该尽可能地同时满足这两种任务，这样是最好的。如果查询需要关联多张表，则只有当ORDER BY子句引用的字段全为第一个表时，才能使用索引做排序。ORDER BY子句和查找型查询的限制是一样的：需要满足索引的最左前缀的要求。否则MySQL无法利用索引排序。
压缩（前缀压缩）索引
MyISAM使用前缀压缩来减小索引的大小，默认只压缩字符串，但通过参数设置也可以对整数做压缩。
MyISAM压缩的方法是，先完全保存索引块中的第一个值，然后将其他值和第一个值进行比较得到相同前缀的字节数和剩余的不同后缀部分。压缩块使用更少空间，代价是某些操作会更慢（比方说倒序扫描）
冗余和重复索引
MySQL允许在相同的列上建多个索引，无论有意还是无意的。MySQL需要单独维护重复的索引（索引类型不同，不算重复），并且优化器在优化查询的时候也需要逐个地进行考虑，这会影响性能。
重复索引是指在相同的列上按照相同的顺序创建的相应类型的索引。应该避免这样创建重复索引，发现后应该删除掉。
冗余索引和重复索引有些不同，如果创建了索引（A，B）在创建索引（A）就是冗余索引。但是（B，A）以及（B）并不是冗余索引（其他类型索引也不算冗余索引）。大多数情况下不需要冗余索引，除非索引很长（优先考虑扩展原来的索引，如果扩展导致索引太长，就考虑冗余）。
未使用的索引
存在但是从来没有用到的，建议删除。
索引和锁
索引可以让查询锁定更少的行。InnoDB只有访问行的时候才会对其加锁，而索引能够减少InnoDB访问行的行数，减少锁的数量。在新的MySQL版本中（5.1以后，也不算多新，5.5以前都叫老，hahahah）InnoDB可以在服务器端过滤行后就释放掉锁。
维护索引和表
当我加上了合适的索引以后，还需要维护表和索引来确保他们都正常工作。目的有三个：找到并且修复损坏的表；维护准确的索引统计信息；减少碎片。
找到并修复损坏的表
表损坏可能是操作系统，MySQL自身，又或者硬件问题等等。损坏的索引会导致查询返回错误的结果，可以尝试运行CHECK TABLE来检查是否发生了表损坏。CHECK TABLE通常能够找出大多数表和索引的错误。
如果InnoDB引擎出现了表损坏，那么一定出现了严重的错误，需要立刻调查一下。（InnoDB一般不会出现损坏，如果某条查询导致InnoDB表损坏，那么一定是遇到了bug，而不是查询问题），如果数据损坏了，最重要的是找到什么导致了损坏，而不只是简单地修复数据。
更新索引统计信息
MySQL的查询有两个API来了解存储引擎的索引值的分布信息，以决定如何使用索引。第一个API是records_in_range()，通过向存储引擎传入两个边界值获取在这个范围大概有多少记录。第二个是info()，该接口返回各种类型的数据，包括索引的基数。
如果存储引擎向优化器提供的信息不准确，优化器就可能做出错误的决定。可以通过运行ANALYZE TABLE来重新生成统计信息解决这个问题。
减少索引和数据的碎片
如果叶子页在物理分布上是顺序且紧密的，那么查询的性能就会更好。否则，对于范围查询，索引覆盖扫描等操作来说，速度可能会降低很多倍。可以通过执行OPTIMIZE TABLE或者导出在导入的方式来重新整理数据。对于InnoDB可以“在线”删除索引，然后重新添加索引来消除索引碎片化。
杂谈（非正式向）
对于B-Tree类索引的学习，推荐还是提前了解学习一下B+树，因为我在之前就学习了解过了树家族（其实就是常规树那一套，如果你没接触过树这种结构，我推荐：二叉树->顺序二叉树->AVL树->红黑树->B树->B+树，大概这个路线和内容，当然对于树并不只有这几种结构而已，但是其他树的变种并不多见，除非你是专门搞数据结构/算法的或者参加竞赛的，否则学习的性价比并不高）所以能比较好的理解一些。没接触过的可能在某些地方会比较懵，不太能理解底层，那也不要紧，首先还是要明白优劣，哪怕不明白为什么会产生，也得大体知道优劣（这本书主要讲的是一些方法和原理，并不会教实操，具体不会的操作还是查一查）。看了这部分我充分体会到了“经验”在数据库中的重要性，对于我一个大学还没毕业的人，好多情况真的很难去想象，以及我也没有办法去判断是否还有更好情况，对于我而言，其实好些东西也是纸上谈兵。
至我上一篇blog已经过了快1一个月了。说来惭愧，这一个月我确实没怎么学习，一小部分原因是我在弄毕设，写论文。最大的原因是我上个月很烦躁，基本就是什么也不想干的状态，可能真的是在家宅太久了，4月份终于出门了，距上次出门已经过了65天了。上个月真的是，每天早上起床发呆，看看视频，然后玩switch，下午发呆，看视频，晚上发呆。这个月生活终于能回归一些正轨。其实最近一直想写两篇文章，一个是关于我大学学习生活的，主要是想说说自己学编程/计算机的经历。再有就是想吐槽一下本科毕业论文这玩意。不过得拖一拖吧，等我答辩完了（估计6月了）写这个，大学那个，毕业附近吧。