索引是利用程序设计和开发的一个重要方面。若索引太多，应用程序的性能可能会受到影响。而索引太少，对查问性能又会产生影响。要找到一个适合的平衡点，这对应用程序的性能至关重要。

B+树索引是InnoDB存储引擎传统意义上的索引，这是目前关系型数据库系统中查找最为罕用和最为无效的索引。B+树索引的结构相似于二叉树，依据键值（Key Value）疾速找到数据。

须要留神的是：B+树索引并不能找到一个给定键值的具体行，B+树索引能找到的只是被查找数据行所在的页。而后数据库通过把页读入到内存，再在内存中进行查找，最初失去要查找的数据。

B+树

B+树是为磁盘或其余直接存取辅助设备设计的一种均衡查找树。在B+树中，所有记录节点都是按键值的大小程序寄存在同一层的叶子节点上，由各叶子节点指针进行连贯。先来看一个B+树，其高度为2，每页可寄存4条记录，扇出（fan out）为5，如图所示。

所有记录都在叶子节点上，并且是程序寄存的，如果用户从最右边的叶子节点开始程序遍历，能够失去所有键值的程序排序。

B+树的插入操作

B+树的插入必须保障插入后叶子节点中的记录仍然排序，同时须要思考插入到B+树的三种状况，每种状况都可能会导致不同的插入算法。如表所示。

为了保持平衡对于新插入的键值可能须要做大量的拆分页（split）操作。因为B+树结构次要用于磁盘，页的拆分意味着磁盘的操作，所以应该在可能的状况下尽量减少页的拆分操作。因而，B+树同样提供了相似于均衡二叉树的旋转（Rotation）性能。

旋转产生在Leaf Page曾经满，然而其的左右兄弟节点没有满的状况下。这时B+树并不会急于去做拆分页的操作，而是将记录移到所在页的兄弟节点上。在通常状况下，左兄弟会被首先查看用来做旋转操作。

B+树的删除操作

B+树应用填充因子（fill factor）来管制树的删除变动，50%是填充因子可设的最小值。B+树的删除操作同样必须保障删除后叶子节点中的记录仍然排序，同插入一样，B+树的删除操作同样须要思考以下表中的三种状况，与插入不同的是，删除依据填充因子的变动来掂量。

B+树索引

B+树索引的实质就是B+树在数据库中的实现，B+索引在数据库中有一个特点是高扇出性。因而在数据库中，B+树的高度个别都在2～4层，这也就是说查找某一键值的行记录时最多只须要2到4次IO。因为以后个别的机械磁盘每秒至多能够做100次IO，2～4次的IO意味着查问工夫只需0.02～0.04秒。

数据库中的B+树索引能够分为汇集索引（clustered inex）和辅助索引（secondary index），然而不论是汇集还是辅助的索引，其外部都是B+树的，即高度均衡的，叶子节点寄存着所有的数据。汇集索引与辅助索引不同的是，叶子节点寄存的是否是一整行的信息。

汇集索引

汇集索引（clustered index）就是依照每张表的主键结构一棵B+树，同时叶子节点中寄存的即为整张表的行记录数据，也将汇集索引的叶子节点称为数据页。

因为理论的数据页只能依照一棵B+树进行排序，因而每张表只能领有一个汇集索引。在少数状况下，查问优化器偏向于采纳汇集索引。因为汇集索引可能在B+树索引的叶子节点上间接找到数据。此外，因为定义了数据的逻辑程序，汇集索引可能特地快地拜访针对范畴值的查问。查问优化器可能疾速发现某一段范畴的数据页须要扫描。

汇集索引的存储并不是物理上间断的，而是逻辑上间断的。这其中有两点：一是后面说过的页通过双向链表链接，页依照主键的程序排序；另一点是每个页中的记录也是通过双向链表进行保护的，物理存储上能够同样不依照主键存储。

汇集索引的另一个益处是，它对于主键的排序查找和范畴查找速度十分快。叶子节点的数据就是用户所要查问的数据。

辅助索引

