vlambda博客
学习文章列表

InnoDB存储引擎概述

InnoDB存储引擎支持的索引：

• B+树索引

• 全文索引

• 哈希索引

       InnoDB存储引擎支持的哈希索引是自适应的，InnoDB存储引擎会根据表的使用情况自动为表生成哈希索引，不能认为干预是否在一张表中生成哈希索引。

       B+树索引是目前关系型数据库中 查找最为常用和最为有效的索引。B+树索引类似于二叉树，根据键值快速找到数据。

   

       注意：B+树中的B不是代表二叉，而是代表平衡（balance），因为B+树是从平衡二叉树演化而来，但是B+树不是一个二叉树。

B+树并不能找到一个给定键值的具体行。B+树索引能找到的只是被查找数据所在的页。然后数据库把页读到内存，再在内存中进行查找，最后得到想要查找的数据。

数据结构与算法

        B+树索引是最常见，也是在数据库中使用最广泛的一种索引。因此在了解B+树索引前先了解一下与之相关的一些算法与数据结构。

   

二分查找法

       二分查找法也称为折半查找法，其基本思想是：将记录有序化（递增或递减）排列，在查找时，先以有序数列的中点位置为比较对象，如果要找的元素值小于中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，即可将查找区间缩小一半。

   

二叉查找树和平衡二叉树

       B+树是通过二叉查找树，再由平衡二叉树，B树演化而来。

       在二叉查找树中，左子树的键值总是小于根的键值，右子树的键值总是大于根的键值。

       二叉树可以任意的构造，只要保证左节点的键值小于根的键值，且右节点的键值大于根的键值即可。可这个任意构造的特点也有一个缺点，有可能导致和顺序查找一样，失去二叉查找的效率，如果需要构造一个高性能的二叉树，那么就需要这个二叉树是平衡的，从而引出新的定义——平衡二叉树，或称为AVL树。

       平衡二叉树的定义：首先符合二叉查找树的定义，其次必须满足任何节点的两个子树的高度最大差为1。平衡二叉树的性能是比较高的，但不是最高的，最好的性能是建立一颗最优二叉树，但这成本非常高，因此一般情况下平衡二叉树即可满足需要。

       维护一个平衡二叉树的代价是非常大的，通常需要1次或多次左旋和右旋得到插入或更新后树的平衡性。

B+树

       B+树由B树和索引顺序访问方法演化而来，但是在现实中B树已经很少使用了。

       B+树的简单定义：B+树是为磁盘或其他直接存取辅助设计的一种平衡二叉树。B+树中 ，所有节点都是按键值的大小顺序放在同一层的叶子节点上，由各叶子节点指针进行连接。

B+树的插入

       B+树的插入必须保证插入后叶子节点中的记录依然有序，同时需要考虑插入到B+树的三种情况，每种情况都会导致不同的插入算法。

      不管怎么变化，B+树总是会保持平衡，但为了保持平衡会对新插入的键值做大量的拆分页操作，因为B+树结构主要用于磁盘，页的拆分意味着磁盘的操作，所以应尽可能少的拆分。因此，B+树同样提供了类似于平衡二叉树的旋转功能。

       旋转发生在Leaf Page已经满，但是其左右兄弟节点没有满的情况下。此时B+树不会急于进行页的拆分，而是将将记录移到所在页的兄弟节点上。通常情况下，左兄弟会被首先检查用于做旋转操作。

  

B+树的删除

      B+树使用填充因子来控制树的删除变化，50%是填充因子可设的最小值。B+树的删除操作同样必须保证删除后叶子点中记录的有序性。且在插入时，同样需要考虑三种情况。

B+树索引

       B+树索引的本质就是B+树在数据库中实现。但是B+树索引在数据库中有一个特点是高扇出性，因此在数据库中B+树的高度一般在2-4层，也就是在查找数据时最多只需要2-4次IO。因为当前机械硬盘每秒至少可以做100次IO，2-4次IO意味着查询时间只需0.02-0.04秒，可以接受。

      B+树索引可以分为聚集索引和辅助索引，但不管是聚集还是辅助的索引，其内部都为B+树结构，即高度平衡，叶子节点存放着所有的数据，两者不同的是叶子节点存放的是否是一整行的信息。

   

