DBDB: 一个简单的key/value数据库（一）

编译自：http://www.aosabook.org/en/500L/dbdb-dog-bed-database.html 作者：Taavi Burns 翻译：鸿 如有翻译问题或建议，请公众号留言

导论 DBDB（Dog Bed Database）是基于Python实现的key/value数据库。 它将key值与value值关联，并将该关联存储在磁盘上方便检索。DBDB可以在服务器崩溃或者发生错误的情况下保存数据，并且也避免了所有数据都保存在内存中，因此它可以存储比服务器内存更多的数据。

DBDB解决的三个问题 如果您的文件系统空间不足，会发生什么情况？ 如果服务器在保存数据时死机会发生什么？ 如果你的数据大小超过可用内存呢？

DBDB的特点 数据库的特点可以用ACID来描述：原子性，一致性，隔离性和持久性。DBDB中的数据更新具有原子性和持久性。但是DBDB不提供一致性保证，因为它没有对存储的数据施加限制。同样的，隔离性也没有实现。当然，应用程序可以使用属于它自己的一致性保证，但隔离性则需要专门的事务管理器。除此以外，还有其它的问题存在。例如，DBDB不会处理老数据，因此重复更新（即使是相同的key值）最终都会消耗掉所有的磁盘空间。

俯瞰DBDB DBDB分为逻辑层（数据结构：二叉树），物理层（如何在磁盘上存储数据）以及接口API（key值与value值的具体内容）几层。

代码架构 下面的模块是按终端用户的使用频率进行降序排序的，换句话说，第一个模块是用户了解的最多的模块，而最后一个模块与终端用户没有什么交集。

• tool.py：一个用于从终端窗口使用数据库的命令行工具。
• interface.py：定义了类（DBDB），它基于二叉树实现了Python字典数据结构。
• logical.py：逻辑层。它是一个key值/value值存储的抽象接口。LogicalBase为数据更新提供了接口（如get，set和commit），并且对锁进行管理和回收内部节点引用。ValueRef是一个引用存储在数据库中的二进制Blob的Python对象，可以避免将所有数据一次性加载到内存中。
• binary_tree.py：在逻辑层之下定义了一个具体的二叉树算法。BinaryTree提供了二叉树的具体实现，其中包含读取，插入和删除key/value的方法。 BinaryTree是一棵函数式的不变的二叉树;更新是通过返回一个与旧树共享公共结构的新树来实现的。 BinaryNode实现了二叉树的一个节点。BinaryNodeRef是一个特殊的ValueRef，它知道如何对BinaryNode进行序列化和反序列化。
• physical.py：定义了物理层。 Storage类提供持久，（往往是）仅追加记录的存储。