对于辅助索引（Secondary Index，也称非汇集索引），叶子节点并不蕴含行记录的全副数据。叶子节点除了蕴含键值以外，每个叶子节点中的索引行中还蕴含了一个书签（bookmark）。该书签用来通知InnoDB存储引擎哪里能够找到与索引绝对应的行数据。因为InnoDB存储引擎表是索引组织表，因而InnoDB存储引擎的辅助索引的书签就是相应行数据的汇集索引键。

B+树索引的治理

索引治理

索引的创立和删除能够通过两种办法，一种是ALTER TABLE，另一种是CREATE/DROP INDEX。通过ALTER TABLE创立索引的语法为：

ALTER TABLE tbl_name ADD {INDEX|KEY} [index_name] [index_type] (index_col_name,...) [index_option] ...ALTER TABLE tbl_name DROP PRIMARY KEY | DROP {INDEX|KEY} index_name

CREATE/DROP INDEX的语法同样很简略：

CREATE [UNIQUE] INDEX index_name [index_type] ON tbl_name (index_col_name,...)DROP INDEX index_name ON tbl_name

用户能够设置对整个列的数据进行索引，也能够只索引一个列的结尾局部数据。

若用户想要查看表中索引的信息，能够应用命令SHOW INDEX，命令SHOW INDEX后果中每列的含意如下：

  • Table：索引所在的表名。
  • Non_unique：非惟一的索引，能够看到primary key是0，因为必须是惟一的。
  • Key_name：索引的名字，用户能够通过这个名字来执行DROP INDEX。
  • Seq_in_index：索引中该列的地位，在联结索引中比拟直观了。
  • Column_name：索引列的名称。
  • Collation：列以什么形式存储在索引中。能够是A或NULL。B+树索引总是A，即排序的。如果应用了Heap存储引擎，并且建设了Hash索引，这里就会显示NULL了。因为Hash依据Hash桶寄存索引数据，而不是对数据进行排序。
  • Cardinality：示意索引中惟一值的数目的估计值。Cardinality表的行数应尽可能靠近1，如果十分小，那么用户须要思考是否能够删除此索引。
  • Sub_part：是否是列的局部被索引。如果索引整个列，则该字段为NULL。
  • Packed：关键字如何被压缩。如果没有被压缩，则为NULL。
  • Null：是否索引的列含有NULL值。
  • Index_type：索引的类型。InnoDB存储引擎只反对B+树索引，所以这里显示的都是BTREE。
  • Comment：正文。

Cardinality值十分要害，优化器会依据这个值来判断是否应用这个索引。然而这个值并不是实时更新的，即并非每次索引的更新都会更新该值，因为这样代价太大了。因而这个值是不太精确的，只是一个大略的值。如果须要更新索引Cardinality的信息，能够应用ANALYZE TABLE命令。倡议在一个非顶峰工夫，对应用程序下的几张外围表做ANALYZE TABLE操作，这能使优化器和索引更好地为你工作。

Fast Index Creation

MySQL 5.5版本之前（不包含5.5）存在的一个广泛被人诟病的问题是MySQL数据库对于索引的增加或者删除的这类DDL操作，MySQL数据库的操作过程为：首先创立一张新的长期表，表构造为通过命令ALTER TABLE新定义的构造。而后把原表中数据导入到长期表，接着删除原表，最初把长期表重名为原来的表名。

能够发现，若用户对于一张大表进行索引的增加和删除操作，那么这会须要很长的工夫。更要害的是，若有大量事务须要拜访正在被批改的表，这意味着数据库服务不可用。

InnoDB存储引擎从InnoDB 1.0.x版本开始反对一种称为Fast Index Creation（疾速索引创立）的索引创立形式——简称FIC。

对于辅助索引的创立，InnoDB存储引擎会对创立索引的表加上一个S锁。在创立的过程中，不须要重建表，因而速度较之前进步很多，并且数据库的可用性也失去了进步。删除辅助索引操作就更简略了，InnoDB存储引擎只需更新外部视图，并将辅助索引的空间标记为可用，同时删除MySQL数据库外部视图上对该表的索引定义即可。

