MySQL优化
创建高性能索引
索引基础知识
何为索引？
索引，在MySQL中也叫作键（key），是存储引擎用于快速找到记录的一种数据结构。要想获得好的性能，索引至关重要！索引优化是对查询性能优化最有效的手段，索引能够轻易将查询性能提升几个数量级。
索引有哪些类型？
在MySQL中，索引在存储引擎层实现。索引有很多种类型，可以为不同场景提供更好的性能。
- 从数据结构角度：
B-Tree索引、Hash索引、R-Tree索引、Full-Text索引 - 物理存储角度：
聚集索引、非聚集索引 - 从逻辑角度：
主键索引、唯一索引、普通索引、组合索引、覆盖索引
深入探索B+Tree索引
B+Tree 基本知识
- B+ 树是 B 树 的一个升级，它比 B 树更适合操作系统的文件索引和数据库索引。
- B+ 树是一种多叉排序树，即每个节点通常有多个孩子。一棵 B+ 树包含根节点、内部节点和叶子节点。
- B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。
首先介绍一棵 m 阶 B+ 树的特性。m 表示这个树的每一个节点最多可以拥有的子节点个数。一棵 m 阶的 B+ 树和 B 树的差异在于：
- 有 n 棵子树的节点中含有
n-1个关键字（即将区间分为n个子区间，每个子区间对应一棵子树）。 - 所有叶子节点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。
- 所有的非叶子节点可以看成是索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字。
- 除根节点外，其他所有节点中所含关键字的个数最少有（
m/2）（向上取整）个 - B+ 树为了方便范围查询，叶子节点之间还用指针串联起来。MySQL在此基础上使用的是双向链表。
以下是一棵 B+ 树的典型结构：
B+Tree 相较于 B-Tree 的优势：
- 由于索引节点上只有索引而没有数据，所以索引节点上能存储比 B 树更多的索引，这样树的高度就会更矮，磁盘寻道的次数更少。
- 数据都集中在叶子节点，而所有叶子节点的高度相同，那么可以在叶子节点中增加前后指针，指向同一个父节点的相邻兄弟节点，这样可以更好地支持查询一个值的前驱或后继，使连续访问更容易实现，更好的利用到程序的局部性原理（空间局部）。
查询
B+ 树的查找过程和 B 树类似。假设需要查找的键值是 k，那么从根节点开始，从上到下递归地遍历树。在每一层上，搜索的范围被减小到包含搜索值的子树中。
一个实例：在如下这棵 B+ 树上查找 45。
- 先和根节点比较，因为根节点的键值比 45 要小，所以去往根节点的右子树查找。
- 因为 45 比 35 大，所以要与右边的索引比较。右侧的索引也为 45，所以要去往该节点的右子树继续查找，然后就可以找到 45。
需要注意的是，在查找时，若非叶子节点上的关键字等于给定值，并不终止，而是继续向下直到叶子节点。因此，在 B+ 树中，不管查找成功与否，每次查找都是走了一条从根到叶子节点的路径。其余同 B 树的查找类似。
遍历
B+Tree叶子节点之间使用指针串联，那么在叶子节点的层级上就可以实现整棵树的遍历。从根节点出发一路搜索到最左端的叶子节点之后即可根据指针遍历。
插入
- 若为空树，创建一个叶子节点，然后将记录插入其中，此时这个叶子节点也是根节点，插入操作结束。
- 针对叶子类型节点：根据关键字找到叶子节点，向这个叶子节点插入记录。插入后，若当前节点关键字的个数小于 m，则插入结束。否则将这个叶子节点分裂成左右两个叶子节点，左叶子节点包含前 m/2 个记录，右节点包含剩下的记录，将第 m/2+1 个记录的关键字进位到父节点中（父节点一定是索引类型节点），进位到父节点的关键字左孩子指针向左节点，右孩子指针向右节点。将当前节点的指针指向父节点，然后执行第 3 步。
- 针对索引类型节点（内部节点）：若当前节点关键字的个数小于等于 m-1，则插入结束。否则，将这个索引类型节点分裂成两个索引节点，左索引节点包含前 (m-1)/2 个 key，右节点包含 m-(m-1)/2 个 key，将第 m/2 个关键字进位到父节点中，进位到父节点的关键字左孩子指向左节点，进位到父节点的关键字右孩子指向右节点。将当前节点的指针指向父节点，然后重复这一步。
比如在下图的 B+ 树中，插入新的数据 10：
由于插入节点[7,11]在插入之后并没有溢出，所以可以直接变成 [7,10,11]。
而如下图的 B+ 树中，插入数据 4:
由于所在节点 [2,3,5] 在插入之后数据溢出，因此需要分裂为两个新的节点，同时调整父节点的索引数据：
[2,3,4,5] 分裂成了 [2,3] 和 [4,5]，因此需要在这两个节点之间新增一个索引值，这个值应该满足：
- 大于左子树的最大值；
- 小于等于右子树的最小值。
综上，需要在父节点中新增索引 4 和两个指向新节点的指针。如果父节点也发生了数据溢出，那么父节点也需要进行分裂，可以看出B+Tree的插入是自底向上进行。
删除
具体步骤如下：
- 首先查询到键值所在的叶子节点，删除该叶子节点的数据。
- 如果删除叶子节点之后的数据数量，满足 B+ 树的平衡条件，则直接返回。
- 否则，就需要做平衡操作：如果该叶子节点的左右兄弟节点的数据量可以借用，就借用过来满足平衡条件。否则，就与相邻的兄弟节点合并成一个新的子节点了。
- 在上面平衡操作中，如果是进行了合并操作，就需要向上修正父节点的指针：删除被合并节点的键值以及指针。
- 由于做了删除操作，可能父节点也会不平衡，那么就按照前面的步骤也对父节点进行重新平衡操作，这样一直到某个节点平衡为止。