【MySQL技术内幕】5.4-B+树索引

1.聚集索引

• Innodb中每张表都会有一个聚集索引，其行记录存在该索引的叶子节点上。
• 叶子节点通过双向链表链接，按照主键的顺序排序
• 页中的记录也是双向链表进行维护，物理上可以不按照顺序存储。
• 所有索引只能定位到页，不能通过索引定位到具体的行，到页后通过Page Directory确定行。

聚集索引的另一个好处是,它对于主键的排序查找和范围查找速度非常快。叶子节点的数据就是用户所要查询的数据。如用户需要查询一张注册用户的表,查询最后注册的10位用户,由于B+树索引是双向链表的,用户可以快速找到最后一个数据页,并取出10条记录。若用命令 EXPLAIN进行分析,可得:

可以看到虽然使用 ORDER BY对记录进行排序,但是在实际过程中并没有进行所谓的 filesort操作,而这就是因为聚集索引的特点另一个是范围查询( range query),即如果要查找主键某一范围内的数据,通过叶子节点的上层中间节点就可以得到页的范围,之后直接读取数据页即可,又如:

执行 EXPLAIN得到了 MySQL数据库的执行计划( execute plan),并且在rows列中给出了一个查询结果的预估返回行数。要注意的是,rows代表的是一个预估值,不是确切的值。

2.辅助索引

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

辅助索引的存在并不影响数据在聚集索引中的组织,因此每张表上可以有多个辅助索引。当通过辅助索引来寻找数据时, InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键,然后再通过主键索引来找到个完整的行记录。举例说,如果在一棵高度为3的辅助索引树中查找数据,那需要对这棵辅助索引树遍历3次找到指定主键,如果聚集索引树的高度同样为3,那么还需要对聚集索引树进行3次查找,最终找到一个完整的行数据所在的页,因此一共需要6次逻辑IO访问以得到最终的一个数据页。

3.B+树索引的分裂

B+树索引页的分裂并不总是从页的中间记录开始,这样可能会导致页空间的浪费。原因参考juejin.im/post/684490…

InnoDB存储引擎的 Page Header中有以下几个部分用来保存插入的顺序信息:

• PAGE_LAST_INSERT
• PAGE_DIRECTION
• PAGE_N_DIRECTION

通过这些信息, InnoDB存储引擎可以决定是向左还是向右进行分裂,同时决定将分裂点记录为哪一个。若插入是随机的,则取页的中间记录作为分裂点的记录,这和之前介绍的相同。若往同一方向进行插入的记录数量为5,并且目前已经定位( cursor)到的记录( InnoDB存储引擎插入时,首先需要进行定位,定位到的记录为待插人记录的前条记录)之后还有3条记录,则分裂点的记录为定位到的记录后的第三条记录,否则分裂点记录就是待插入的记录。

来看一个向右分裂的例子,并且定位到的记录之后还有3条记录,则分裂点记录如图所示。

图5-17向右分裂且定位到的记录之后还有3条记录, split record为分裂点记录最终向右分裂得到如图5-18所示的情况。

对于图5-19的情况,分裂点就为插入记录本身,向右分裂后仅插入记录本身,这在自增插人时是普遍存在的一种情况

4.B+树索引的管理

4.1 索引管理

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

CREATE/ DROP INDEX的语法同样很简单:

用户可以设置对整个列的数据进行索引,也可以只索引一个列的开头部分数据,如

alter table t add key ids_b (b(100));

若用户想要查看表中索引的信息,可以使用命令 SHOW INDEX。

mysql> show index from t_reco_confirm_summary\G
*************************** 1. row ***************************
        Table: t_reco_confirm_summary
   Non_unique: 0
     Key_name: PRIMARY
 Seq_in_index: 1
  Column_name: id
    Collation: A
  Cardinality: 11422
     Sub_part: NULL
       Packed: NULL
         Null:
   Index_type: BTREE
      Comment:
Index_comment:
*************************** 2. row ***************************
        Table: t_reco_confirm_summary
   Non_unique: 1
     Key_name: idx_rd_date
 Seq_in_index: 1
  Column_name: record_date
    Collation: A
  Cardinality: 300
     Sub_part: NULL
       Packed: NULL
         Null:
   Index_type: BTREE
      Comment:
Index_comment:
*************************** 3. row ***************************
        Table: t_reco_confirm_summary
   Non_unique: 1
     Key_name: idx_channel
 Seq_in_index: 1
  Column_name: channel
    Collation: A
  Cardinality: 14
     Sub_part: NULL
       Packed: NULL
         Null:
   Index_type: BTREE
      Comment:
Index_comment:
*************************** 4. row ***************************
        Table: t_reco_confirm_summary
   Non_unique: 1
     Key_name: idx_channel
 Seq_in_index: 2
  Column_name: merchant_id
    Collation: A
  Cardinality: 74
     Sub_part: NULL
       Packed: NULL
         Null:
   Index_type: BTREE
      Comment:
Index_comment:
4 rows in set (0.01 sec)

接着具体阐述命令 SHOW INDEX展现结果中每列的含义。

• Table:索引所在的表名。
• Non_unique:非唯一的索引,可以看到 primary key是0,因为必须是唯的
• Key_name:索引的名字,用户可以通过这个名字来执行 DROP INDEX
• Seq_in_index:索引中该列的位置,如果看联合索引idx_channel就比较直观了。
• Column_name:索引列的名称。
• Collation:列以什么方式存储在索引中。可以是A或NULL。B+树索引总是A,即排序的。如果使用了Heap存储引擎,并且建立了Hash索引,这里就会显示NULL了。因为Hash根据Hash桶存放索引数据,而不是对数据进行排序。
• Cardinality:非常关键的值,表示索引中唯一值的数目的估计值。 Cardinality表的行数应尽可能接近1,如果非常小,那么用户需要考虑是否可以删除此索引。
• Sub_part:是否是列的部分被索引。如果看idxb这个索引,这里显示100,表示只对b列的前100字符进行索引。如果索引整个列,则该字段为NULL
• Packed:关键字如何被压缩。如果没有被压缩,则为NULL。
• Null:是否索引的列含有NULL值。
• Index type:索引的类型。 InnoDB存储引擎只支持B+树索引,所以这里显示的都是 BTREE。
• Comment:注释。

Cardinality值非常关键,优化器会根据这个值来判断是否使用这个索引。但是这个值并不是实时更新的,即并非每次索引的更新都会更新该值,因为这样代价太大了。因此这个值是不太准确的,只是一个大概的值。如果需要更新索引 Cardinality的信息,可以使用 ANALYZE TABLE命令,如:

mysql> analyze table t;
+----------+---------+----------+----------+
| Table    | Op      | Msg_type | Msg_text |
+----------+---------+----------+----------+
| mytest.t | analyze | status   | OK       |
+----------+---------+----------+----------+
1 row in set (0.02 sec)

4.2 Fast Index Creation

MySQL5.5版本之前(不包括55)存在的一个普遍被人诟病的问题是 MySQL数据库对于索引的添加或者删除的这类DDL操作, MySQL数据库的操作过程为:

• 首先创建一张新的临时表,表结构为通过命令 ALTER TABLE新定义的结构
• 然后把原表中数据导入到临时表。
• 接着删除原表。
• 最后把临时表重名为原来的表名。

可以发现,若用户对于一张大表进行索引的添加和删除操作,那么这会需要很长的时间。更关键的是,若有大量事务需要访问正在被修改的表,这意味着数据库服务不可用。

InnoDB存储引擎从 InnoDB1.0.x版本开始支持一种称为 Fast Index Creation(快速索引创建)的索引创建方式——简称FIC。

对于辅助索引的创建, InnoDB存储引擎会对创建索引的表加上一个S锁。在创建的过程中,不需要重建表,因此速度较之前提高很多,并且数据库的可用性也得到了提高。删除辅助索引操作就更简单了, InnoDB存储引擎只需更新内部视图,并将辅助索引的空间标记为可用,同时删除 My SQL数据库内部视图上对该表的索引定义即可。这里需要特别注意的是,临时表的创建路径是通过参数 tmpdir进行设置的。用户必须保证 tmpdir有足够的空间可以存放临时表,否则会导致创建索引失败。

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

