终于了解 MySQL 索引要用 B+tree ，并且还这么快

发布时间：12/01 来源：未知浏览：关键词：

mysql教程栏目介绍懂得索引的B+tree。

免费引荐：mysql教程(视频)

前言

当你此刻碰到了一条慢 SQL 需要停止优化时，你第一时间能想到的优化手段是啥？

大部分人第一反响大概都是增加索引，在大多数状况下面，索引能够将一条 SQL 语句的查询效力提高几个数目级。

索引的本质：用于快速查寻记载的一种数据构造。

索引的常用数据构造：

二叉树
红黑树
Hash 表
B-tree （B树，并不叫什么B减树）
B+tree

数据构造图形化网址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

索引查询

大家知道 select * from t where col = 88 这么一条 SQL 语句假如不走索引停止查寻的话，正常地查就是全表扫描：从表的第一行记载开端逐行寻，把每一行的 col 字段的值和 88 停止对照，这明显效力是很低的。

而假如走索引的话，查询的流程就完全不一样了（假设此刻用一棵均衡二叉树数据构造储备我们的索引列）

此时该二叉树的储备构造（Key - Value）：Key 就是索引字段的数据，Value 就是索引所在行的磁盘文件地址。

当最后寻到了 88 的时候，就可以把它的 Value 对应的磁盘文件地址拿出来，然后就直接去磁盘上去寻这一行的数据，这时候的速度就会比全表扫描要快许多。

但实际上 MySQL 底层并没有用二叉树来储备索引数据，是用的 B+tree（B+树）。

为什么不采纳二叉树

假设此时用一般二叉树记载 id 索引列，我们在每插入一行记载的同时还要保护二叉树索引字段。

此时当我要寻 id = 7 的那条数据时，它的查寻历程如下：

此时寻 id = 7 这一行记载时寻了 7 次，和我们全表扫描也没什么很大不同。不言而喻，二叉树关于这种顺次递增的数据列其实是不适合作为索引的数据构造。

为什么不采纳 Hash 表

Hash 表：一个快速搜索的数据构造，搜索的时间复杂度 O(1)
Hash 函数：将一个任意类型的 key，可以转换成一个 int 类型的下标

假设此时用 Hash 表记载 id 索引列，我们在每插入一行记载的同时还要保护 Hash 表索引字段。

这时候开端查寻 id = 7 的树节点仅寻了 1 次，效力非常高了。

但 MySQL 的索引仍然不采纳能够精准定位的Hash 表。由于它不适用于范畴查询。

为什么不采纳红黑树

红黑树是一种特化的 AVL树（均衡二叉树），都是在停止插入和删除操纵时通过特定操纵保持二叉查寻树的均衡；
若一棵二叉查寻树是红黑树，则它的任一子树必为红黑树。

假设此时用红黑树记载 id 索引列，我们在每插入一行记载的同时还要保护红黑树索引字段。

插入历程中会发明它与一般二叉树不一样的是当一棵树的摆布子树高度差 > 1 时，它会停止自旋操纵，保持树的均衡。

这时候开端查寻 id = 7 的树节点只寻了 3 次，比所谓的一般二叉树还是要更快的。

但 MySQL 的索引仍然不采纳能够准确定位和范畴查询都优异的红黑树。

由于当 MySQL 数据量很大的时候，索引的体积也会很大，大概内存置不下，所以需要从磁盘上停止相关读写，假如树的层级太高，则读写磁盘的次数（I/O交互）就会越多，机能就会越差。

B-tree

红黑树当前的独一不足点就是树的高度不成控，所以此刻我们的切入点就是树的高度。
当前一个节点是只分配了一个储备 1 个元素，假如要操纵高度，我们就可以把一个节点分配的空间更大一点，让它横向储备多个元素，这个时候高度就可控了。这么个革新历程，就变成了 B-tree。

B-tree 是一颗绝对均衡的多路树。它的构造中还有两个概念

度（Degree）：一个节点具有的子节点（子树）的数目。（有的地方是以度来说明 B-tree 的，这里说明一下）
阶（order）：一个节点的子节点的最大个数。（平常用 m 表示）
关键字：数据索引。

一棵 m 阶 B-tree 是一棵均衡的 m 路搜索树。它大概是空树，或者知足以下特点：

除根节点和叶子节点外，其它每个节点至少有 $? \frac{m}{2} ? \lceil \dfrac{m}{2}\rceil$ 个子节点；
$? \frac{m}{2} ? \lceil \dfrac{m}{2}\rceil$ 为 m / 2 然后向上取整
每个非根节点所包括的关键字个数 j 知足： $? \frac{m}{2} ? \lceil \dfrac{m}{2}\rceil$ - 1 ≤ j ≤ m - 1；
节点的关键字从左到右递增摆列，有 k 个关键字的非叶子节点恰好有 (k + 1) 个子节点；
所有的叶子结点都位于统一层。

名字取义（题外话，轻松一下）

以下摘自维基百科

鲁道夫·拜尔（Rudolf Bayer）和艾华·M·麦克雷（Ed M. McCreight）于1972年在波音研讨实验室（Boeing Research Labs）工作时创造了 B-tree，但是他们没有说明 B 代表什么意义（假如有的话）。

道格拉斯·科默尔（Douglas Comer）说明说：两位作者从来都没说明过 B-tree 的原始意义。我们大概觉得 balanced, broad 或 bushy 大概适合。其别人倡议字母 B 代表 Boeing。源自于他的资助，不外，看起来把 B-tree 当作 Bayer 树更适宜些。

高德纳（Donald Knuth）在他1980年5月发布的题为 "CS144C classroom lecture about disk storage and B-trees" 的论文中猜测了 B-tree 的名字取义，提出 B 大概意味 Boeing 或者 Bayer 的名字。