B+树索引

B+树索引

B+树索引并不能找到一个给定键值的具体行，B+树索引能找到的只是被查找数据所在的页。

然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要查找的数据。

B+树总是会保持平衡。但是为了保持平衡对于新插入的键值可能需要做大量的

拆分页（split）操作。因为B+树结构主要用于磁盘，页的拆分意味着磁盘操作，

所以应该在可能的情况下尽量减少页的拆分操作。因此，B+树同样提供了类似于

平衡二叉树的旋转（Rotation）功能。

旋转发生在Leaf Page已经满，但是其左右兄弟节点没有满的情况下。这是B+树

并不会急于做拆分页的操作，而是将记录移到所在页的兄弟节点上。通常情况下，

左兄弟会被首先检查用来做旋转操作。

B+索引在数据库中有一个特点是高扇出性，因此在数据库中，B+树的高度一般都在2~4层，

也就是说查找某一键值的行记录时最多只需要2到4次IO。

当前机械磁盘每秒至少可以做100次IO，2~4次的IO意味着查询时间只需0.02~0.04秒。

B+树索引的管理

索引管理

用户想看表中索引的信息，可以使用命令SHOW INDEX。

其中可以看到Cardinality字段，表示索引中唯一值的数目的估计值。

Cardinality值非常关键，优化器会根据这个值来判断是否使用这个索引。

但这个值并不是实时更新的，即并非每次索引的更新都会更新该值。

可使用 ANALYZE TABLE命令刷新该值

Fast Index Creation

MySQL 5.5版本之前对于索引的添加或删除的这类DDL操作，过程为：

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

若用户对一张大表进行索引的添加和删除操作，那么需要很长的时间。

更关键的是，若有大量事务需要访问正在被修改的表，这意味着数据库服务不可用。

InnoDB存储引擎从1.0.x版本开始支持一种称为Fast Index Creation（快速索引创建）

的索引创建方式——简称FIC。

对于辅助索引的创建，会对创建索引的表加一个S锁，在创建的过程中不需要重建表。

但只能对表进行读操作，写操作依然会阻塞。此外对于主键的创建和删除同样需要重建一张表。

Online Schema Change

Online Schema Change（在线架构改变，简称OSC），所谓在线，即事务在进行中，

仍可以对表进行操作，需要使用脚本实现。

Online DDL

虽然FIC可以让InnoDB存储引擎避免创建临时表，从而提高索引创建的效率。

但索引创建时会阻塞表上的`DML操作。OSC虽然解决了上述部分问题，但有较大局限性。

MySQL 5.6版本开始支持Online DDL在线数据定义，其允许辅助索引创建的同时，还允许

如INSERT、UPDATE、DELETE这类DML操作。以下的操作都可以通过Online DDL的方式进行

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

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

ALTER TABLE tbl_name ADD {INDEX|KEY} [index_name] [index_type] (index_col_name,...) 
 [index_option] ...
ALGORITHM [=] {DEFAULT|INPLACE|COPY}
LOCK [=] {DEFAULT|NONE|SHARED|EXCLUSIVE}

ALGORITHM 指定算法

LOCK 表示对表添加锁的情况

Online DDL的实现原理是在执行DDL动作的同时，将INSERT、UPDATE、DELETE这类DML

操作日志写入到一个缓存中。待DDL完成之后再重做到表上，以此达到数据一致性。

这个缓存默认为128MB，可通过innodb_online_alter_log_max_size控制。