聚集索引

       InnoDB引擎表是索引组织表，即表中的数据是按照主键顺序存放。而聚集索引就是按照每张表的主键构造一颗B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。聚集索引的这个特性决定了 索引组织表中数据也是索引的一部分，每个数据页都通过一个双向链表来进行链接。

       由于实际的数据页只能按照一颗B+树进行排序，因此每张表只能拥有一个聚集索引。多数情况下，查询优化器倾向于采用聚集索引。因为聚集索引能够在B+树索引的叶子节点上直接找到数据。

       聚集索引的存储并不是物理上连续的，而是逻辑上连续的。其中有两点：

1. 页通过双向链表链接，页按照主键的顺序排序。

2. 每个页中的记录也是通过双向链表进行维护的，物理存储上可以不按照主键存储。

  

      聚集索引的另一个好处是，它对于主键的排序查找和范围查找速度非常快。叶子节点的数据就是用户所要查询的数据。

辅助索引

       辅助索引也称为非聚集索引，叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签。该书签的作用是告知InnoDB引擎哪里可以找到与索引相对应的行数据。由于InnoDB引擎表是索引组织表，因此InnoDB存储引擎的辅助索引的书签就是相应的行数据的聚集索引键。

       辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表上可以有多个辅助索引。当通过辅助索引寻找数据时，InnoDB引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引找到一个完整的行记录。

B+树索引的分裂

       B+树索引页的分裂并不总是从页的中间记录开始，这样可能会导致页空间的浪费。InnoDB引擎的Page Header中的以下几个部分用来保存插入的顺序信息：

1. PAGE_LAST_INSERT

2. PAGE_DIRECTION

3. PAGE_N_DIRECTION

       通过这些信息，InnoDB可以决定向右还是向左进行分裂，同时决定将分裂点记录为哪一个。若插入是随机的，则取页的中间记录作为分裂点的记录。若往同一方向进行插入的记录数量为5，且目前已经定位到的记录之后还有3条记录，则分裂点的记录为定位到的记录后的第三条记录，否则分裂点记录就是待插入的记录。

B+树索引的管理

       索引的创建和删除可以通过两种方法，一种是ALTER TABLE，另一种是CREATE/DROP INDEX。

        Cardinality值非常关键，优化器会根据这个值来判断是否使用索引，但是该值并非实时更新的，即并非每次索引的更新都会更新该值，因为如何实时更新单价会很大。如果需要更新索引Cardinality的信息，可以使用ANALYZE TABLE命令。

       有时Carginality为NULL，在某些情况下可能会发生索引建立了却没有用到的情况。或者对两条基本一样语句执行EXPLAIN，但是最终结果却不一样：一个使用索引，另一个全表扫描，这时最好的办法就是做一次ANALYZE TABLE操作。此外建议在一个非高峰时间，对应用程序的几张核心表做ANALYZETABLE操作，这可以使优化器和索引更好地为你工作。

MySQL5.5之前，MySQL对于索引的添加或者删除操作，其过程为：

1. 首先创建一张新的临时表，表结构为通过命令ALTER TABLE新定义的结构。

2. 然后把原表中数据导入到临时表。

3. 接着删除原表。

4. 最后把临时表重名为原来的表名。

  

 InnoDB引擎从InnoDB 1.0.x版本开始支持一种称为Fast Index Creation的索引创建方式——简称FIC。对于辅助索引的创建，InnoDB引擎会对创建索引的表加一个S锁。在创建的过程中，不需要重建表，因此速度较之前提高很多，且数据库的可用性也得到了提高。删除辅助索引操作就更简单了，InnoDB引擎只需要更新内部视图，并将辅助索引的空间标记为可用，同时删除MySLQ数据库内部视图上对该表的索引定义即可。

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

       Online Schema Change最早是由Facebook实现的一种在线执行DDL的方式，并广泛地应用于Facebook的MySQL数据库。所谓在线是指，可以在事务的创建过程中，可以有读写事务对表进行操作，这提高了原有MySQL数据库在DDL操作时的并发性。

       FIC功能优点很多，但还是有很大的局限性。MySLQ5.6开始支持Online DDL（在线数据定义）操作，其允许辅助索引创建的同时，还允许其他诸如INSERT、UPDATE、DELETE这类操作，这极大提高了MySQL数据库在生产环境中的可用性。

       此外，不仅是辅助索引，以下这几类DDL操作都可以通过“在线”的方式进行操作：