这里须要特地留神的是，长期表的创立门路是通过参数tmpdir进行设置的。用户必须保障tmpdir有足够的空间能够寄存长期表，否则会导致创立索引失败。

因为FIC在索引的创立的过程中对表加上了S锁，因而在创立的过程中只能对该表进行读操作，若有大量的事务须要对指标表进行写操作，那么数据库的服务同样不可用。此外，FIC形式只限定于辅助索引，对于主键的创立和删除同样须要重建一张表。

Cardinality

并不是在所有的查问条件中呈现的列都须要增加索引。对于什么时候增加B+树索引，个别的教训是，在拜访表中很少一部分时应用B+树索引才有意义。对于性别字段、地区字段、类型字段，它们可取值的范畴很小，称为低选择性。

怎么查看索引是否是高选择性的呢？能够通过SHOW INDEX后果中的列Cardinality来察看。Cardinality值十分要害，示意索引中不重复记录数量的预估值。同时须要留神的是，Cardinality是一个预估值，而不是一个精确值，基本上用户也不可能失去一个精确的值。在理论利用中，Cardinality/n_rows_in_table应尽可能地靠近1。

在生产环境中，索引的更新操作可能是十分频繁的。如果每次索引在产生操作时就对其进行Cardinality的统计，那么将会给数据库带来很大的累赘。另外须要思考的是，如果一张表的数据十分大，如一张表有50G的数据，那么统计一次Cardinality信息所须要的工夫可能十分长。这在生产环境下，也是不能承受的。因而，数据库对于Cardinality的统计都是通过采样（Sample）的办法来实现的。

在InnoDB存储引擎中，Cardinality统计信息的更新产生在两个操作中：INSERT和UPDATE。外部更新Cardinality信息的策略为：

  • 表中1/16的数据已产生过变动。
  • stat_modified_counter>2000 000 000。

第一种策略为自从上次统计Cardinality信息后，表中1/16的数据曾经产生过变动，这时须要更新Cardinality信息。第二种状况思考的是，如果对表中某一行数据频繁地进行更新操作，这时表中的数据理论并没有减少，理论发生变化的还是这一行数据，则第一种更新策略就无奈实用这这种状况。故在InnoDB存储引擎外部有一个计数器stat_modified_counter，用来示意发生变化的次数，当stat_modified_counter大于2000 000000时，则同样须要更新Cardinality信息。

InnoDB存储引擎外部是怎么来进行Cardinality信息的统计和更新操作的呢？默认InnoDB存储引擎对8个叶子节点（Leaf Page）进行采样。采样的过程如下：

  1. 获得B+树索引中叶子节点的数量，记为A。
  2. 随机获得B+树索引中的8个叶子节点。统计每个页不同记录的个数，即为P1，P2，…，P8。
  3. 依据采样信息给出Cardinality的预估值：Cardinality=（P1+P2+…+P8）*A/8。

在InnoDB存储引擎中，Cardinality值是通过对8个叶子节点预估而得的，不是一个理论准确的值。再者，每次对Cardinality值的统计，都是通过随机取8个叶子节点失去的，这同时又暗示了另一个Cardinality景象，即每次失去的Cardinality值可能是不同的。

在InnoDB 1.2版本之前，能够通过参数innodb_stats_sample_pages用来设置统计Cardinality时每次采样页的数量，默认值为8。同时，参数innodb_stats_method用来判断如何看待索引中呈现的NULL值记录。该参数默认值为nulls_equal，示意将NULL值记录视为相等的记录。其有效值还有nulls_unequal，nulls_ignored，别离示意将NULL值记录视为不同的记录和疏忽NULL值记录。

当执行SQL语句ANALYZE TABLE、SHOW TABLE STATUS、SHOW INDEX以及拜访INFORMATION_SCHEMA架构下的表TABLES和STATISTICS时会导致InnoDB存储引擎去从新计算索引的Cardinality值。若表中的数据量十分大，并且表中存在多个辅助索引时，执行上述这些操作可能会十分慢。尽管用户可能并不心愿去更新Cardinality值。

InnoDB1.2版本提供了更多的参数对Cardinality统计进行设置，这些参数如下表所示。

