Innodb之索引与算法

admin

目录
一、概述
二、数据结构与算法
1、二分查找
2、二叉查找树和平衡二叉树
1）二叉查找树
2）平衡二叉树
三、B+树
1、B+树完整定义
2、关于 M 和 L的选定案例
四、B+树索引
1、聚集索引
2、辅助索引
五、Cardinality 值
1、Cardinality定义
2、Cardinality的更新
六、B+树索引的使用
1、联合索引
2、覆盖索引
3、优化器选择不使用索引的情况
4、索引提示
5、Multi-Range Read 优化 (MRR)
6、Index Condition Pushdown 优化 （ICP）

一、概述
索引太少，查询效率低；索引太多程序性能受到影响，索引的使用应该贴合实际情况。
Innodb 支持的索引包括：

全文检索，使用倒排索引

哈希索引，自适应，不能认为干预，依据缓冲池中的聚集索引页创建，并不会将整张表进行哈希索引，所以建立索引非常快。

B+树索引，传统意义上的索引，目前关系型数据库中最有效和最常用的索引。

B+树并不能定位到表上具体的行记录，而是放回该行记录所在的页；最后在内存中根据 slot槽 信息，以及行记录头中的next record 信息进行精确定位。

二、数据结构与算法
1、二分查找
二分查找只能用来对一组有序的线性数据进行查找，每次取中值，小往前，大往后。时间复杂度 ：log N，如图为对有序数组中的数字48的查找。

2、二叉查找树和平衡二叉树
1）二叉查找树
二叉查找树指的是，一个二叉树中，都满足：任意节点左子节点比自身小，任意节点右子节点大于自身的二叉树，即为二叉查找树。
普通的二叉树无法保证 O(logN) 的访问时间，因为当极端情况下，它甚至可以退化成链表。
当把一组有序的数据按序构建一个二叉树，那么就得到了一个链表，此时时间复杂度变为：O(N)

2）平衡二叉树
平衡二叉树是二叉搜索树，但是它多了一个限制条件：任意节点的两个子节点的树高相差不能超过1。构建二叉树的过程中，如果破坏了这个条件，可以通过适当的旋转来解决。

平衡二叉树保证了时间复杂度为：O(logN)

虽然能保证O(logN) 的访问时间，但是它并不适合用来做数据库索引：

二叉树树高攀升非常快(1024 = 2的10次幂)，当数据量非常巨大时log(N) 也是非常可观的。

其中最糟糕的是，二叉树的叶子节点只能存放一个数据，必定要进行多次的磁盘IO。然而实际应用中相较于CPU的执行指令的时间，频繁读取磁盘将是灾难性的。所以，二叉树并不适合用来做数据库的索引。

对于机械硬盘，其访问时间取决于磁盘转速和磁头移动时间，这都是由机械结构完成的，对比cpu 中执行的电信号指令，速度必定天差地别。<CPU的时钟周期一般以GHz为单位。>

1000万数据，如果使用平衡二叉树（最坏时间界限为 1.44 * logN ），即便不取最坏时间界，按 log(N) 计算最终约为 24，那么说明需要进行 24 次磁盘IO，这显然不行。


【树高为对数值向上取整，例如：log2 = 1，但是树高为2；log3 = 1.58，树高为2；】

三、B+树
由于平衡二叉树的局限，所以需要引入B+树。

B+树是专为磁盘或其它直接存取辅助设备设计的一种平衡查找树，B+ 树中，所有记录节点都是按键值大小，
顺序存放在同一层的叶子节点上，由各叶子节点指针进行链接。
1、B+树完整定义
一颗M阶的B+树需要满足如下的性质：

下列所有定义中的关于两数相除，不能整除时往上取整，而不是丢弃小数位。(案例中推演不等式除外)

1）数据项必须存在叶子节点上

2）非叶节点存贮M-1个关键字以指示搜索方向；关键字 i 代表非叶节点的第i + 1 棵子树中最小的关键字；假设5阶B+树，那么它有 5 - 1 = 4 个关键字。