4.3 Online DDL

虽然FIC可以让 InnoDB存储引擎避免创建临时表,从而提高索引创建的效率。但正如前面小节所说的,索引创建时会阻塞表上的DML操作。MySQL5.6版本开始支持 Online DDL(在线数据定义)操作,其允许辅助索引创建的同时,还允许其他诸如 INSERT、 UPDATE, DELETE这类DML操作,这极大地提高了 MySQL数据库在生产环境中的可用性。

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

• 辅助索引的创建与删除
• 改变自增长值
• 添加或删除外键约束
• 列的重命名

通过新的ALTER TABLE语法,用户可以选择索引的创建方式:

ALGORITHM指定了创建或删除索引的算法,COPY表示按照 MySQL5.1版本之前的工作模式,即创建临时表的方式。 INPLACE表示索引创建或删除操作不需要创建临时表。 DEFAULT表示根据参数 old_alter_table来判断是通过 INPLACE还是COPY的算法,该参数的默认值为OFF,表示采用 INPLACE的方式,如:

mysql> select @@version;
+-----------+
| @@version |
+-----------+
| 5.7.21    |
+-----------+
1 row in set (0.00 sec)
 
mysql> show variables like 'old_alter_table';
+-----------------+-------+
| Variable_name   | Value |
+-----------------+-------+
| old_alter_table | OFF   |
+-----------------+-------+
1 row in set (0.00 sec)

1 row in set (0.00 sec)

LOCK部分为索引创建或删除时对表添加锁的情况,可有的选择为:

(1) NONE

执行索引创建或者删除操作时,对目标表不添加任何的锁,即事务仍然可以进行读写操作,不会收到阻塞。因此这种模式可以获得最大的并发度。

(2) SHARE

这和之前的FC类似,执行索引创建或删除操作时,对目标表加上一个S锁。对于并发地读事务,依然可以执行,但是遇到写事务,就会发生等待操作。如果存储引擎矿支持 SHARE模式,会返回一个错误信息。

(3) EXCLUSIVE

在 EXCLUSIVE模式下,执行索引创建或删除操作时,对目标表加上一个X锁。读写事务都不能进行,因此会阻塞所有的线程,这和COPY方式运行得到的状态类似,但是不需要像COPY方式那样创建一张临时表。

(4 DEFAULT

DEFAULT模式首先会判断当前操作是否可以使用NONE模式,若不能,则判断是否可以使用 SHARE模式,最后判断是否可以使用 EXCLUSIVE模式。也就是说DEFAULT会通过判断事务的最大并发性来判断执行DDL的模式。

InnoDB存储引擎实现 Online DDl的原理是在执行创建或者删除操作的同时,将INSERT、 UPDATE、 DELETE这类DML操作日志写入到一个缓存中。待完成索引创建后再将重做应用到表上,以此达到数据的一致性。这个缓存的大小由参数 innodb_online_alter_log_max_size控制,默认的大小为128MB。若用户更新的表比较大,并且在创建过程中伴有大量的写事务,如遇到 innodb_online_alter_log_max_size的空间不能存放日志时,会抛出类似如下的错误:

Error: 1799SQLSTATE: HY000(ER INNODB ONLINE LOG TOO BIG)

Message: Creating index tidx aaa required more than 'innodb_online_alter_log_max_size' bytes of modification log. Please try again

对于这个错误,用户可以调大参数innodb_online_alter_log_max_size,以此获得更大的日志缓存空间。此外,还可以设置 ALTER TABLE的模式为 SHARE,这样在执行过程中不会有写事务发生,因此不需要进行DML日志的记录。

需要特别注意的是,由于 Online DDl在创建索引完成后再通过重做日志达到数据库的最终一致性,这意味着在索引创建过程中,SQL优化器不会选择正在创建中的索引