1. 辅助索引的创建与删除。

2. 改变自增长值。

3. 添加或删除外键约束。

4. 列的重命名。

InnoDB引擎实现Online DDL的原理是在执行创建或者删除的同时，将DML类操作日志写入到一个缓存中，待完成索引创建后再将重做应用到表上，一次达到数据的一致性。这个缓存的大小由参数innodb_online_alter_log_max_size控制，默认大小为128M。

Cardinality值

       对于什么时候添加B+数索引，一般的经验是，在访问表中很少一部分时使用B+树索引才有意义。比如按性别进行查询时，可取值范围一般只有“男 或 女”，因此查询得到的结果可能是表中50%的数据，此时B+树索引是没有必要的。相反，如果某个字段的取值范围很广，几乎没有重复，即属于高选择性，此时使用B+树索引是最合适的。

     如何查看索引是否是高选择性呢？可通过SHOW INDEX结果中的Cardinality来观察。Cardinality值非常关键，表示索引中不重复记录数量的预估值，但并不是准确值。在实际应用中，Cardinality/n_row_in_table应尽可能接近1。如果非常小，那么用户就要考虑是否有必要创建索引。故在访问高选择性属性的字段并从表中取出很少一部分数据时，对这个字段添加B+树索引是非常有必要的。

InnoDB引擎的Cardinality统计

       数据库对于Cardinality的统计都是通过采样的方法来完成的。InnoDB引擎中，Cardinality统计信息的更新发生在两个操作：INSERT和UPDATE。但也不是每次发生INSERT和UPDATE时就去更新Cardinality信息，因此InnoDB引擎对更新Cardinality信息的策略为：

1. 表中1/16的数据已经发生过变化。

2. stat_modified_counter>2000000000。

  

InnoDB引擎通过“采样”的方法进行Cardinality信息的统计和更新。默认InnoDB引擎对8个叶子节点进行采用。采样过程如下：

1. 取得B+树索引中叶子节点的数量，记为A。

2. 随机取得B+树索引中的8个叶子节点，统计每个页不同记录的个数，即为P1，P2，...，P8。

3. 根据采样信息给出Cardinality的预估值：Cardinality=（P1+....+P8）*A/8。

B+树索引的使用

联合索引

       联合索引是指对表上的多个列进行索引。

   

覆盖索引

       InnoDB引擎支持覆盖索引，即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。使用覆盖索引的一个好处是，辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。

       注意：InnoDB版本小于1.0的，或者数据库版本为5.0或以下的，InnoDB存储引擎不支持覆盖索引的特性。

优化器选择不使用索引的情况

       某些情况下，会发现优化器并没有选择索引去查找数据，而是通过扫描聚集索引，也就是进行全表的扫描来得到数据。

索引提示

       MySQL数据库支持索引提示（INDEX HINT）,显式地告诉优化器使用哪个索引。可能用到INDEX HINT的两种情况为：

1. MySQL数据库的优化器错误选择某个索引，导致SQL语句运行很慢。不过在新的MySQL数据库版本中，这种情况非常少见。

2. 某SQL语句可以选择的索引非常多，这时优化器选择执行计划时间的开销可能会大于SQL语句本身。

  

Multi-Range Read优化

       MySQL5.6版本开始支持Multi-Range Read（MRR）优化。其优化的目的是为了减少磁盘的随机访问，并将随机访问转化为较为顺序的数据访问，这对于IO-bound类型的SQL查询语句可带来性能极大的提升。Multi-Range Read优化可用于range，ref，eq_ref类型的查询。

  

MRR优化有以下几个好处：

1. MRR使数据访问变得较为顺序。在查找辅助索引时，首先根据得到的查询结果，按照主键进行排序，并按照主键排序的顺序进行书签查找。

2. 减少缓冲池中页被替换的次数。

3. 批量处理对键值的查询操作。

       对于InnoDB和MyISAM引擎的范围查询和JOIN查询缓存，MRR的工作方式如下：

1. 将查询得到的辅助索引键值存放于一个缓存中，这时缓存中的数据是根据辅助索引键值排序的。

2. 将缓存中的键值根据RowID进行排序。

3. 根据RowID的排序顺序来访问实际的数据文件。

