MySQL高级（四）

四、索引的数据结构

1. 索引及其优缺点

1.1 索引概述

索引（Index）是帮助MySQL高效获取数据的数据结构。

索引的本质：索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”，满足特定查找算法。这些数据结构以某种方式指向数据， 这样就可以在这些数据结构的基础上实现 高级查找算法 。

1.2 优点

• 降低 数据库的IO成本
• 保证数据库表中每一行 数据的唯一性
• 加速表和表之间的连接，对于有依赖关系的子表和父表联合查询时，可以提高查询速度
• 减少查询中分组和排序的时间 ，降低了CPU的消耗

1.3 缺点

• 创建索引和维护索引要 耗费时间 ，并且随着数据量的增加，所耗费的时间也会增加
• 索引需要占 磁盘空间
• 降低更新表的速度，对表中的数据进行增加、删除和修改的时候，索引也要动态地维护

2. InnoDB中索引的推演

2.1 数据存储示意图

下表为采用Compact行格式存储的简化示意图

在存储引擎中的简化示意图为

• record_type ：记录头信息的一项属性，表示记录的类型， 0 表示普通记录、1 表示目录项记录、 2 表示最小记录、 3 表示最大记录
• next_record ：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量
• 各个列的值：真正的记录值
• 其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息

2.2 InnoDB索引的设计

• 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值
• 给所有的页建立一个目录项，组成的目录即为索引
• 相同点：两者用的是一样的数据页，都会为主键值生成 Page Directory （页目录），从而在按照主键值进行查找时可以使用 二分法 来加快查询速度。
• 假如页31为新增的用户记录，此时页30容量已满则需要一个新的 页32 来存放 页31 对应的目录项
• 了解：记录头信息里还有一个叫 min_rec_mask 的属性，只有在存储 目录项记录 的页中的主键值 最小的目录项记录 的 min_rec_mask 值为 1 ，其他别的记录的 min_rec_mask 值都是 0

2.3 B+Tree

假设所有存放用户记录的叶子节点代表的数据页可以存放 100条用户记录 ，所有存放目录项记录的内节点代表的数据页可以存放 1000条目录项记录 ，那么：

• 如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放 100 条记录。
• 如果B+树有2层，最多能存放 1000×100=10,0000 条记录。
• 如果B+树有3层，最多能存放 1000×1000×100=1,0000,0000 条记录
• 。。。

2.4 聚簇索引

**特点：**B+树的 叶子节点 存储的是完整的用户记录。

优点：数据访问更快、对于主键的 排序查找 和 范围查找 速度非常快、节省了大量的io操作

缺点：

• 插入速度严重依赖于插入顺序 ，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键
• 更新主键的代价很高 ，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新

2.5 二级索引（辅助索引，非聚簇索引）

二级索引记录的是字段和主键，所以››需要回表

回表： 我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值，所以如果我们想根据c2列的值查找到完整的用户记录的话，仍然需要到 聚簇索引 中再查一遍，这个过程称为 回表 。也就是根据c2列的值查询一条完整的用户记录需要使用到 2 棵B+树

2.6 联合索引

让B+树按照 c2和c3列 的大小进行排序，为c2和c3列分别建立索引会分别以c2和c3列的大小为排序规则建立2棵B+树

2.7 InnoDB的B+树索引的注意事项

1. 根页面位置万年不动

   当根节点中的可用 空间用完时 继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页，比如页a中，然后对这个新页进行 页分裂 的操作，得到另一个新页，比如 页b。这时新插入的记录根据键值（也就是聚筷索引中的主键值，二级索引中对应的索引列的值）的大小就会被分配到 页a 或者 页b 中，而根节点便升级为存储目录项记录的页。

   凡是 InnoDB 存储引擎需要用到索引的时候，会从固定的地方取出根节点的页号，从而来访问这个索引。

2. 内节点中目录项记录的唯一性

3. 一个页面最少存储2条记录

3. MyISAM中的索引

MyISAM引擎使用 B+Tree 作为索引结构，叶子节点的data域存放的是 数据记录的地址。

3.1 MyISAM索引的原理

如果我们在Col2上建立一个二级索引，则此索引的结构如下图所示：

3.2 MyISAM与InnoDB对比

MyISAM的索引方式都是“非聚簇”的，与InnoDB包含1个聚簇索引是不同的。小结两种引擎中索引的区别：

1. 在InnoDB存储引擎中，我们只需要根据主键值对 聚簇索引 进行一次查找就能找到对应的记录，而在 MyISAM 中却需要进行一次 回表 操作，意味着MyISAM中建立的索引相当于全部都是 二级索引。
2. InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是 分离的 ，索引文件仅保存数据记录的地址。
3. InnoDB的非聚簇索引data域存储相应记录 主键的值 ，而MyISAM索引记录的是 地址 。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。
4. MyISAM的回表操作是十分 快速 的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。

