前言
在上篇博文：构建优化之城：MySQL 数据建模、数据类型优化与索引常识全面解析 提到了数据建模方案及数据类型的优化方案，简要说明了一些索引的基本知识及分类、技术名词，该篇博文会从以下几点来对 MySQL 调优部分进行分析：
- 索引数据结构、优化细节
- 大数据量查询优化
- 海量数据解耦优化处理
数据结构
InnoDB、MyISAM 存储引擎底层索引使用的 B+ Tree，Memory 存储引擎使用的 hash
推荐一个数据结构可视化网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
HASH
hash 表存在于就是一个数组，然后在每一个数组下可以添加一个数据桶，以链表的方式进行实现。hash 表有对应的下标值，从 0 开始进行排列，若想要往 hash 表里放数据的话，必须要经过散列算法，然后计算出对应的位置，将数据放入到指定的位置中，而散列算法最简单的实现就是取模运算
hash 表方式看起来虽然很好，能够通过对应的下标位置定位到某一条记录，但是需要注意 hash 表同样也有明显的缺点
会占用大量的内存空间，在每次使用 hash 表时需要将大量的数据加载到内存中，此时是非常浪费内存空间的，所以在 MySQL Memory 存储引擎中使用 hash 索引，像 InnoDB 这种存储引擎支持自适应 hash，但它是由 MySQL 自主控制的- 在进行数据查询时都是等值查询，首先通过 Key 计算出 hash 值，然后定位到某一个位置，进行 Key 比较，但是大部分公司用的都是基于范围查询，而 hash 表在进行范围查询时必须挨个匹配，这样查询会比较浪费时间，所以不太合适。最终可以得出结论：
若每次查询都是等值查询，那么 hash 表方式查询是是比较快的，若是基于范围查询，hash 方式查询是比较慢的 - 使用 hash 表存储数据时，需要设计比较优秀的 hash 算法，若算法设计不合理的话，会导致数据散列不均匀，浪费比较多的存储空间，同时在数据查询时会导致查询效率较低
基于以上缺点，在 MySQL InnoDB、MyISAM 存储引擎并没有使用 hash 表来存储数据，而 Memory 存储引擎使用了 hash 表这样的方式，注意索引的数据结构选择与存储引擎是息息相关的
Binary Search Trees、AVL Trees
基于二叉树会产生一条腿长一条腿短，这样的话很明显会编程挨个对比的过程，而当插入的数据越来越多时，会导致链表越长，这样的效率一定是比较低的，大于根节点值往右边塞 < 小于根节点值往左边塞 >
造成上述问题，最关键的原因：树的左右分支不够平衡，因此后续才有了二叉平衡树，即 AVL 树，如下图：
AVL 树要求左子树、右子树之间的高度之差不能超过 1，因此在进行数据插入时会造成 N 个旋转操作来保持树的平衡，所以在进行数据插入时效率比较低，查询的效率会比较快，这样的话可以理解为损失部分性能来满足查询性能的提升，但会引起插入、删除需求比较多时，如何解决呢？插入数据的越来越多，会造成树越来越深，从而会造成查询效率降低
Red/Black Trees
红黑树也基于二叉平衡树，只不过不是严格意义上的平衡树；在 AVL 树中，要求左右子树的高度之差不能超过 1，但红黑树的要求是最长子树只要不超过最短子树的两倍路径长度就好，如下图：
通过以上的分析，可以得出一个结论：无论是那种类型的二叉树，最终都会存在一个问题，随着数据量的增加，树的层数就会增加，那么就会造成 IO 次数越多，从而影响数据读取的效率
B Trees
B 树的数据结构特点如下：
- 所有键值分布在整棵树中
- 搜索有可能在非叶子节点结束（有可能在度为 0 或度为 1 的节点结束）在关键字全局内作一次查找，性能逼近于
二分查找 - 每个节点最多拥有 M 个子树，根节点至少有 2 个子树
- 分支节点至少拥有 M/2 颗子树（除根节点、叶子节点都是分支节点）
- 所有叶子节点都在同一层，每个叶子节点最多有 M-1 Key，并且以升序排列
在 MySQL 使用 B 树结构进行数据存储时，如下图：
每一个树节点都占用一个磁盘块，一个节点上有两个升序排序的关键词(如：16、34)以及三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词（16、34）划分成三个范围域对应三个指针所指向的子树数据范围域，以根节点 16、34 为例子，P1 指针指向的子树数据范围小于 16，P2 指针指向的子树数据范围为 16～34，P3 指针指向的子树数据范围大于 34
比如，要找出关键词等于 28，查找关键词过程如下：
- 通过根节点找到磁盘块 1，读入内存【磁盘 I/O 操纵第一次】
- 比较关键字 28 在区间（16～34）找到磁盘块 1 中的 P2 指针
- 通过 P2 指针找到磁盘块 3，读入内存【磁盘 I/O 操纵第二次】
- 比较关键字 28 在区间（25～31）找到磁盘块 3 中的 P2 指针
- 通过 P2 指针找到磁盘块 8，读入内存【磁盘 I/O 操纵第三次】
- 在磁盘块 8 中的关键词列表，找到关键字 28
B 树作为存储索引的数据结构，缺点如下：
- 每个节点都有 Key，同时也包含了 data，但每个页的存储空间是有限的，若 data 比较大的话会导致每个节点存储的 Key 数量变小
- 当存储数据量很大时会导致深度越大，同时就会增大查询时的
磁盘 IO 次数，进而影响了查询性能 - InnoDB 存储引擎，默认情况下读取的是 16 KB，一共会读取三个磁盘块，意味着一共读取了 48 KB 数据，假设说上面这些 P 指针、节点 Key 都不需要占用额外的存储空间，一条数据占用 1 KB，那意味着当前节点里面最多存储 16 条数据，下一个磁盘块也是 16 条，第三个磁盘块也是 16 条，最终的总数也就是 4096 条，故而这个支撑的数据量太少了！
B+ Trees
B+ 树是在 B 树基础之上作的一种优化，如下：
- B+ 树每个节点可以包含更多的节点，这样做的原因是：为了降低树的高度、将数据范围变为多个区间，区间越多，数据检索越快
- 非叶子节点存储 Key，叶子节点存储 Key、数据
- 叶子节点之间通过指针相互连接在一起（符合磁盘的预读特性）顺序查询性能更高
在 B+ 树有两个头指针：一个指向根节点，另一个指向关键词最小的叶子节点，但所有叶子节点（数据节点）之间是一种链式环结构；因此可以对 B+ Tree 进行两种查找运算：
- 对于主键的范围查询、分页查询
- 从根节点开始，进行随机查找
叶子节点负责存储数据，非叶子节点不存储数据，能保证尽可能多的存储数据，查找数据的方式不变，可以进行计算一下三层的 B+ 树能存储多少数据
读取数据仍然是 16 KB，假设：P 指针、节点 Key 占用 10 字节，那么 16 KB = 16*1000/10，结果为 1600，第二层也是 1600，第三层还是 1600，最终的结果：40960000，可达到千万级别，而刚刚 B 树为 4096，完全不是量级的数据
数据存储
在上述中，是对 MySQL 索引结构的统一描述，但对于不同的存储引擎来说，虽然使用的都是基于 B+ Tree 数据结构，但在实际存储数据时是完全不一样的
InnoDB
在 InnoDB 存储引擎中，数据、索引是放在一起的，因此你看到的只有 idb 文件，其中既能存储实际的数据，又可以存储索引数据，因此当查询索引时，能够直接从叶子节点中获取需要的数据行，如下图：
[root@trench study]# cat /etc/my.cnf # 找到 datadir 配置所在的文件目录 [root@trench study]# pwd /var/lib/mysql/study [root@trench study]# ll total 1152 # 表结构文件 -rw-r----- 1 mysql mysql 8586 May 16 22:22 course.frm -rw-r----- 1 mysql mysql 98304 May 16 22:24 course.ibd
InnoDB 通过 B+ Trees 结构对主键创建索引，然后在叶子节点中存储记录，若没有主键，那么就选择唯一键，后台就会生成一个 6 字节的 row_id 作为主键
若创建索引的键是其他字段，那么叶子节点存储的是该记录的主键，然后再通过主键索引找到对应的记录，这叫做回表
MyISAM
在 MyISAM 存储引擎中，数据文件、索引文件是分开存储的，所以能看到两个文件，后缀分别是：MYI、MYD，因此在进行数据检索时，需要读取两个文件，在索引的数据结构中存储的是实际的数据行地址，如下图：
[root@trench study]# pwd /var/lib/mysql/study [root@trench study]# ll total 1064 # 表结构文件 -rw-r----- 1 mysql mysql 8586 May 16 22:36 course.frm -rw-r----- 1 mysql mysql 120 May 16 22:36 course.MYD -rw-r----- 1 mysql mysql 2048 May 16 22:36 course.MYI
索引优化
上一篇讲到了索引的基本概念、索引的分类以及索引相关的技术名词
在 MySQL 官网中，给了数据库、表案例 > sakila 数据库，如下：https://dev.mysql.com/doc/index-other.html，后续会基于该数据库表进行索引优化演示
