B树与数据库索引

什么是B树

B树在许多软件中都扮演着基础角色，尤其是数据库管理系统（DBMS）。MySQL、PostgreSQL、MongoDB、Dynamo 等众多系统都依赖 B 树通过索引来高效地查找数据。当你读完这篇文章时，你将了解 B 树和 B+ 树的工作原理，数据库为何使用它们来构建索引，以及为什么将 UUID 作为主键可能不是一个好主意。你还将有机会体验我们讨论的数据结构的交互式动画。准备好点击按钮吧。

计算机科学领域有大量的数据结构可供选择，用于在计算机上存储、搜索和管理数据。B树就是这样一种数据结构，它在数据库应用中被广泛使用。B树以计算机程序员所说的树状结构存储被称为键值对的数据。对于不熟悉计算机科学家如何使用“树”这个术语的人来说，它实际上看起来更像一个根系。

下面是本博客的第一个交互式组件。借助它，你可以直观地看到B树的结构，还能了解在添加键值对以及更改每个节点的键值对数量时会发生什么。点击“添加”或“Add random”按钮几次来试试看，在我们深入细节之前，先直观感受一下它的工作原理。

如果上述动画速度过快或过慢，你可以调整本文中所有与B树相关操作的动画速度。请在下方进行调整：

每个 B 树都由节点（矩形）和子指针（连接节点的线）组成。我们将最顶层的节点称为根节点，最底层的节点称为叶子节点，其余的节点则称为内部节点。B 树的正式定义可能因询问对象的不同而有所差异，但以下是一个相当典型的定义。

阶为 K 的 B 树是一种具有以下属性的树结构：

树中的每个节点存储 N 个键值对，其中 N 大于 1 且小于或等于 K。
每个内部节点至少有 N/2 个键值对（内部节点是指既不是叶子节点也不是根节点的节点）。
每个节点有 N + 1 个子节点。
根节点至少有一个值和两个子节点，除非它是唯一的节点。
所有叶子节点都在同一层。

B树的另一个关键特性是有序性。在每个节点中，元素都保持有序排列。某个键左侧的所有子节点只能包含小于该键的其他键。右侧的子节点则必须包含大于该键的键。

这种强制的有序性意味着你可以非常高效地搜索一个键。从根节点开始，执行以下操作：

检查该节点是否包含你要查找的键。
如果不包含，则在节点中查找要插入该键时它会被插入的位置。
沿着该位置的子指针向下进入下一层，然后重复此过程。

以这种方式进行搜索时，为了查找一个键，你在树的每一层只需访问一个节点。因此，树的层数越少（或者说树越浅），搜索速度就越快。试着在下面的树中搜索一些键：

当你有大量数据需要持久化到长期存储设备（磁盘）时，B树特别适用。这是因为每个节点使用固定数量的字节。字节数量可以进行调整，以很好地适配磁盘块。

在硬盘（HDD）和固态硬盘（SSD）上读写数据是以称为块的单位进行的。这些块通常是长度为 4096、8192 或 16384 字节的字节序列（4KB、8KB、16KB）。单个磁盘的容量可以达到数百万甚至数十亿个块。另一方面，随机存取存储器（RAM）通常可以按字节寻址。

这就是为什么当我们需要在磁盘上组织和存储持久化数据时，B 树能很好地发挥作用。B 树的每个节点的大小可以设置为与磁盘块的大小相匹配（或为该大小的倍数）。

树中每个节点能够存储的值的数量，取决于为每个节点分配的字节数以及每个键值对所占用的字节数。在上面的示例中，你看到了一些非常小的节点 —— 存储 3 个整数值和 4 个指针的节点。如果我们的磁盘块和 B 树节点大小为 16KB，并且我们的键、值和子指针都为 8 位，这意味着每个节点可以存储 682 个键值对和 683 个子指针。一个三层的树可以存储超过 3 亿个键值对（682 × 682 × 682 = 317,214,568）。

什么是B+树

B树非常优秀，但许多数据库索引使用了一种更“高级”的变体，称为B+树。它与B树类似，但规则有以下变化：

键值对仅存储在叶子节点中。
非叶子节点仅存储键和相关的子指针。

在MySQL索引中实现B+树还有两条特定的额外规则：

非叶子节点存储N个子指针，而不是N+1个。
所有节点还包含“下一个”和“上一个”指针，使得树的每一层都能充当双向链表。

下面是另一个可视化示例，展示具有这些修改特性的B+树是如何工作的。这次除了添加键值对外，你还可以分别调整内部节点和叶子节点中的键的数量。

为什么 B+ 树更适合用于数据库呢？主要有两个原因。

由于内部节点无需存储值，每个内部节点可以容纳更多的键！这有助于保持树的层级更浅。
所有的值都可以存储在同一层级，并且可以通过底层的链表按顺序遍历。

也来尝试一下在 B+ 树上进行搜索吧：

在Mysql中使用B+树