B+树索引的应用

联结索引

联结索引是指对表上的多个列进行索引。后面探讨的状况都是只对表上的一个列进行索引。联结索引的创立办法与单个索引创立的办法一样，不同之处仅在于有多个索引列。

从实质上来说，联结索引也是一棵B+树，不同的是联结索引的键值的数量不是1，而是大于等于2。和之前探讨的单个键值的B+树并没有什么不同，键值都是排序的，通过叶子节点能够逻辑上程序地读出所有数据。

应用联结索引须要留神的是陈词滥调的最左匹配准则，应用场景往往是多条件查找以及查找的同时须要进行排序。

笼罩索引

InnoDB存储引擎反对笼罩索引（covering index，或称索引笼罩），即从辅助索引中就能够失去查问的记录，而不须要查问汇集索引中的记录。应用笼罩索引的一个益处是辅助索引不蕴含整行记录的所有信息，故其大小要远小于汇集索引，因而能够缩小大量的IO操作。

对于InnoDB存储引擎的辅助索引而言，因为其蕴含了主键信息，因而其叶子节点寄存的数据为（primary key1，primarykey2，…，key1，key2，…）。如果查问只波及到了辅助索引和主键，那么就不须要去汇集索引中去进行二次查找了。

笼罩索引的另一个益处是对某些统计问题而言的。如果一张表上同时存在汇集索引和辅助索引的话，InnoDB存储引擎并不会抉择通过查问汇集索引来进行统计。因为辅助索引中蕴含有主键值，所以能够用于统计信息，而且体积远小于汇集索引，抉择辅助索引能够缩小IO操作。

在通常状况下，诸如（a，b）的联结索引，个别是不能够抉择列b中所谓的查问条件。然而如果是统计操作，并且是笼罩索引的，则优化器会进行抉择。依据列b范畴查问列a的查问，相似于 select userid from log where date >= '2009-01-01' and date <= '2009-02-01' 的时候也会利用笼罩索引。

优化器抉择不应用索引的状况

在某些状况下，当执行EXPLAIN命令进行SQL语句的剖析时，会发现优化器并没有抉择索引去查找数据，而是通过扫描汇集索引，也就是间接进行全表的扫描来失去数据。这种状况多产生于范畴查找、JOIN链接操作等状况下。例如：

SELECT * FROM orderdetails WHERE orderid > 10000 and orderid < 102000;

表orderdetails有（OrderID，ProductID）的联结主键，此外还有对于列OrderID的单个索引。上述这句SQL显然是能够通过扫描OrderID上的索引进行数据的查找，然而在最初的索引应用中，优化器抉择了PRIMARY汇集索引，也就是表扫描（table scan），而非OrderID辅助索引扫描（index scan）。

起因在于用户要选取的数据是整行信息，而OrderID索引不能笼罩到咱们要查问的信息，因而在对OrderID索引查问到指定数据后，还须要一次书签拜访来查找整行数据的信息。尽管OrderID索引中数据是程序寄存的，然而再一次进行书签查找的数据则是无序的，因而变为了磁盘上的离散读操作。如果要求拜访的数据量很小，则优化器还是会抉择辅助索引，然而当拜访的数据占整个表中数据的蛮大一部分时（个别是20%左右），优化器会抉择通过汇集索引来查找数据。因为之前曾经提到过，程序读要远远快于离散读。

若用户应用的磁盘是固态硬盘，随机读操作十分快，同时有足够的自信来确认应用辅助索引能够带来更好的性能，那么能够应用关键字FORCE INDEX来强制应用某个索引。

索引提醒

MySQL数据库反对索引提醒（INDEX HINT），显式地通知优化器应用哪个索引。以下两种状况可能须要用到INDEX HINT：

  1. MySQL数据库的优化器谬误地抉择了某个索引，导致SQL语句运行的很慢。这种状况在最新的MySQL数据库版本中十分十分的少见。优化器在绝大部分状况下工作得都十分无效和正确。
  2. 某SQL语句能够抉择的索引十分多，这时优化器抉择执行打算工夫的开销可能会大于SQL语句自身。例如，优化器剖析Range查问自身就是比拟耗时的操作。