3）B+树要么只有一个树叶节点作为根节点(没有任何儿子节点)；如果它有儿子节点，它的节点数必须属于集合：{2~M}；

4）除根外，所有非叶节点的儿子节点数必须满足属于集合： { M/2 ，M } ；

5）所有树叶都在相同深度上，且树叶节点的数据项个数必须属于集合：{ L/2 ，L } ；

2、关于 M 和 L的选定案例
以下表为例，模拟推演B+树，主键50字节，算上行记录本身消耗空间，假定所有字段总长不超过500字节：
已知所有行记录都会消耗一些字节记录行信息：例如变长字段，行记录头，事务ID，回滚指针等等。
[mw_shl_code=applescript,true]create table context(
        id  varchar(50) primary key,
        name varchar(50) not null,
        description varchar(360)  
);
[/mw_shl_code]
一个叶子节点代表的是一个数据页，M 和 L 值的选择跟他息息相关，假设数据页大小为：P/字节 （以本文讨论的MySQL为例，一个数据页大小为16K 也就是 16384 个字节。）

非叶节点上：B+树的关键字是主键，本例假设主键为 50 个字节，M阶B+树的关键字为 M -1 个，占用：50 * （M - 1）个字节的空间；

再加上它指向 M 个子节点的分支指针，假定每个分支指针占用4个字节存储；那么一个非叶节点中，所有空间消耗共计：50 * （M - 1）+ 4 * M = 54M - 50字节。

当使用MySQL，且假设主键50个字节，成立不等式： 54M - 50 <= P，其中P = 16384，那么关于 M 的解为：M <= 302 ，阶数M最大可选值约为：302；此处我们最大可以选择一颗，302 阶 B+ 树。

叶子节点上，已知表中定义的每个行的容量的最大为： 500 字节，这时成立如下表达式：L * 500 <= 16384 成立，L的解集为：L <= 32 ；这时 L 我们最大可以选择：32。
如下图，此时5000W数据，树高大于3，说明我们只需要最多4次磁盘IO就能查到数据。

参考下图，平衡二叉树最坏时间界为：1.44 * logN = 25.58 * 1.44 = 36.83；也就是说5000W 数据若使用平衡二叉，树最坏情况下会超过36 次磁盘IO，最少26次磁盘IO。

如图为一颗5 阶普通B+树 (M = 5)，此处每个节点最多5个值（L = 5）; M和L不一定相等，就如上述分析而言: M 和 L视实际情况而定。

哈哈哈画图太麻烦了，我从数据结构与算法分析这本书上拍的照片，机智如我。

这里只讲B+树定义以及参数选取详情，B+树的插入、B+树的删除部分类容不在赘述。

四、B+树索引
一般B+ 树树高 为2~4 层，也就是查找行记录时一般只需要2 ~ 4 次磁盘IO就能找到行记录所在的页。不论聚集索引还是非聚集索引，内部都是高度平衡的，索引的数据都存放于叶子节点，区别是聚集索引的叶子节点存放了整个行记录数据。

1、聚集索引
聚集索引的叶子节点存放整行数据，每张表只能拥有一个聚集索引。

2、辅助索引
辅助索引的叶子节点存储了键值和一个书签，该书签告诉Innodb 存储引擎从哪里可以找到于索引相应的行记录完整数据。<可以认为该书签就是聚集索引的关键字，也就是表的主键>

每张表可以有多个辅助索引

使用辅助索引的去确定是，找到辅助索引存储的书签后，还需要去离散的读聚集索引才能最终得到完整的行数据。

五、Cardinality 值
对于Cardinality的讨论都是基于非聚集索引的，每个非聚集索引都会有一个Cardinality值。

1、Cardinality定义
须知并不是所有查询条件中的列都需要加索引，比如：性别、年纪、科目等取值范文小密集分布的字典量。
Cardinality 表示索引中不重复记录数量的 预估值 ，一般： Cardinality / 表中记录行数 应尽量接近 1；如果非常小，则需要考虑该索引是否应该去掉。(聚集索引中该值必定接近于1，没有讨论价值)。

