深入理解 MySQL 索引
那索引为啥要用 B+Tree 的数据结构呢？
====================
如果我们简单地想的话，想要快速地查找到数据，感觉 hash 表是最快的，根据 key，hash 到某个槽位上，直接一次查找就可以准确的找到数据的位置，这多快呀。但是我们在做业务时，往往只需要一条的数据需求很少，大部分的需求都是根据一定的条件查询一部分的数据，这个时候 hash 显示不是很合适。
我们再考虑树，比如二叉树，平衡二叉树，红黑树，B 树等，他们都是二
分查找，找数也快，但是不管是平衡二叉树还是优化后的红黑树，说到底他们都是二叉树，当节点多了的时候，它们的高度就会高呀，我找一个数据。根节点不是，那就找下一层，下一层还没有我就再去找下一层，这样造成的后果就是我找一个数据可能要找好几次，而每一次都是执行了一次磁盘的 io，而我们的索引的目的就是要减少磁盘 io 呀，这样设计可不行。那我们是不是把高度变矮就可以了呢？
所以我们再考虑下 B 树。首先简单介绍下 B 树的数据结构：
B 树的定义：
======
每个节点最多有 m-1 个关键字（可以存有的键值对）。
根节点最少可以只有 1 个关键字。
非根节点至少有 m/2 关键字。
每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
每个节点都存有索引和数据，也就是对应的 key 和 value。
所以，根节点的 关键字 数量范围： 1 <= k <= m-1 ，非根节点的 关键字 数量范围： m/2 <= k <= m-1 。
这里的 m 表示阶数，阶数表示了一个节点最多有多少个孩子节点，所以描述一颗 B 树时需要指定它的阶数。
我们再举个例子来说明一下上面的概念，比如这里有一个 5 阶的 B 树，根节点数量范围：1 <= k <= 4，非根节点数量范围：2 <= k <= 4。
下面，我们通过一个插入的例子，讲解一下 B 树的插入过程，接着，再讲解一下删除关键字的过程。
1.2 B 树插入
插入的时候，我们需要记住一个规则： 判断当前结点 key 的个数是否小于等于 m-1，如果满足，直接插入即可，如果不满足，将节点的中间的 key 将这个节点分为左右两部分，中间的节点放到父节点中即可。
例子：在 5 阶 B 树中，结点最多有 4 个 key,最少有 2 个 key（注意：下面的节点统一 用一个节点表示 key 和 value ）。
插入 18，70，50,40
插入 22
插入 22 时，发现这个节点的关键字已经大于 4 了，所以需要进行分裂，分裂的规则在上面已经讲了，分裂之后，如下。
评论