为什么 MySQL 使用 B+ 树 （二）

设计

到了这里我们已经明确了今天待讨论的问题，也就是为什么 MySQL 的 InnoDB 存储引擎会选择 B+ 树作为底层的数据结构，而不选择 B 树或者哈希？在这一节中，我们将通过以下的两个方面介绍 InnoDB 这样选择的原因。

• InnoDB 需要支持的场景和功能需要在特定查询上拥有较强的性能；

• CPU 将磁盘上的数据加载到内存中需要花费大量的时间，这使得 B+ 树成为了非常好的选择；

数据的持久化以及持久化数据的查询其实是一个常见的需求，而数据的持久化就需要我们与磁盘、内存和 CPU 打交道；MySQL 作为 OLTP 的数据库不仅需要具备事务的处理能力，而且要保证数据的持久化并且能够有一定的实时数据查询能力，这些需求共同决定了 B+ 树的选择，接下来我们会详细分析上述两个原因背后的逻辑。

读写性能

很多人对 OLTP 这个词可能不是特别了解，我们帮助各位读者快速理解一下，与 OLTP 相比的还有 OLAP，它们分别是 Online Transaction Processing 和 Online Analytical Processing，从这两个名字中我们就可以看出，前者指的就是传统的关系型数据库，主要用于处理基本的、日常的事务处理，而后者主要在数据仓库中使用，用于支持一些复杂的分析和决策。

作为支撑 OLTP 数据库的存储引擎，我们经常会使用 InnoDB 完成以下的一些工作：

• 通过 INSERT、UPDATE 和 DELETE 语句对表中的数据进行增加、修改和删除；

• 通过 UPDATE 和 DELETE 语句对符合条件的数据进行批量的删除；

• 通过 SELECT 语句和主键查询某条记录的全部列；

• 通过 SELECT 语句在表中查询符合某些条件的记录并根据某些字段排序；

• 通过 SELECT 语句查询表中数据的行数；

• 通过唯一索引保证表中某个字段或者某几个字段的唯一性；

如果我们使用 B+ 树作为底层的数据结构，那么所有只会访问或者修改一条数据的 SQL 的时间复杂度都是 O(log n)，也就是树的高度，但是使用哈希却有可能达到 O(1) 的时间复杂度，看起来是不是特别的美好。但是当我们使用如下所示的 SQL 时，哈希的表现就不会这么好了：

SQL

SELECT * FROM posts WHERE author = 'draven' ORDER BY created_at DESCSELECT * FROM posts WHERE comments_count > 10UPDATE posts SET github = 'github.com/draveness' WHERE author = 'draven'DELETE FROM posts WHERE author = 'draven'

如果我们使用哈希作为底层的数据结构，遇到上述的场景时，使用哈希构成的主键索引或者辅助索引可能就没有办法快速处理了，它对于处理范围查询或者排序性能会非常差，只能进行全表扫描并依次判断是否满足条件。全表扫描对于数据库来说是一个非常糟糕的结果，这其实也就意味着我们使用的数据结构对于这些查询没有其他任何效果，最终的性能可能都不如从日志中顺序进行匹配。

使用 B+ 树其实能够保证数据按照键的顺序进行存储，也就是相邻的所有数据其实都是按照自然顺序排列的，使用哈希却无法达到这样的效果，因为哈希函数的目的就是让数据尽可能被分散到不同的桶中进行存储，所以在遇到可能存在相同键 author = 'draven 或者排序以及范围查询 comments_count > 10 时，由哈希作为底层数据结构的表可能就会面对数据库查询的噩梦 —— 全表扫描。

B 树和 B+ 树在数据结构上其实有一些类似，它们都可以按照某些顺序对索引中的内容进行遍历，对于排序和范围查询等操作，B 树和 B+ 树相比于哈希会带来更好的性能，当然如果索引建立不够好或者 SQL 查询非常复杂，依然会导致全表扫描。

与 B 树和 B+ 树相比，哈希作为底层的数据结构的表能够以 O(1) 的速度处理单个数据行的增删改查，但是面对范围查询或者排序时就会导致全表扫描的结果，而 B 树和 B+ 树虽然在单数据行的增删查改上需要 O(log n) 的时间，但是它会将索引列相近的数据按顺序存储，所以能够避免全表扫描。

数据加载

既然使用哈希无法应对我们常见的 SQL 中排序和范围查询等操作，而 B 树和 B 树和 B+ 树都可以相对高效地执行这些查询，那么为什么我们不选择 B 树呢？这个原因其实非常简单 —— 计算机在读写文件时会以页为单位将数据加载到内存中。页的大小可能会根据操作系统的不同而发生变化，不过在大多数的操作系统中，页的大小都是 4KB，你可以通过如下的命令获取操作系统上的页大小:

Go

$ getconf PAGE_SIZE4096

本文转载自 Draveness 技术博客。

原文链接：https://draveness.me/whys-the-design-mysql-b-plus-tree