[toc]

索引与算法

存储索引概述

InnoDB支持的几种索引：B+树（不是二叉binary，是balance）、全文、hash

B+数这个后面展开讲，hash是自适应的不受人为的干涉，全文这里也没讲是啥

数据结构和算法

这里就是简单的介绍一下相关的算法和结构

二分查找

需要数据本身就排好序的，折半查找

二叉查找树和平衡二叉树

二叉查找树就一个左小右大的二叉树，不要求平衡，性能不是很高

平衡二叉树就是平衡的二叉查找树，平衡二叉树的查询性能是比较高的，最高的是最优二叉树，但这个东西构建和维护的开销大，一般只需要建立一个平衡二叉树

B+树

这个图可以很好的说明B+树的基础机构

插入操作

这里就简单说一下

如果叶子节点和它的父节点都没满的话，就直接插入，这个时候最理想
如果叶子节点满了但是它的父节点还没满的话，那就分裂子节点把子节点的中间值放到父节点去
如果叶子节点和它的父节点都满了的话，就要先分裂子节点，再分裂父节点
另外如果叶子节点满了，但是做兄弟节点没满的话不会直接做分裂，左兄弟会检查做旋转操作来节省开销

删除操作

它这里给每个节点设置最少也有有一半的数据，如果低于了一半那就需要做节点的合并，具体的合并规则这里不展开说了

B+树索引

聚簇索引

首先聚簇索引是指行数据会存储在B+树的叶子结点上，非聚簇索引的叶子节点上存储的上聚簇索引的索引数据也就是主键
InnoDB的表数据就是通过一颗主键聚簇索引进行存储的
聚簇索引在磁盘上存储的时候是逻辑上连续的，由于叶子结点通过双向链表进行了连接，物理页不要求完全连续（会多出寻址时间）

辅助索引

也就是非聚簇索引

如果查询的数据在辅助索引上没有那就需要去聚簇索引上查询，叫做回表

B+树索引的分裂

B+树索引的分裂并不总是从页中间开始，会做一些优化来决定是向左还是向右分裂

B+树索引的管理

创建和删除的语句这里就不列举了
查看索引信息时有一个参数比较重要，cardinality可以叫做基数，这个数越大索引能发挥更好的性能，这个值是预估出来的不完全准确，可以通过analyze table来主动的让InnoDB对基数进行重新统计

索引创建&删除的方法

5.5之前使用的方法：

创建一张临时表
把原表数据导入到临时表中
删除原表、重命名临时表

Fast Index Creation

InnoDB 1.0开始支持Fast index creation，对于辅助索引的创建，中表上面加一个S锁，创建的过程中不需要重新建表，速度和可用性都提高了很多

弊端是表加了S锁之后只读，对于写入的事务不能处理，只限定与辅助索引

online schema change

FB发明的，后来被官方集成了，大致方法也没读懂，创建一个新表进行alter table操作，将数据导入新表，创建一个detail表用来记录导入过程中发生的数据修改，最后将detail表中的数据通过日志刷新到新表，删除原表、重命名新表

online DDL

mysql 5.6版本开始支持，允许辅助索引创建的同时进行DML的操作，一下几类DDL支持在线方式：

辅助索引的创建和删除
改变自增长值
添加或删除外键约束
列的重命名
实现原理是，在DDL过程中发生的DML操作写入到缓存中，等DDL完成后将缓冲写入表

Cardinality值

基数、选择性

Cardinality统计

一直进行统计的话太消耗资源了，触发统计的策略：

表中1/16的数据已经发生过变化
数据修改次数超过20e
执行analyze table、show table status、show index以及访问information_schema架构下tables和statistics表时
统计方法：对8个叶子节点进行采样分析（如果数据总量不超过8个叶子结点那统计出来的就是精确值）

B+树索引的使用

OLTP应用：对数据进行访问，使用索引是很不错的
OLAP应用：对数据进行规模化统计，索引只适合在表关联查询的时候以及时间字段（经常会从时间维度进行统计）

联合索引

和普通索引的结构是一样的，只是索引列是多个

覆盖索引

mysql5.0以上才支持，由于辅助索引上能拿到所需的信息就不要再做回表操作了

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

访问数据两超过总体的20%时会直接做表扫描（聚簇索引），可以强制指定使用索引

索引提示

select * from table use index(index_a) where a=1 and b=2建议优化器使用索引index_a至于优化器听不听那就不好说了
select * from table force index(index_a) where a=1 and b=2强制制定优化器使用索引index_a

muliti-range read优化

MySQL 5.6开始支持，目的是减少磁盘随机访问的次数，原理是通过辅助索引进行批量查询时，将从辅助索引上拿到的主键值进行排序再去组建索引上进行查找