algorithm - 用于可变长度记录存储和仅在主键上搜索的磁盘上查找的数据结构/算法

Question

我正在寻找一种适用于基于大块的设备(例如机械硬盘驱动器)的算法/数据结构，它针对插入、获取、更新和删除进行了优化，其中搜索始终使用数据的 ID 和其中任何 ID 的数据字段都具有可变长度。

B-Tree 似乎是一种普遍引用的结构，但主要用于定长记录。我还期望比插入和删除操作多得多的获取和更新操作。我可以摆脱 B 树的 O(log m) 查找吗？

我很高兴它是一个组合系统，例如 ISAM 结合了 B 树和线性文件存储，看起来它可以作为一种方法处理可变长度记录。还有更好的吗？

一些进一步的限制:

1) ID 可能是稀疏的，但可以将它们制成线性数字 block - 但范围很大(64 位)

2) 我不想使用 DBMS，我的特定问题的性能证明不是很好。我不需要完整的 DBMS 使用的任何操作，我不需要搜索。我需要一些我可以轻松调整和优化的东西。称之为学术好奇心，如果 MySQL 无法执行，那么我会使用它，但我必须尝试更快。

3) 数据集大于内存，但索引可能很适合内存，如果它像键、偏移量一样简单。我当然希望存储 10 亿个或更多的实体。

4) 理想情况下，删除记录时应恢复空间。这可能是通过压缩，但我有兴趣看看是否有更好的方法(例如 B 树可以轻松恢复空间)。

Answer 1

简单的方法:使用 Berkeley DB 之类的东西。它为任意字节字符串提供键值存储，并为您完成所有艰苦的工作。如果需要，它甚至可以提供用于索引的“辅助数据库”。

自己动手的方法:使用 Protocol Buffers(或您选择的二进制格式)来定义 B-Tree 节点和数据项结构。为您的数据库使用仅附加文件。要写入新记录或修改现有记录，只需将记录本身写入文件末尾，然后写入任何修改的 B-Tree 节点(例如，记录的父节点，它的父节点, 依此类推直到根)。然后，将树的新根的位置写入文件开头的头 block 。要读取该文件，您只需找到最近的根节点并像读取任何其他文件一样读取 B-Tree。这种方法有几个优点:

• 由于写入的数据永远不会被修改，因此读取者无需锁定，也无需在开始读取时获取基于根节点的数据库“快照” View 。
• 通过向您的节点和记录添加“先前版本”字段，您基本上可以免费访问先前版本的数据库。
• 与大多数支持修改的磁盘文件格式相比，它非常容易实现和调试。
• 压缩数据库包括简单地读取最新版本的数据和 B-Tree，并将其写入新文件。