Index Condition Pushdown（ICP）优化

         ICP优化同样是MySQL5.6开始支持的一种 根据索引进行查询的方式。

 ICP优化支持range、ref、eq_ref、ref_or_null类型的查询，当前支持MyISAM和InnoDB存储引擎。当优化器选择ICP优化时，可在执行计划的列Extra看到Using index condition提示。

哈希算法

       哈希算法是一种常见的算法，时间复杂度为O（1），且不只存在于索引中，每个数据库应用中都存在该数据结构。

   

哈希表

       哈希表也称散列表，由直接寻址表改进而来。我们先来看直接寻址表。当关键字的全域U比较小时，直接寻址是一种简单有效的技术。

       直接寻址技术存在一个问题，如果域U很大，在一台典型计算机的可用容量的限制下，要在机器中存储大小为U的一张表T就有点不实际，甚至是不可能。如果实际存储的关键字集合K相对于U来说很小，那么分配给T的大部分空间都要浪费掉。因此哈希表出现了。

      哈希表技术很好解决了直接寻址遇到的问题，但是这样有一个小问题，如果两个关键字映射到同一 个槽上。一般将之称为碰撞。在数据库中一般采用链接法解决碰撞问题。

   

InnoDB存储引擎中的哈希算法

      InnoDB引擎使用哈希算法来对字典进行查找，其冲突机制采用链表格式，哈希函数采用除法散列方式。对于缓冲池页的哈希表来说，在缓冲池的Page页都有一个chain指针，它指向相同哈希函数值的页。对于除法散列，m的取值为略大于2倍的缓冲池页数的质数。

   

自适应哈希索引

       自适应哈希索引采用哈希表的方式实现。不同的是，这仅是数据库自身创建并使用的，不能人为的干预。   

   

全文索引

       全文索引是将存储于数据库中的整本书或整篇文章中的任意内容信息查找出来的技术。从InnoDB1.2.x版本开始，InnoDB引擎开始支持全文检索，其支持MyISAM存储引擎的全部功能，且还支持其他一些特性。   

   

倒序索引

      全文检索通常使用倒序索引来实现。倒排索引同B+树一样，也是一种索引结构。它在辅助表中存储了单词与单词自身在一个或多个文档中所在位置之间的映射，这通常利用关联数组实现，其拥有两种表现形式：

1. inverted file index，其表现形式为{单词，单词所在文档的ID}

2. full inverted index，其表现形式为{单词，（单词所在文档的ID，在具体文档中的位置）}

  

InnoDB全文检索

       InnoDB引擎从1.2.x版本开始支持全文检索的技术，其采用full inverted index的方式。在InnoDB引擎中，将（DocumentID,Position）视为一个“ilist”。因此在全文检索表中有两个列，一个是word字段，另一个是ilist字段，且在word字段上设有索引。此外InnoDB引擎在ilist字段中存放了Position信息，故可以进行Proximity Search，而MyISAM引擎不支持该特性。  

当前InnoDB引擎的全文检索还存在以下限制：

1. 每张表只能有一个全文检索的索引。

2. 由多列组合而成的全文检索的索引列必须使用相同的字符集与排序规则。

3. 不支持没有单词界定符的语言，如中文、日语、韩语等。

   

全文检索

       MySQL通过MATCH()...AGAINST()语法 支持全文检索的查询。MATCH指定了需要被查询的列，AGAINST指定了使用何种方法去进行查询。

Natural Language

      全文检索通过MATCH函数进行查询，默认采用Natural Language模式，其表示查询带有指定word的文档。由于NATURAL LANGUAGE MODE是默认的全文检索查询模式，因此可以省略查询修饰符。  

   

Boolean

       当使用IN BOOLEAN MODE修饰符进行全文检索时，查询字符串的前后字符会有特殊的含义。   

   

Query Expansion

      MySQL还支持全文检索的扩展查询。这种查询通常在查询的关键词太短，用户需要隐藏知识时进行。

通过在查询短语中添加 WITH QUERY EXPANSION 或 IN NATURAL LANGUAGE MODE WITH QUERY EX-PANSION

可以开启 blind query expansion。该查询分为两个阶段：

1. 根据搜索的单词进行全文索引查询。

2. 根据第一阶段产生的分词再进行一次全文检索的查询。

参考资料：《MySQL技术内幕：InnoDB存储引擎》