乐趣区

关于mysql:MySQL原理索引

jiezi

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

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 提醒。

退出移动版