为什么MySQL要用B+树？

为什么MySQL要用B+树？

​ 这是数据库相关面试中非常常见的问题，对于这个问题我听过很多答案，例如：B+树节点存id节约空间、B+树子树之间有指针、B+树只需要较低的层高就能存大量数据...

​ 并不是说这些答案不对，但是终究是有点片面。

​ 所以今天我们来系统的讨论下，为什么MySQL要用B+树。

前言

首先要明白的一点是，B+树跟MySQL没有任何直接关系，真正跟B+树有关系的是MySQL的存储引擎，而存储引擎的主要作用是负责数据的存储和提取。

image.png

MySQL的默认存储引擎是InnoDB，当然也可以使用MyISAM，今天不讨论MyISAM，只说说InnoDB。那么问题来了？为什么MySQL的默认存储引擎InnoDB要使用B+树来作为数据的存储结构呢？

​ 相信有阅读过MySQL索引章节的同学们都了解过，表中的索引不论是主键还是辅助索引都会使用B+树进行存储，前者使用的存储方式是<id, row>，后者的方式是<row_index, id>。这也比较容易理解：

  • 在主键（聚簇索引）中，id是主键，数据库通过id去查找数据行。
  • 在非聚簇索引（辅助索引）中，索引的列（或者说数据行的列）构成了主键，通过索引的列去找到索引的id。（如果有需要，还可以通过id去找当前数据行的全部内容，这也是为什么辅助索引需要再回表的原因）

讨论

现在疑问来了，InnoDB为什么要用B+树呢？用B树不行吗？用hash表不行吗？ok，我们从两个角度来分析这个问题：

  • InnoDB 需要支持的场景和功能需要在特定查询上拥有较强的性能
  • CPU 将磁盘上的数据加载到内存中需要花费大量的时间

这其实就是我们使用数据库最平常不过的两个操作：对数据的持久化与对持久化数据的查询。实时查询数据需要快，而持久化数据需要IO，在这两者同时兼顾的情况下，B+树成为了最好的选择。

读写性能

​ MySQL作为传统的关系型数据库（OLTP），InnoDB作为传统关系型数据库的存储引擎，通常要用来执行以下操作：

  • 通过Insert、Delete、Update对单行数据进行增删改
  • 通过 Update 和 Delete 语句对符合条件的数据进行批量的删除；
  • 通过 Select 语句和主键查询某条记录的全部列；
  • 通过 Select 语句在表中查询符合某些条件的记录并根据某些字段排序；
  • 通过 Select 语句查询表中数据的行数select count(*)；
  • 通过唯一索引保证表中某个字段或者某几个字段的唯一性；

如果我们尝试对一条数据进行修改/访问时，SQL执行的时间复杂度时O(logN),而N是树的高度。但是这时候有小伙伴就要问了：

  • 啊！你这O(logN)，Hash表读可是可以达到O(1)的！B+树8彳亍！

虽然对于读取单条数据的场景说，哈希表确实爆杀B+树，但是不要忘了，我们还有范围查询的场景：

select * from table where age='22' order by desc; 

select * from table where age > 18;

update table set features = '超级帅' where name = '十七';

delete from table where name = 'hug';

​ 我们都知道哈希表的原理是根据字符串进行哈希然后均摊在哈希桶中，而哈希表不论是哈希桶还是哈希值都是无序的。

​ 这就意味着，当遇到范围匹配的场景时，哈希表构成的索引就完全没有用处了，只能进行全表查询并且一个一个的去判断是否满足条件。而全表查询对于数据库来说十分的糟糕！==（所有的查询都应该避免全表查询！）==换句话说，在范围查询时，哈希表有跟无， 没有区别。

​ 而B+树是能够保证数据按照主键的顺序进行存储，也就是说在B+树中，相邻的数据其实都是按照自然顺序排列的（这里就不讲B+树的原理了）

​ 这时候又有小伙伴要问了：

  • 啊！不是还有B树吗！B树也可以排列啊！为啥不用B树！（是不是因为作者没有B树！）

​ B树和B+树在数据结构上确实是类似的，他们都可以按照顺序对索引中的内容进行遍历，对于排序和范围查询等操作，B树相对于B+树来说会有更好的性能。（当然如果索引建的比较差劲或者SQL写的复杂，也是会全表查询。）

小结

与 B 树和 B+ 树相比，哈希作为底层的数据结构的表能够以 O(1) 的速度处理单个数据行的增删改查，但是面对范围查询或者排序时就会导致全表扫描的结果。

而 B 树和 B+ 树虽然在单数据行的增删查改上需要 O(log n) 的时间，但是它会将索引列相近的数据按顺序存储，所以能够避免全表扫描。

数据加载

我们来回答小伙伴的问题，哈希表已经被我们排除了，B+树和B树一样都可以相对高效的执行查询，那为什么不选择B树？

这时候我们就要来讨论第二个因素——数据加载

先来说说读取数据