INDEX HINT的关键词有USE、FORCE、IGNORE等，IGNORE INDEX是通知优化器疏忽该索引，USE INDEX只是通知优化器能够抉择该索引，实际上优化器还是会再依据本人的判断进行抉择。如果用户确定指定某个索引来实现查问，那么最牢靠的是应用FORCE INDEX。

Multi-Range Read优化

MySQL5.6版本开始反对Multi-Range Read（MRR）优化。Multi-Range Read优化的目标就是为了缩小磁盘的随机拜访，并且将随机拜访转化为较为程序的数据拜访，这对于IO-bound类型的SQL查问语句可带来性能极大的晋升。Multi-RangeRead优化可实用于range，ref，eq_ref类型的查问。

对于InnoDB和MyISAM存储引擎的范畴查问和JOIN查问操作，MRR的工作形式如下：

  1. 将查问失去的辅助索引键值寄存于一个缓存中，这时缓存中的数据是依据辅助索引键值排序的。
  2. 将缓存中的键值依据RowID进行排序。
  3. 依据RowID的排序程序来拜访理论的数据文件。

MRR优化有以下几个益处：

  1. MRR使数据拜访变得较为程序。在查问辅助索引时，首先依据失去的查问后果，依照主键进行排序，并依照主键排序的程序进行书签查找。
  2. 缩小缓冲池中页被替换的次数。
  3. 批量解决对键值的查问操作。

此外，Multi-Range Read还能够将某些范畴查问，拆分为键值对，以此来进行批量的数据查问。这样做的益处是能够在拆分过程中，间接过滤一些不合乎查问条件的数据，例如：

SELECT * FROM t WHERE key_part1 >= 1000 AND key_part1 < 2000 AND key_part2 = 10000;

表t有（key_part1，key_part2）的联结索引，因而索引依据key_part1，key_part2的地位关系进行排序。若没有Multi-Read Range，此时查问类型为Range，SQL优化器会先将key_part1大于1000且小于2000的数据都取出，即便key_part2不等于1000。待取出行数据后再依据key_part2的条件进行过滤。这会导致无用数据被取出。如果有大量的数据且其key_part2不等于1000，则启用Mulit-Range Read优化会使性能有微小的晋升。

假使启用了Multi-Range Read优化，优化器会先将查问条件进行拆分，而后再进行数据查问。就上述查问语句而言，优化器会将查问条件拆分为（1000，1000），（1001，1000），（1002，1000），…，（1999，1000），最初再依据这些拆分出的条件进行数据的查问。

是否启用Multi-Range Read优化能够通过参数optimizer_switch中的标记（flag）来管制。当mrr为on时，示意启用Multi-Range Read优化。mrr_cost_based标记示意是否通过cost based的形式来抉择是否启用mrr。若将mrr设为on，mrr_cost_based设为off，则总是启用Multi-Range Read优化。

参数read_rnd_buffer_size用来管制键值的缓冲区大小，当大于该值时，则执行器对曾经缓存的数据依据RowID进行排序，并通过RowID来获得行数据。该值默认为256K。

Index Condition Pushdown（ICP）优化

和Multi-Range Read一样，Index Condition Pushdown同样是MySQL 5.6开始反对的一种依据索引进行查问的优化形式。之前的MySQL数据库版本不反对Index Condition Pushdown，当进行索引查问时，首先依据索引来查找记录，而后再依据WHERE条件来过滤记录。在反对Index ConditionPushdown后，MySQL数据库会在取出索引的同时，判断是否能够进行WHERE条件的过滤，也就是将WHERE的局部过滤操作放在了存储引擎层。在某些查问下，能够大大减少下层SQL层对记录的索取（fetch），从而进步数据库的整体性能。

Index Condition Pushdown优化反对range、ref、eq_ref、ref_or_null类型的查问，以后反对MyISAM和InnoDB存储引擎。当优化器抉择Index Condition Pushdown优化时，可在执行打算的列Extra看到Using index condition提醒。