开源单机存储引擎之 B-Tree/B+Tree

前面已整理过一篇关于 LSMTree 的开源单机存储引擎。本篇收集几个 B-Tree/B+Tree 的开源实现。

LMDB^[1]

LMDB（Lightning Memory-Mapped Database）是一个 C 语言实现的 B+Tree 结构的 key-value 存储引擎。它支持 MVCC、支持事务（ACID）、支持一写多读并发执行（读和写互不阻塞）。

我觉得 LMDB 设计上最大的特点，或者说“槽点”是：没有自己管理内存；而是直接使用 mmap，将内存/缓存的管理交给操作系统。

重点是，这竟然还成为了 LMDB 宣传的“亮点”：

With memory-mapped files, it has the read performance of a pure in-memory database while retaining the persistence of standard disk-based databases.

有点想吐槽……

不用自己实现内存（缓存）管理，好处是简化了存储引擎的实现。根据经验，如果数据量和内存大小接近，大部分请求都能命中 page cache，使用 mmap 似乎问题不大。MongoDB 最初的存储引擎就是采用了类似的方式。

但是如果数据量远超过内存大小（很多场景都是如此），那么海量的 page cache miss 造成的缺页、换页可能会是性能灾难，并且你几乎做不了任何控制和优化，毕竟你把一切都交给了操作系统。

当然，LMDB 仍然非常经典，代码不长，资料也不少，就算不看代码，看看相关文档也好：LMDB TECHNICAL INFORMATION^[2]。

BoltDB^[3]

BoltDB 是参考 LMDB，并用 Go 语言实现的存储引擎。业界使用 BoltDB 的开源项目主要有 etcd^[4]、consul^[5] 等。

BoltDB 源码比较清晰，没有太多奇技淫巧，就是经典的 B+Tree 实现。性能上可能不够突出，不过胜在简单可靠。

目前，BoltDB 的原作者已经“放弃治疗”了，现在这个项目由 etcd 团队维护一个 fork 分支。

BerkeleyDB^[6]

不同于前面提到的 LMDB 和 BoltDB，BerkeleyDB 是一个 B-Tree 结构的存储引擎。关于 B-Tree 和 B+Tree 的差别，网上的资料很多，这里就不赘述。

BerkeleyDB 是一个比较历史悠久的项目。BerkeleyDB 的前身是伯克利加州大学为了移除受 AT&T 限制的代码，从 BSD 4.3 到 4.4 时所改写的软件。目前的代码由 Oracle 维护。

WiredTiger^[7]

WiredTiger 一个 B-Tree 存储引擎。2014 年，WiredTiger 被当时崛起的文档型数据库 MongoDB 收购。MongoDB 3.2 之后 WiredTiger 成为 MongoDB 的默认存储引擎。

其它

MySQL 的官方存储引擎 InnoDB^[8] 和 PostgreSQL 的存储引擎^[9] 也是优秀的 B+Tree 和 B-Tree 存储引擎。不过，因为关系数据库的复杂性，这两个存储引擎也比上面提到的几个存储引擎复杂不少。

参考资料