可以说，MySQL 是世界上最受欢迎的数据库管理系统，它支持多种存储引擎。最常用的引擎是 InnoDB，它严重依赖 B+ 树。事实上，它对 B+ 树的依赖程度之深，以至于实际上会将所有表数据存储在一棵 B+ 树中，其中表的主键被用作树的键。

每当你创建一个新的 InnoDB 表时，都需要指定一个主键。数据库管理员和软件工程师通常会使用简单的自增整数作为这个值。在幕后，MySQL 和 InnoDB 会为每个新创建的表创建一棵 B+ 树。这棵树的键就是所设置的主键。值则是每行的其余列值，并且仅存储在叶子节点中。

这些 B+ 树中每个节点的大小默认设置为 16KB。每当 MySQL 需要访问某条数据（键、值等）时，它都会从磁盘加载整个关联的页面（B+ 树节点），即使该页面包含其他它不需要的键或值也是如此。

每个节点中存储的行数取决于表的“宽度”。在“窄表”（列数较少的表）中，每个叶子节点可以存储数百行数据。在“宽表”（列数较多的表）中，每个叶子节点可能只能存储个位数的行数。InnoDB 也支持行的大小大于磁盘块，但在本文中我们不会深入探讨这一点。

使用下面的可视化示例来查看每个内部节点和每个叶子节点中的键数量如何影响树的深度。树的深度越大，查找元素的速度就越慢。因此，我们希望数据库中的树尽可能浅！

在 InnoDB 表上创建二级索引也很常见，二级索引是创建在非主键列上的索引。在 SQL 查询中，可能需要这些索引来加快 WHERE 子句的过滤速度。为每个二级索引都会构建一棵额外的持久化 B+ 树。对于这些 B+ 树，其键是用户选择用来创建索引的列，值则是关联行的主键。每当查询使用二级索引时：

在二级索引的 B+ 树上执行搜索。
收集匹配结果的主键。
然后使用这些主键在主表的 B+ 树上进行额外的 B+ 树查找，以找到实际的行数据。

考虑以下数据库模式：

CREATE TABLE user (
  user_id BIGINT UNSIGNED AUTO_INCREMENT NOT NULL,
  username VARCHAR(256) NOT NULL,
  email VARCHAR(256) NOT NULL,
  PRIMARY KEY (user_id)
);
CREATE INDEX email_index ON user(email);

这将创建两个 B+ 树索引：

一个用于表的主键，使用 user_id 作为键，另外两列存储在值中。
另一个用于 email_index，使用 email 作为键，user_id 作为值。

当执行类似这样的查询时：

1	SELECT username FROM user WHERE email = 'x@veitor.net';

这将首先在 email_index 的 B+ 树上查找 x@veitor.net。找到关联的 user_id 值后，会使用该值在主键 B+ 树上进行另一次查找，并从那里获取用户名。

总体而言，我们始终希望最小化执行查询时需要访问的块/节点数量。我们需要访问的节点越少，查询速度就越快。为表选择的主键对于最小化需要访问的节点数量至关重要。

插入数据

表中的数据在 B+ 树中的排列方式取决于你选择的键。这意味着你对主键的选择将影响表中所有数据在磁盘上的布局，进而影响性能。请谨慎选择你的主键！

主键通常有两种常见的选择：

整数序列（例如 BIGINT UNSIGNED AUTO_INCREMENT）
UUID，它有多种版本。

我们先来考虑使用 UUIDv4 作为主键会带来的后果。UUIDv4 是一个基本随机的 128 位整数。

我们可以通过在 B+ 树可视化界面中 插入一组随机整数 来模拟这种情况。每次插入时，所有被访问的节点都会 高亮显示为绿色。你还可以控制在节点分裂时 保留在现有节点中的键的百分比。点击 Add random 按钮几次试试看，你注意到了什么？

一些观察结果：

插入操作时要访问的节点无法提前预测。
插入操作的目标叶子节点无法提前预测。
叶子节点中的值是无序的。

问题 1 和问题 2 会带来麻烦，因为在多次插入过程中，我们不得不访问树中的许多节点（页面）。这种过度的读写操作会导致性能不佳。如果我们打算按数据插入的顺序搜索或查看数据，问题 3 也会带来麻烦。

其他一些 UUID 也可能出现同样的问题（尽管可能没有那么严重）。例如，UUID v3 和 v5 都是通过哈希生成的，因此不会是连续的，其行为与随机插入类似。不过，UUIDv7 在克服其中一些问题方面表现得相当不错。

让我们考虑使用连续的 BIGINT UNSIGNED AUTO_INCREMENT 作为主键。尝试在 B+ 树中 插入连续值：

这可以缓解上述所有问题：

插入新值时，我们总是沿着最右侧的路径进行。
叶子节点只会在树的右侧添加。
在叶子节点层，数据会根据插入顺序排序。

由于上述第 1 点和第 2 点，许多连续的插入操作会重复访问相同的页面路径，这意味着在插入大量键值对时，I/O 请求会更少。