稍微了解操作系统的小伙伴们都知道，计算机在读取文件的时候会按页为单位将数据读到内存中。页的大小在大多数操作系统上都是4KB，可以通过

$ getconf PAGE_SIZE
16384/4096 ...

来获取，我的电脑一页是16KB，因操作系统不同而不同。

在我们执行查询数据时，CPU会发现当前数据在磁盘里而不是内存中，这时候就会触发I/O将数据从磁盘中读入内存中进行访问。而我们都知道数据从磁盘读到内存的成本非常大。就以普通磁盘为例，加载数据需要经过队列、寻道、旋转、传输等过程，总计算大约需要10ms的时间。

回到数据库

一般我们估算MySQL查询时间时就可以用10ms来衡量随机I/O时间，这里需要特别说一下，这个时间指的是随机I/O的时间，顺序读取磁盘数据是可以达到40MB/s的，两者差距是几个数量级，因此在日常开发中，要注意减少随机I/O的次数，以提高性能。

而B树和B+树最大的区别在于，B树可以在非叶子结点中存储数据，但是B+树的所有数据都存在叶子结点中，下面来举个栗子，假设有以下语句：

select * from table where id > 3 and id < 9

那么，如图所示：

image-20220316204050209

如果我们不考虑优化，在上面的B树中执行查询的顺序是：

  1. 加载根节点，发现根节点第一个元素是5，大于3（第一次随机I/O）
  2. 通过根节点加载左叶子节点，遍历叶子结点的数据，找到匹配的数据（第二次随机I/O)
  3. 加载回根节点，发现根节点不包含第二个元素（第三次随机I/O）
  4. 加载右叶子节点，遍历叶子结点数据，找到匹配的数据（第四次随机IO）

由此得出，执行上面的简单的查询语句在B树中我们需要进行4次随机IO才能找到所有满足条件的行，当然我们也可以用各种方式来优化查询，不过，B树能做的优化基本上B+树都可以。但有的优化，B+树可以，B树不彳亍。

B+树可以，B树不行的优化

由于所有的节点都可能包含目标数据，我们总是要从根节点向下遍历子树查找满足条件的数据行，这个特点带来了大量的随机 I/O，也是 B 树最大的性能问题。

但B+ 树中就不存在这个问题了，B+树所有的数据行都存储在叶节点中，而这些叶节点可以通过指针依次按顺序连接，遍历数据时可以直接在多个子节点之间进行跳转，这样能够节省大量的磁盘 I/O 时间，也不需要在不同层级的节点之间对数据进行拼接和排序。

通过一个 B+ 树最左侧的叶子节点，我们可以像链表一样遍历整个树中的全部数据，也可以引入双向链表保证倒序遍历时的性能。

image-20220316222441110

当然，有的小伙伴可能就会问了：

  • 啊！你这个B+树的结构会因为数据量不断增加高度从而增加整体的耗时！

然而，根据B+树的原理高度为 3 的 B+ 树就能够存储千万级别的数据，实践中 B+ 树的高度最多也就 4 或者 5，所以不用担心，这不是性能瓶颈。

总结

如果一个设计不考虑场景，那么所有的设计都是纸上谈兵

当我们了解需求场景和使用原理，再对不同的数据结构进行选择就成了理所当然的事情。只能说，B+树不是最好的数据结构，但是对于MySQL来说，B+树就是合适的结构，他能在尽量优秀的情况下解决大多数情况下MySQL会遇到的问题。

我们来把文章的内容总结一下，为什么MySQL默认的存储引擎选择B+树而不是哈希表或者B树呢？

原因：

  • 哈希表有极其优秀的单数据操作性能，但是对于范围查询和排序却无能为力，反而会引起全表扫描。
  • B树能够在非叶节点中存储数据，但是这也导致在查询连续数据时可能会带来更多的随机 I/O，而 B+ 树的所有叶节点可以通过指针相互连接，能够减少顺序遍历时产生的额外随机 I/O。

当然，有的小伙伴可能会问了：

  • 啊！我就不能两个都用吗！单行数据的时候我用哈希，顺序查询的时候我用B+树！

答案是当然可以，但是必须能够容忍更高的复杂度。

在同一张表上可以同时建哈希表和B+树构成的存储结构，这样在不同的操作时可以选择更快的数据结构，但是！这会导致更新和删除时在redo log中操作更多份数据，总表的体积也会变得非常非常大

从今天的角度来看，B+树可能不是 InnoDB 的最优选择，但是它一定是能够满足当时设计场景的需要。

结尾引用自draveness大大的一句话

数据库、程序、系统设计思想的发展到今天已经过了几十年的时间，我们不得不说优秀的工程设计确实有足够的生命力。而我们作为工程师，在设计系统、设计算法、设计数据结构时也应该非常清楚地知道不同数据结构、程序架构适合的场景，因为软件工程中没有银弹。

Reference

最后修改：2022 年 08 月 05 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