MySQL索引使用B+tree的原因
当你遇到慢SQL需要优化时，你能立即想到什么优化方法？
大多数人的第一反应可能是添加索引。大多数情况下，索引可以添加一条SQL语句的查询效率提高几个数量级。
索引的本质：用于快速查找记录的数据结构。
索引常用的数据结构：
二叉树红黑树哈希表B树（B树不叫B减树）B+tree图形数据结构网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
索引查询
大家都知道如果select * from t where col = 88这样一个SQL语句不使用索引进行搜索，正常搜索是全表扫描：从表的第一行开始逐行搜索，比较col<的值每行的 /code> 字段与 88 相比，这显然是非常低效的。
如果使用索引，查询过程完全不同（假设使用平衡二叉树数据结构来存储我们的索引列）
此时二叉树的存储结构（Key - Value）：Key是索引字段的数据，Value是索引所在行的磁盘文件地址。
当最终找到88时，就可以取出它的Value对应的磁盘文件地址，然后直接去磁盘中查找这一行数据。这时速度会比全表扫描快很多。
但是实际上 MySQL并没有使用二叉树在底层存储索引数据层，但使用 B+tree (B+tree) 。
为什么不使用二叉树
假设使用普通二叉树来记录id索引列。我们在插入一行记录时必须维护二叉树索引字段。 。
当我想查找id = 7的那条数据时，查找过程如下：
< /p>
此时id=7行被搜索了7次，这和我们的全表扫描没有太大区别。显然，二叉树实际上是不适合作为这种递增数据列的索引数据结构。
为什么不使用哈希表
哈希表：一种快速搜索的数据结构，搜索时间复杂y 为 O(1)
哈希函数：将任意类型的 key 转换为 int 类型下标
假设使用哈希表来记录id索引列，此时我们插入每记录一行的同时，哈希表索引字段也必须维护。
此时id=7的树节点只被搜索了1次，效率很高。
但是，MySQL 的索引仍然没有使用可以准确定位。因为它不适用于范围查询。
为什么不使用红黑树
红黑树是一种专门的AVL树（平衡二叉树），它使用特定的操作来维护树的平衡二叉搜索树；
如果二叉搜索树是红黑树，那么它的任何子树都必须是红黑树。
假设红黑树是用来记录id索引列的，我们在插入一行记录的同时，必须维护红黑树索引字段。
在插入过程中，你会发现它与普通二叉树的不同之处在于，当一棵树的左右子树的高度差>1时，将旋转操作来保持树平衡。
此时id=7的树节点只被搜索了3次，仍然比所谓的普通二叉树快。
但是MySQL的索引仍然没有使用精确度极佳的红黑树定位和范围查询。 。
因为当MySQL数据量很大时，索引大小也会很大，可能无法保存在内存中，所以需要进行相关的读写从磁盘。如果树的层次是too高，磁盘读写次数（I/O交互）会增加，性能会变差。
B树
红黑树唯一的缺点是树的高度不可控，所以现在我们的入口点 是树的高度。
目前，一个节点仅分配存储1个元素。如果我们想要控制高度，可以给一个节点分配一个较大的空间，让它水平存储多个元素，此时高度是可控的。经过这个转变过程，就变成了
B树。
B树是一个绝对平衡的多路树。它的结构中有两个概念
度：一个节点拥有的子节点（子树）的数量。 （有些地方
B树是用度来解释的，这里解释一下）阶数：一个节点的最大数量。 （通常用m表示）
关键字：数据索引。
m 阶 B 树 是平衡的 m 路搜索树。它可能是一棵空树，也可能满足以下特征：
除根节点和叶节点外，其他节点至少有 ⌈2 米 < span class="vlist-s">⌉ 子节点；
⌈ 2< span class="pstrut">m ⌉为m/2，然后向上取整
每个非根节点包含的关键字j的数量满足：< span class="mopen">⌈2< span>m ⌉ - 1 ≤ j ≤ m - 1；
节点关键字是从左到右升序排列，有k个关键字的非叶子节点恰好有(k + 1)个子节点；
所有叶子节点都位于同一级别。
名字的含义（题外话，放松一下）
以下摘自维基百科
Rudolf Bayer）和Ed M. McCreight 于 1972 年在波音研究实验室工作时发明了 B 树，但他们没有解释 B 代表什么含义（如果有的话）。
Douglas Comer 解释道：两位作者都没有解释过 B-tree 的原始含义。我们可能觉得平衡、宽阔或浓密可能是合适的。其他人则认为字母 B 代表波音。然而，由于他的赞助，将 B 树视为拜耳树似乎更合适。
Donald Knuth）在1980年5月发表的题为“CS144C关于磁盘存储和B-trees的课堂讲座”的论文中，推测了B-tree这个名字的含义以及提议 B 可能意味着n 波音或拜耳的名字。
搜索
B树的搜索其实和二叉树非常相似：
二叉树有一个关键字在每个节点和两个分支上，B-tree 上的每个节点都有 k 个关键字和 (k + 1) 个分支。
二叉树中的搜索只考虑向左还是向右，而B树需要通过多个分支来确定。
B树的搜索分为两步：
B-tree通常存储在磁盘上，因此这一步需要磁盘IO操作；搜索关键字。当找到一个节点时，将该节点读入内存，然后通过顺序或二分查找找到关键字。如果没有找到关键字，则需要判断大小，找到合适的分支继续搜索。 操作过程
现在需要查找元素：88
第一次：磁盘IO
第二次：磁盘IO
第三个time：磁盘IO
然后是内存比较，分别与70和88进行比较，最终找到88。
从搜索过程中我们发现B-tree的比较次数和磁盘IO次数其实和那些没有太大区别二叉树。似乎没有什么区别。有什么优点。
但是仔细一看，你会发现比较是在内存中完成的，不涉及磁盘IO，时间消耗可以忽略不计。
此外，B-tree中的一个节点可以存储许多关键字（数量由顺序决定）。相同数量的关键词词在B树中生成的节点远少于二叉树中的节点，节点数量的差异相当于数量磁盘 IO 数。达到一定数量后，性能差异就变得明显。
插入
当B-tree 当你想要插入关键字时，总是直接找到叶子节点并执行操作。
操作流程
例如，我们现在需要向最大度（阶）为3：72的B树中插入元素
查找要插入的元素叶子节点
节点分裂：应该和[70,88]在同一个磁盘块上，但是当一个节点有3个关键字时，是可以的如果有 4 个子节点，则超出了我们定义的限制的最大度数 3，因此 split 必须按每个此时形成：以middle关键字为边界，将节点一分为二，生成一个新节点，并将中间关键字上移到父节点。
提示：当有两个中间关键字时，左侧关键字通常会向上移动并拆分。
删除
删除操作会比查找和插入更麻烦，因为要删除的关键字不一定在叶子节点上，删除也可能会导致 B树是不平衡的，需要进行合并、旋转等操作来维持整棵树的平衡。
仅以一棵树（第 5 级）为例
感谢您的阅读！看完上面的内容，你是不是对MySQL索引使用B+tree的原因有了一个大概的了解了呢？希望文章的内容对大家有所帮助。如果您想了解更多相关文章，请关注行业资讯渠道。
2. 本站积分货币获取途径以及用途的解读，想在本站混的好，请务必认真阅读！
3. 本站强烈打击盗版/破解等有损他人权益和违法作为，请各位会员支持正版！
4. 编程技术 > MySQL索引使用B+tree的原因