下面的柱状图展示了上述两棵 B+ 树中前 5 次插入操作访问的唯一节点数量。假设两棵树的深度相同，你会发现随机插入对应的数值略高，这意味着性能更差。

如果你想了解 分裂百分比 对连续插入和随机插入模式的影响，可以查看下面的交互式可视化图表。使用滑块设置 分裂百分比，折线图会更新，显示在插入 400 个键的过程中不同阶段前 5 次插入需要访问的节点数量。请注意，在大多数情况下，连续插入 需要访问的节点数量比 随机插入 少得多，而且也更可预测。

数据顺序

在数据库中按时间顺序搜索数据是很常见的操作。以查看 X 平台上的时间线，或者 Slack 中的聊天记录为例。我们通常希望按时间（或逆时间）顺序查看帖子和聊天消息。这意味着我们经常会读取在时间上“相近”的数据库数据块。这些查询通常采用以下形式：

SELECT username, message_text, ...
FROM post
  WHERE sent > $START_DATETIME
  AND sent < $END_DATETIME
  ORDER BY sent DESC;

设想一下，如果我们使用 UUIDv4 作为主键会怎样。在下面的 B+ 树中，已经向表中插入了一堆随机键和对应的值。尝试 查找值的范围。你看到了什么？

注意到值序列分布在许多非连续的叶子节点中。另一方面，可以考虑 查找 按顺序插入的值。

在这种情况下，包含搜索结果的所有页面都会彼此相邻。甚至有可能搜索几行数据，而这些数据都在同一页面中彼此相邻。对于这种查询模式，我们可以使用顺序主键来减少需要读取的页面数量。

主键大小

另一个需要考虑的重要因素是键的大小。我们总是希望主键满足以下条件：

足够大，永远不会出现值耗尽的情况
足够小，不会占用过多的存储空间

对于整数序列，对于较小的表，我们有时可以使用 MEDIUMINT（1600 万个唯一值）或 INT（40 亿个唯一值）。对于大表，为了稳妥起见，我们通常会使用 BIGINT（1800 亿亿亿个可能的值）。BIGINT 是 64 位（8 字节）。UUID 通常是 128 位（16 字节），是 MySQL 中最大整数类型大小的两倍。由于 B+ 树的节点大小是固定的，与 UUID 相比，BIGINT 能让每个节点存储更多的键。这会使树的层级更浅，查找速度更快。

假设每个树节点只有 100 字节，子指针为 8 字节，值为 8 字节。每个节点可以存储 4 个 UUID（加上 4 个子指针）。点击下面的播放插入序列按钮查看插入过程。

如果我们使用的是 BIGINT，那么每个节点就可以容纳 6 个键（以及相应的子指针）。这将使树的层级更浅，有助于提升性能。

页和InnoDB

回顾一下，B+树的一大优势在于我们可以将节点大小设置为任意想要的值。在 InnoDB 中，B+树节点通常设置为 16KB，这也是一个 InnoDB 页 的大小。

在执行查询（因此需要遍历 B+树）时，InnoDB 不会从磁盘读取单独的行和列。每当它需要访问某条数据时，都会从磁盘加载整个关联的页。

InnoDB 有一些方法来缓解这个问题，其中主要的方法就是 缓冲池。缓冲池是 InnoDB 页的内存缓存，位于磁盘上的页和 MySQL 查询执行之间。当 MySQL 需要读取一个页时，它首先会检查该页是否已经在缓冲池中。如果在，就直接从缓冲池中读取，跳过磁盘 I/O 操作。如果不在，它会在磁盘上找到该页，将其添加到缓冲池中，然后继续执行查询。

缓冲池极大地提升了查询性能。如果没有缓冲池，为了处理查询任务，我们最终将进行大量额外的磁盘 I/O 操作。即便有了缓冲池，尽量减少需要访问的页面数量也有助于提升性能，原因如下：(1) 在缓冲池中查找页面仍有（少量的）开销；(2) 这有助于减少缓冲池需要进行的加载和淘汰操作的次数。

其他情况

在这里，我们主要关注了顺序键与随机键/UUID 键的比较。不过，无论你考虑使用哪种主键或二级键，这里展示的原则都值得牢记。

例如，你也可以考虑使用 user.created_at 时间戳作为索引的键。这将具有与顺序整数类似的特性。通常情况下，插入操作总是会沿着最右侧的路径进行，除非正在插入旧数据。

相反，像 user.email_address 字符串这样的键会具有更类似于随机键的特性。用户不会按照邮箱地址的字母顺序来创建账户，因此插入操作会在 B+ 树的各个位置发生。

总结

这已经是一篇很长的博客文章了，但关于 B+ 树、索引以及 MySQL 中主键的选择，还有很多内容可以探讨。表面上看，这些内容似乎很简单，但如果你想充分挖掘数据库的每一点性能，就有非常多的细节需要考虑。如果你想进一步实验，可以访问专门的交互式 B+ 树网站。如果你想了解普通的 B 树，请访问这里。希望你对索引有了一些新的认识！