从头实现数据库3

B+树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。

B树是一个平衡n叉树

许多实用的二叉树，例如 AVL 树或 RB 树，被称为高度平衡树，这意味着树的高度（从根到叶子）限制为 O(logN) ，因此查找是 O(logN) 。 B 树也是高度平衡的；所有叶节点的高度相同。

B+树操作

按键插入从叶子开始。叶子只是一个键的排序列表。将密钥插入到叶子中是很简单的。但是，插入可能导致节点大小超过页面大小。在本例中，我们需要将叶节点拆分为2个节点，每个节点包含一半的键，这样两个叶节点就可以放入一个页面中。

一个内部节点包括：

指向其子级的指针列表。

与指针列表配对的键列表。每个键都是对应子项的第一个键。

在将一个叶节点分割为2个节点之后。父结点用新指针和键替换旧指针和键。并且节点的大小增加，这可能会引发进一步的分裂。


    parent              parent
   /  |  \     =>      /  | |  \
L1   L2   L6         L1  L3 L4  L6

拆分根结点后，添加一个新的根结点。B树是这样生长的。


                       new_root
                          / \
    root                 N1 N2
   /  |  \     =>      /  | |  \
L1   L2   L6         L1  L3 L4  L6

键删除与插入相反。一个节点永远不会是空的，因为一个小节点将被合并到它的左同级或右同级。

并且当一个非叶根被减少到一个单一的键时，根可以被它唯一的子键替换。这就是B树缩小的方式。

不可变的数据结构

不可变意味着永远不会在适当的位置更新数据。类似的术语还有“只追加”、“写时复制”和“持久性数据结构”（“持久性”这个词与我们前面讨论的“持久性”没有任何关系）。

例如，当向叶节点插入一个键时，不要修改该节点，而是使用要更新的节点中的所有键和新键创建一个新节点。现在父结点也必须更新以指向新结点。

同样，父结点与新指针复制。在到达根结点之前，整个路径都是重复的。这有效地创建了与旧版本共存的树的新版本。

不变的数据结构有以下几个优点：

避免数据损坏。不可变数据结构不会修改现有的数据，它们只是添加新的数据，因此即使更新中断，旧版本的数据仍然保持不变。

易于并发。读取器可以与编写器并行操作，因为读取器可以在不受影响的旧版本上工作。

持久性和并发性将在后面的章节中介绍。现在，这里先编写一个不可变的B+树。