4. 索引的代价

• 空间上的代价

  每建立一个索引都要为它建立一棵B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会占用 16KB 的存储空间，一棵很大的B+树由许多数据页组成，那就是很大的一片存储空间。

• 时间上的代价

  每次对表中的数据进行 增、删、改 操作时，都需要去修改各个B+树索引。而且我们讲过，B+树每层节点都是按照索引列的值 从小到大的顺序排序 而组成了 双向链表 。不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需 要额外的时间进行一些记录移位 ， 页面分裂 、 页面回收 等操作来维护好节点和记录的排序。如果我们建了许多索引，每个索引对应的B+树都要进行相关的维护操作，会给性能拖后腿。

5. MySQL数据结构选择的合理性

5.1 全表遍历

5.2 Hash结构

Hash结构效率高，那为什么索引结构要设计成树型呢？

原因1：Hash 索引仅能满足(=)(<>)和 IN 查询。如果进行范围查询，哈希型的索引，时间复杂度会退化为O(n)；而树型的“有序”特性，依然能够多保持O(log2N)的高效率。
原因2：Hash 索引还有一个缺陷，数据的存储是 没有顺序的，在ORDER BY 的情况下，使用Hash 索引还需要对数据重新排序。
原因3：对于联合索引的情况，Hash 值是将联合索引键合并后一起来计算的，无法对单独的一个键或者几个索引键进行查询。
原因4：对于等值查询来说，通常 Hash 索引1的效率更高，不过也存在一种情况，就是 索引列的重复值如果很多，效率就会降低。这是因为遇到 Hash 冲突时，需要遍历桶中的链表行指针来进行比较，找到查询的关键字，非常耗时。所以，Hash 索引通常不会用到重复值多的列上，比如列为性别、年龄的情况等。

InnoDB的自适应Hash索引

当查询到数据页后会把数据页相关信息存储的 自适应 Hash，通过 innodb_adaptive_hash_index 变量来查看是否开启了自适应 Hash

6.3 二叉搜索树

极端情况：

为了提高查询效率，就需要 减少磁盘IO数 。为了减少磁盘IO的次数，就需要尽量 降低树的高度 ，需要把原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好。

6.4 AVL树（平行二叉搜索树）

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

常见的平衡二叉树有很多种，包括了 平衡二叉搜索树、红黑树、数堆、伸展树。

6.5 B-Tree

一个 M阶(每个节点最多包含的子节点数) 的 B 树（M>2）有以下的特性：

1. 根节点的儿子数的范围是 [2,M]。
2. 每个中间节点包含 k-1 个关键字（判断的边界）和 k 个孩子，孩子的数量 = 关键字的数量 +1，k 的取值范围为 [ceil(M/2), M]。
3. 叶子节点包括 k-1 个关键字（叶子节点没有孩子），k 的取值范围为 [ceil(M/2), M]。
4. 假设中间节点节点的关键字为：Key[1], Key[2], …, Key[k-1]，且关键字按照升序排序，即 Key[i]<Key[i+1]。此时 k-1 个关键字相当于划分了 k 个范围，也就是对应着 k 个指针，即为：P[1], P[2], …,P[k]，其中 P[1] 指向关键字小于 Key[1] 的子树，P[i] 指向关键字属于 (Key[i-1], Key[i]) 的子树，P[k]指向关键字大于 Key[k-1] 的子树。
5. 所有叶子节点位于同一层。

6.6 B+Tree

B+ 树和 B 树的差异：

1. 有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数+1。
2. 非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）。
3. 非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中， 非叶子节点既保存索引，也保存数据记录 。
4. 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。

6.7 R树

R-Tree在MySQL很少使用，仅支持 geometry数据类型 ，支持该类型的存储引擎只有myisam、bdb、 innodb、ndb、archive几种。举个R树在现实领域中能够解决的例子：查找20英里以内所有的餐厅。如果 没有R树你会怎么解决？一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中，一个字段记 录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满 足要求。如果一个地区有100家餐厅的话，我们就要进行100次位置计算操作了，如果应用到谷歌、百度地图这种超大数据库中，这种方法便必定不可行了。R树就很好的 解决了这种高维空间搜索问题 。它把B 树的思想很好的扩展到了多维空间，采用了B树分割空间的思想，并在添加、删除操作时采用合并、分解 结点的方法，保证树的平衡性。因此，R树就是一棵用来 存储高维数据的平衡树 。相对于B-Tree，R-Tree 的优势在于范围查找。

附录：算法的时间复杂度