2、Cardinality的更新
MySQL中由于各存储引擎对于B+树索引的实现各不相同，所以Cardinality 的统计是在存储引擎层实现的。
当表中数据量非常巨大时，对Cardinality 进行统计是非常耗时的，它的统计一般使用采样的方法来进行。

。。。。。。待续

六、B+树索引的使用
【 本部分讨论的索引多指辅助索引，对聚集索引的查询一般称为全表扫描。】

1、联合索引
联合索引是在表上的多个列上建索引，它也是B+树结构，与单个索引的区别仅是它存在多个列。
[mw_shl_code=applescript,true]create table t (
        a int,
        b int,
        primary key (a),
        key idx_ab (a, b)
)engine=innodb;
[/mw_shl_code]
上表中，设置联合主键idx_ab，其存储结构如下所述：

如上图所述，键值有序，需要注意的是，如下SQL可以使用该索引：
[mw_shl_code=applescript,true]        select * from t where a = ? and b = ?
       
        select * from t where a = ?
[/mw_shl_code]
如下sql 不能使用该索引，查看联合索引叶子节点存放的数据，两个叶子节点上，关于字段b的存放显然不是有序的。
[mw_shl_code=applescript,true]        select * from t where b = ?
[/mw_shl_code]
联合索引本身还有一个好处，辅助索引本身已经对第二个键值进行了排序，如下语句可以避免多一次的排序。
        [mw_shl_code=applescript,true]select b from t where a = ?  order by b desc[/mw_shl_code]
辅助索引中已经对 b 列进行了排序，所以此时使用辅助索引更高效。

2、覆盖索引
Innodb 支持覆盖索引(covering index，或称为索引覆盖)，即从辅助索引中就可以得到结果，而不需要查询聚集索引中的记录。因为辅助索引不包含完整的行记录，所以它比聚集索引要小很多，可以减少大量IO操作。

再形如：select count(*) from table name where b <= ? and b >= ? 的sql，如果有满足条件的辅助索引，它会优先使用辅助索引因为辅助索引体积远远小于聚集索引。

3、优化器选择不使用索引的情况
某些情况下，通过EXPLAIN指令会发现一些SQL，并没有选择使用满足条件的辅助索引去查数据，而是直接选择了全表扫描(聚集索引)，这种情况一般发生于 范围查找、join链接操作等情况下。

当发生此类查找时，一般是查找一个较大范围内的数据，当范围较大时同样意味着大量的数据需要再进行一次书签访问去获取完整数据，已知顺序读取速度大于离散读取速度，所以此时不会使用辅助索引，而是直接查聚集索引(整表扫描)。（一般当访问数据超过表中数据总数 20%时，会出现不能进行索引覆盖的问题。）
[mw_shl_code=applescript,true]        create table t (
                a int,
                b int,
                primary key (a,b),
                key idx_a (a)
        )engine=innodb;
[/mw_shl_code]
如上定义表，a和b两列构成联合索引，列a上有独立的辅助索引，对于语句：

[mw_shl_code=applescript,true]select * from  t where  a >= 3  and a<= 1000000;
[/mw_shl_code]
按理说，该语句是可以选择使用辅助索引 idx_a 进行查找的，但是通过执行 explain 发现该语句发生了全表扫描(聚集索引)，而不是使用辅助索引： idx_a。

4、索引提示
索引提示指MySQL支持在SQL中显式的告诉优化器使用哪个索引。

当优化器选择索引错误，可以手动指定索引。[极小概率事件]

当索引太多时，优化器选择索引的操作时间开销大，此时可以手动指定索引。

使用索引提示的前提是我们自己要对sql的执行非常了解，非常明确该操作能带来更好的效率。

5、Multi-Range Read 优化 (MRR)
MySQL5.6版本开始支持Multi-Range Read (MRR) 优化，它的目的是减少磁盘的离散度，将离散的访问优化为相对有序的访问，它使用于 range ref eq_ref 类型的查询。

