2

欢迎笑寒进入课堂我们刚刚回顾了数据库的基础和持久化技术，其中存储引擎的选择至关重要。今天我们深入探讨一种核心数据结构——B树。大家可能都熟悉平衡二叉搜索树，比如AVL树或红黑树，它们通过旋转来保持高度平衡，非常适合内存操作。但当数据量巨大，需要频繁读写磁盘时，频繁的旋转操作就显得效率低下。因为磁盘I/O是以页为单位的，一次读写一个页，而不是一个节点。所以，我们需要一种更适合磁盘特性的数据结构，这就是B树的出发点。B树的核心思想是放弃二叉树的限制，转而采用多叉树结构，每个节点可以容纳多个键和多个子节点指针，这样就能在一次I/O中获取更多的信息。B树的平衡策略与传统BST截然不同。AVL树、红黑树等通过旋转来调整左右子树的高度差，保证树的深度尽可能小。而B树的平衡关注的是节点的大小，也就是它能容纳的数据量。想象一下，一个节点就像一个文件夹，里面装满了文件。如果文件夹太满了，塞不下了怎么办？那就把它分成两个文件夹，这就是分裂。反之，如果一个文件夹太空了，几乎没东西，那就把它和旁边的兄弟文件夹合并一下，这就是合并。这种基于节点容量的平衡策略，使得B树的查找、插入和删除操作在磁盘I/O上都更加高效。大家可以简单理解为，B树是一种更胖、更矮的树，而不是像BST那样瘦高。如果你对2-3树有所了解，你会发现它就是B树的一个具体例子，更容易理解。为了帮助大家建立更直观的B树概念，我们不妨从大家熟悉的数组入手。一个有序数组，我们可以通过二分查找快速定位到目标值，效率是 O(log n)。但是，如果要在数组中间插入一个元素，或者删除一个元素，就需要移动后面所有元素，时间复杂度是 O(n)。对于内存来说，这可能还好，但对于磁盘来说，移动大量数据是非常耗时的操作。怎么办呢？我们可以借鉴B树的思想，把一个大数组拆分成若干个小数组，比如分成大约根号 n 个，每个小数组包含大约根号 n 个元素。然后，我们用一个顶层数组来记录这些小数组的起始位置，就像一个目录。查找的时候，先用二分法找到对应的目录项，再在对应的小数组里查找。插入或删除操作也主要发生在小数组内部，影响范围大大缩小。这种嵌套结构，其实就是B树的一种朴素体现。B树的内部节点和叶节点，就类似于这里的目录和小数组。现在我们聚焦于B加树的插入操作。B加树是一种常见的变体，它将数据值存储在叶节点，而内部节点只存储键值。插入操作总是从叶节点开始。找到合适的叶节点，将新键插入到有序列表中。这就像往一个有序列表里添加一个新元素。但如果这个列表太长了，超过了我们定义的页大小，怎么办？那就需要分裂。我们把这个叶节点拆分成两个新的叶节点，每个节点大约包含一半的键。原来的父节点需要更新，用新的子节点指针替换掉旧的，并且增加一个新的键值，这个新键值是分裂后两个新叶节点的最小键值。这个过程会一直向上递归，直到根节点。如果根节点也因为分裂而增大，超过了页容量，那么就需要创建一个新的根节点，树的高度增加一层。这就是B加树的生长机制。我们来看一个具体的插入示例。假设父节点原来指向一个叶节点 L2。我们向 L2 中插入一个元素，导致 L2 超出了页容量。这时，L2 被分裂成两个新的叶节点 L3 和 L4。父节点需要更新，它原来指向 L2 的位置，现在要指向 L3 和 L4，同时，它还需要增加一个键，通常是 L3 的最小键值，用来区分 L3 和 L4 的范围。这就像在目录里增加了一个新的条目。如果这个操作发生在根节点，情况就更特殊了。根节点分裂后，会产生一个新节点，它会成为新的根节点，原来的根节点变成它的子节点。这样，树的高度就增加了。这就是 B树如何通过分裂和可能的根节点分裂来适应数据增长的。删除操作是插入操作的逆过程。我们通常从叶节点开始删除。如果删除后，一个节点里的键数量太少，低于我们设定的最小阈值，怎么办？这就需要合并或者借用。合并，就是把一个节点和它旁边的兄弟节点合并成一个。如果兄弟节点有富余，还可以借用一些键和子节点过来，避免合并带来的额外开销。这就像两个文件夹太空了，可以合并一下，或者从旁边的文件夹借几个文件过来。对于非叶节点，如果删除后只剩下一个键，那它可能就变成了一个叶子节点。对于根节点，如果它不是叶子节点，而且只剩下一个键，那么它就可以被收缩，直接用它唯一的子节点来替代自己，树的高度会减少。在深入代码之前，我们先聊聊不可变数据结构。这个概念在现代系统设计中越来越重要，尤其是在并发和持久化方面。不可变意味着一旦创建，数据就不能再被修改了。每次更新操作都生成一个全新的数据副本，而不是在原地修改。这听起来有点反直觉，但好处多多。比如，在我们的B加树插入场景中，当我们想往一个叶节点插入一个新键时，我们不直接修改那个叶节点，而是创建一个新的叶节点，这个新节点包含了所有旧键和新键。然后，我们再创建一个新的父节点，这个父节点指向新的叶节点。如果原来的父节点也需要更新，我们就再复制一个父节点，以此类推，直到根节点。这样，整个插入操作就形成了一个全新的、独立的树版本，而原来的树版本保持不变。这种append only或者copy on write的方式，是构建可靠、并发友好的数据结构的关键。为什么我们要费心搞这种不可变结构呢？主要有两大优势。第一，避免数据损坏。在分布式系统或者需要持久化的场景下，更新操作可能会因为各种原因中断，比如机器宕机、网络故障。如果数据是可变的，那么在更新过程中发生中断，就可能导致数据处于不一致或损坏的状态。但不可变结构就不怕了，因为它只创建新的版本，旧版本始终是完整的。即使更新失败，旧数据依然可用。第二，易于并发。读写操作可以并行进行。因为读者总是访问的是某个稳定版本的数据，而写者则是在创建新的数据版本，两者互不影响。这大大简化了并发控制，提高了系统的吞吐量和响应速度。这对于高并发的数据库系统来说至关重要。理论讲了不少，现在我们来动手实践一下，用Go语言实现一个简单的不可变B加树。首先，我们要考虑数据怎么存到磁盘上。所以，第一步是设计一个清晰的节点格式。一个B加树节点，无论是内部节点还是叶节点，都需要包含一些基本信息。我们通常会有一个固定大小的头部，记录节点的类型是内部还是叶子，以及它里面存储了多少个键。对于内部节点，还需要包含指向其子节点的指针列表。为了方便查找和管理，我们通常会维护一个偏移量列表，记录每个键值对在节点内部的起始位置。最后，就是实际的键值对数据，我们会把它们紧凑地打包在一起。我们再具体看一下这个格式。头部占4个字节，前两个字节表示类型，后两个字节表示键的数量。如果是内部节点，接下来就是指针列表，每个指针通常是64位的，用来指向磁盘上的页号。然后是偏移量列表，每个偏移量是2个字节，表示相对于第一个键值对起始位置的偏移。注意，第一个键值对的偏移量是0，所以不需要存储。最后是键值对本身，每个键值对前先用2个字节存储键的长度，再用2个字节存储值的长度，然后紧跟键的数据和值的数据。这种结构设计使得我们可以高效地计算出任何一个键值对的位置，也方便了节点的序列化和反序列化。基于刚才的节点格式，我们定义一些数据类型。最核心的是 BNode，它就是一个字节切片，用来存放节点的二进制数据。这样做的好处是，我们可以直接把这个 byte 切片写入磁盘文件。我们定义了两个常量来区分内部节点和叶节点。然后是 BTree 结构体，它包含了根节点的页号，以及三个关键的回调函数：get 用于获取指定页号的节点，new 用于分配新的页并返回页号，del 用于释放页。这三个回调函数抽象了底层的磁盘操作，使得我们的 B 树代码可以专注于逻辑本身。我们还定义了页大小，比如常用的 4KB，以及键和值的最大长度限制。这些限制是为了保证单个键值对一定能放入一个页内，避免了单个 KV 对跨页存储的复杂性。当然，实际应用中可能需要更灵活的处理。有了 BNode 结构，我们还需要一些辅助函数来方便地读取和写入数据。我们先来看头部信息的处理。btype 函数用来获取节点的类型，nkeys 函数获取节点中的键数。这两个函数都使用了 binary.LittleEndian.Uint16 来读取小端序的 16 位无符号整数。setHeader 函数则负责设置头部信息，同样使用了 binary.LittleEndian.PutUint16。这些函数封装了底层的字节序转换和偏移量计算，使得上层代码可以更简洁地操作节点信息。接下来是内部节点的指针列表和偏移量列表。对于内部节点，我们有 getPtr 和 setPtr 函数来获取和设置第 idx 个子节点的指针。指针列表紧跟在头部之后，每个指针占用 8 个字节。偏移量列表则稍微复杂一点。我们注意到，第一个键值对的起始偏移量是 0，所以不需要存储。我们只需要存储 nkeys 个偏移量，分别对应第 1 个到第 nkeys 个键值对的起始偏移量。offsetPos 函数计算了偏移量列表中第 idx 个元素在 BNode.data 中的起始位置。getOffset 函数返回第 idx 个键值对的起始偏移量，注意 idx 从 1 开始，因为第 0 个偏移量是 0。setOffset 则负责设置这些偏移量。这些函数共同实现了对节点内部结构的访问。最后，我们来看如何访问和操作键值对本身。我们需要知道第 idx 个键值对在节点数据中的起始位置，这就是 kvPos 函数要计算的。它结合了头部、指针列表和偏移量列表的起始位置，以及从偏移量列表中获取的该键值对的起始偏移量。一旦知道了起始位置，就可以用 getKey 和 getVal 函数来提取键和值了。它们首先读取键的长度 klen 和值的长度 vlen，然后根据这些长度从数据中切片出对应的键和值。还有一个 nbytes 函数，它计算了整个节点占用的字节数，这对于判断节点是否需要分裂非常重要。通过这些辅助函数，我们可以像操作普通数据结构一样，方便地访问和修改 BNode 内部的各个部分。