数据库系统内幕

B

树的变体

｜

103

所有写操作都必须经过根节点。在创建新根之后，旧根将无法进行新的读写操作。引用

旧树节的读操作一旦完成，其页就会被回收，并且可以被重新使用。由于 LMDB 的仅追

加设计，它不使用同级指针，所以在顺序扫描时必须上升到父节点。

在这种设计中，将陈旧数据留在复制出的节点中是不明智的：已经有一个副本可以用于

MVCC 并满足正在进行的读取事务了。这种数据库结构本质上是多版本的，读取者可以

在没有任何锁的情况下运行，因为它们不会以任何方式干扰写入者。

6.2

抽象节点更新

为了更新磁盘上的页，我们必须首先更新它在内存中的表示形式。然而，有多种方法

可以表示内存中的一个节点：我们可以直接访问节点的缓存版本，或者通过包装器

（wrapper）对象访问，抑或在实现语言中构建它的内存表示。

在具有非托管内存模型的语言中，存储在 B 树节点中的原始二进制数据是可以被重新解

释的，且可以被原生指针所操作。在这种情况下，节点是按照结构体定义的，这些结构

体使用指针和运行时类型转换来操作背后的原始二进制数据。最常见的情况是，它们指

向页缓存管理的内存区域，或者使用内存映射。

另一种方法是将 B 树节点物化为语言原生的对象或结构体。这些结构体可用于插入、更

新和删除。在刷写期间，更改应用于内存中的页，随后应用于磁盘上的页。这种方法的

优点是简化了并发访问，因为对底层原始页的更改与对中间对象的访问是分开管理的。

但是这会导致更高的内存开销，因为我们必须在内存中存储同一页的两个版本（原始二

进制版本和语言原生版本）。

第三种方法则是通过包装器对象来提供对节点背后缓冲区的访问 ...