MySQL -- 06 -- MySQL索引优化
一、运用二叉查找树
-
二叉查找树 (Binary Search Tree)，又称二叉排序树 (Binary Sort Tree)，亦称二叉搜索树，是数据结构中的一类，在一般情况下，查询效率要比链表结构要高
-
二叉查找树定义
-
1、二叉查找树的每个节点最多有两个子树，称为左子树和右子树
-
2、若左子树不为空，则左子树上所有节点的值均小于它的根节点的值
-
3、若右子树不为空，则右子树上所有节点的值均大于它的根节点的值
-
-
二叉查找树使用二分法进行查找，因为是对半搜索，所以其时间复杂度为 O(logn)，因此其查询效率是非常高的
-
当数据发生变动的时候，例如：将上图中的 2 和 6 两个数据进行删除，同时新增 11 和 13 两个数据，此时二叉查找树就会演变成一个线性的二叉树，其时间复杂度为 O(n)，大大降低了查询效率
-
二叉查找树缺点
-
假设所有的索引块都在磁盘中，当我们要查询一个数据时，会去检索树，检索深度每增加 1，就会发生一次 IO
-
无论是二叉查找树、平衡二叉树还是红黑树，每个节点最多只有两个子节点，而磁盘上的数据块会非常多，因此为了组织起这些数据块，树的深度会非常深，IO 的次数也会很非常多
-
这样数据一多，其检索性能会比全表扫描还要低，无法满足优化查询的需求
-
二、运用 B 树
-
B 树 (B - tree)，又称平衡多路查找树
-
B 树定义
-
1、根节点至少包含两个子节点
-
2、树中每个节点最多含有 m 个子节点 (m >= 2)
-
这就是我们平常所说的 m 阶树的含义了
-
m 取决于节点的容量以及相关配置
-
-
3、除根节点和叶节点外，其他每个节点至少有 ceil(m / 2) 个子节点
- ceil() 函数表示取值的上限，如：m 为 3，那么 ceil(3 / 2) 得 2
-
4、所有叶子节点都位于同一层，即叶子节点的高度都是一样的
-
5、假设每个非终端节点中包含 n 个关键字信息，其中
-
a) K[i] (i = 1, 2, 3 … n) 为关键字，且关键字按顺序升序排序，即 K[i - 1] < K[i]
-
b) 关键字的个数 n 必须满足：ceil(m / 2) - 1 <= n <= m - 1
-
c) 非叶子节点的指针：P[1], P[2], P[3] … P[M]：其中 P[1] 指向关键字小于 K[1] 的子树；P[M] 指向关键字大于 K[M - 1] 的子树；其他 P[i] 指向关键字位于 (K[i - 1], K[i]) 区域之间的子树
-
-
-
三阶 B 树示意图
-
这里我们重点看下定义中的第 5 点
-
第 a 条，K[i] (i = 1, 2, 3 … n) 为关键字，且关键字按顺序升序排序，即 K[i - 1] < K[i]
-
第 b 条，关键字的个数 n 必须满足：ceil(m / 2) - 1 <= n <= m - 1
-
第 c 条，非叶子节点的指针：P[1], P[2], P[3] … P[M]：其中 P[1] 指向关键字小于 K[1] 的子树；P[M] 指向关键字大于 K[M - 1] 的子树；其他 P[i] 指向关键字位于 (K[i - 1], K[i]) 区域之间的子树
-
-
-
当数据发生变动的时候，现有结构会被打乱，则有可能会出现像二叉查找树一样线性的情况，而 B 树由于相关定义的存在，会存在相应的策略，通过合并、分裂、上移、下移节点，来保持 B 树的特征，使树远比二叉查找树矮的多，并且不会存在经过数据不断变动后变成线性的情况
三、运用 B+ 树
-
B+ 树 (B+ - tree)，是 B 树的变体，其定义基本与 B 树相同，除了以下几点
-
1、非叶子节点的子树指针与关键字个数相同
-
2、非叶子节点的子树指针 P[i]，指向关键字值 [K[i], K[i + 1]) 的子树
-
3、非叶子节点仅用于索引，数据都保存在叶子节点中
-
4、所有叶子节点均有一个链指针指向下一个叶子节点，并按大小顺序进行链接
-
-
三阶 B+ 树示意图
-
这里我们来看看这几条定义
-
第 1 条，非叶子节点的子树指针与关键字个数相同
-
第 2 条，非叶子节点的子树指针 P[i]，指向关键字值 [K[i], K[i + 1]) 的子树
-
第 3 条，非叶子节点仅用于索引，数据都保存在叶子节点中
-
第 4 条，所有叶子节点均有一个链指针指向下一个叶子节点，并按大小顺序进行链接
-
-
-
因此，B+ 树相对于 B 树来说，更适合来做存储索引，原因如下
-
B+ 树的磁盘读写代价更低
- 内部节点并不是最终指向文件内容的节点，而是叶子节点中关键字的索引，因此其内部节点相对于 B 树来说更少，但存储的关键字更多，一次性加载进内存的关键字也就越多，相对来说 IO 次数就降低了
-
B+ 树的查询效率更加稳定
- 内部节点并不是最终指向文件内容的节点，而是叶子节点中关键字的索引，所以任何关键字的查找，必须走一条从根节点到叶子节点的路，所有关键字查询的长度相同，导致每个数据的查询效率也几乎是相同的，为 O(logn)
-
B+ 树更有利于对数据库的扫描
- B 树在提高磁盘 IO 性能的同时，并没有解决元素遍历效率低下的问题；而 B+ 树只需要遍历叶子节点，就可以对全部关键字进行扫描，所以对于数据库中频繁使用的范围查询，B+ 树有着更高的性能
-
四、运用 Hash 索引
-
有些数据库存储引擎还支持 Hash 索引
-
理论上，Hash 索引的效率要高于 B+ 树，但是任何事物都是有两面性的，Hash 索引也存在很多缺点
-
只能满足 “=”、“IN” 等查询，不能使用范围查询
- 因为经过 Hash 算法处理后的 Hash 值，其大小关系并不能保证和 Hash 运算前键值的大小关系完全一致
-
无法被用于避免数据的排序操作
-
因为经过 Hash 算法处理后的 Hash 值，其大小关系并不能保证和 Hash 运算前键值的大小关系完全一致
-
也就是说通过 Hash 索引查询出来的数据不具备大小顺序，需要对查询出来的数据进行排序
-
-
不能利用部分索引键进行查询
-
对于组合索引，Hash 索引在计算 Hash 值时，是对组合的索引键进行计算的，而不是对单个索引键进行计算
-
因此通过组合索引的前面一个或几个索引键进行查询时，Hash 索引无法被利用，而 B+ 树是支持利用组合索引中的部分索引的
-
-
不能避免表扫描
- Hash 索引是将索引键通过 Hash 运算之后，将得到的 Hash 值和对应的行指针信息存放在一个 bucket 中，由于不同的索引键可能会存在相同的 Hash 值 (即 Hash 冲突)，因此无法直接通过 Hash 索引完成查询，需要对指定 bucket 中的数据进行比较
-
遇到大量 Hash 值相同的情况下，Hash 索引的性能并不一定会比 B+ 树索引高
- 在极端情况下，所有索引键计算得到的 Hash 值都相等，即每个索引键的 Hash 值和对应的行指针信息都位于同一个 bucket 中，此时就演变成了一个线性结构，当我们要查询最后一条数据时，其时间复杂度会变为 O(n)，大大降低了查询效率
-
-
在 MySQL 中，InnoDB 存储引擎将哈希索引用于其自适应哈希索引 (adaptive hash index) 功能，即当 InnoDB 注意到某些索引值被使用的非常频繁时，它会在内存中基于 B-Tree 索引之上再创建一个哈希索引，这样就让 B-Tree 索引也具有了哈希索引的一些优点，比如：快速的 Hash 查找；这是一个完全自动的、内部的行为，不能人为干预是否在一张表中生成哈希索引
五、归纳总结
-
为什么 B+ 数相比较 B 数更适合做数据库索引？
-
B+ 树的磁盘读写代价更低
- 内部节点并不是最终指向文件内容的节点，而是叶子节点中关键字的索引，因此其内部节点相对于 B 树来说更少，但存储的关键字更多，一次性加载进内存的关键字也就越多，相对来说 IO 次数就降低了
-
B+ 树的查询效率更加稳定
- 内部节点并不是最终指向文件内容的节点，而是叶子节点中关键字的索引，所以任何关键字的查找，必须走一条从根节点到叶子节点的路，所有关键字查询的长度相同，导致每个数据的查询效率也几乎是相同的，为 O(logn)
-
B+ 树更有利于对数据库的扫描
- B 树在提高磁盘 IO 性能的同时，并没有解决元素遍历效率低下的问题；而 B+ 树只需要遍历叶子节点，就可以对全部关键字进行扫描，所以对于数据库中频繁使用的范围查询，B+ 树有着更高的性能
-
-
Hash 索引缺点
-
只能满足 “=”、“IN” 等查询，不能使用范围查询
- 因为经过 Hash 算法处理后的 Hash 值，其大小关系并不能保证和 Hash 运算前键值的大小关系完全一致
-
无法被用于避免数据的排序操作
-
因为经过 Hash 算法处理后的 Hash 值，其大小关系并不能保证和 Hash 运算前键值的大小关系完全一致
-
也就是说通过 Hash 索引查询出来的数据不具备大小顺序，需要对查询出来的数据进行排序
-
-
不能利用部分索引键进行查询
-
对于组合索引，Hash 索引在计算 Hash 值时，是对组合的索引键进行计算的，而不是对单个索引键进行计算
-
因此通过组合索引的前面一个或几个索引键进行查询时，Hash 索引无法被利用，而 B+ 树是支持利用组合索引中的部分索引的
-
-
不能避免表扫描
- Hash 索引是将索引键通过 Hash 运算之后，将得到的 Hash 值和对应的行指针信息存放在一个 bucket 中，由于不同的索引键可能会存在相同的 Hash 值 (即 Hash 冲突)，因此无法直接通过 Hash 索引完成查询，需要对指定 bucket 中的数据进行比较
-
遇到大量 Hash 值相同的情况下，Hash 索引的性能并不一定会比 B+ 树索引高
-
-
自适应哈希索引
-
InnoDB 支持自适应哈希索引，即当 InnoDB 注意到某些索引值被使用的非常频繁时，它会在内存中基于 B-Tree 索引之上再创建一个哈希索引，这样就让 B-Tree 索引也具有了哈希索引的一些优点，比如：快速的 Hash 查找
-
这是一个完全自动的、内部的行为，不能人为干预是否在一张表中生成哈希索引
-