1).MRR优化有如下好处：

它使得数据访问变得较为顺序，当根据辅助索引查询是，会将查询结果按照主键排序后，再去聚集索引进行书签查询。

减少缓冲池中页被替换的次数；

批量处理对键值的查询操作；

2).对于 JOIN 和 范围查询，Innodb 中MRR的工作方式为：

将通过辅助索引查询到的数据放到一个缓存中，此时这些数据是按照辅助索引键值排序的；

将缓存中的数据按照主键顺序排序；

根据主键顺序访问实际数据文件；

可以想象，当缓冲池不够大的时候进行大范围数据的查询，那么会频繁出现数据页被从LRU列表剔除的情况。如果被查询的辅助索引不是按主键排序的，可能会多次发生如下的情况：一个页在同一次查询中被剔出LRU列表后又再次被加载出来。

配置项：read_rnd_buffer_size 用来配置上述描述的键值缓冲区大小，默认为256K；当发生溢出时，执行器只对已经缓存的数据进行排序。

3).对于范围查询：MMR还支持对键值的拆分，将范围查询拆分为键值对进行批量的数据查询.
[mw_shl_code=applescript,true]create table t (
        a integer,
        b integer,
        primary key (a),
        key idx_ab (a, b)
)engine=innodb;
[/mw_shl_code]
[mw_shl_code=applescript,true]select * from t where a = 50  and  b>= 100 and  b<= 20000
[/mw_shl_code]
由于存在辅助索引 idx_ab，上述sql语句的条件可以拆分为键值对集合：{( 50 , 100 ),( 50 , 101 ),......,( 50 , 20000 )}，这样就将范围查询优化为对键值对的查询；否则会进行范围查询，将 b ∈ {100，20000} 的所有数据都取出。

Multi-Range Read 是否启用，由如下参数中的，mrr 和 mrr_cost_based 标记进行控制，mrr标记是 MRR优化的开关。若前者设置为on，后者设置为off表示当满足条件时总是使用MRR优化；若前者设置为 on，后者也设置 on 表示通过 cost base 方式判断是否需要 MRR优化。

6、Index Condition Pushdown 优化 （ICP）
ICP优化也从MySQL 5.6 开始支持，它是一种根据索引进行查询的优化方式，它支持对：range、ref、eq_ref、ref_or_null 类型的查询进行优化。

禁用ICP时，存储引擎层会通过遍历索引，定位完整的行记录；然后返回给数据库层，再去为这些数据行进行where条件的过滤。

启用ICP时，如果where条件可以使用索引，MySQL会把这部分过滤操作放到存储引擎层，存储引擎通过索引过滤，把满足where 条件的数据取出整行数据并返回。 ICP可以减少存储引擎层访问行记录的次数以及Server层必须访问存储引擎的次数。

【使用这个过滤的前提是：该过滤条件需要是，该索引可以覆盖到的范围】

Index Condition Pushdown工作原理如下：

1)不使用ICP时

（1）当存储引擎读取下一行时，从叶子节点读到相关的行记录<聚集索引的引用书签>，然后使用书签引用查询完整的行记录。

（2） 数据库层对完整的行记录进行where条件过滤，如果该行数据满足where条件则使用，否则丢弃。

（3）执行第1步，直到最后一行数据。

2）使用ICP时，如何进行索引扫描

（1）存储引擎从索引中读取下一条记录。

（2）存储引擎从索引读取数据，根据索引的key使用where条件过滤，如果不满足条件，存储引擎将会处理下一条数据（回到上一步）。只有满足下推的索引条件的时候，才会继续去叶子节点中读取数据。

（3）最后存储引擎层会将所有满足被索引覆盖到的条件，的数据返回数据库层。

（4）数据库层再继续使用，没有被索引覆盖到的where 条件进行过滤。

关于ICP优化，部分内容参考了下文：https://blog.csdn.net/wanbin6470398/article/details/82351161