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

Question

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

B树似乎是一个常见的引用结构,但主要用于固定长度记录.我也期望获得和更新的次数比插入和删除的次数多得多.我可以摆脱B树的O(log m)查找吗？

我很高兴它成为一个组合系统,例如ISAM结合了B树和线性文件存储,看起来它可以作为一种方法使用可变长度记录.还有更好的东西吗？

进一步的限制:

1)ID可能是稀疏的,但可以使它们成为线性数字块 - 但是在大范围内(64位)

2)我不想使用DBMS,性能对于我的特定问题并没有证明是非常好的.我不需要完整DBMS使用的任何操作,我不需要搜索.我需要一些可以轻松调整和优化的东西.称之为学术好奇心,如果它由MySQL执行,那么我将使用它,但我必须尝试更快.

3)数据集大于可以适合内存的数据集,但是如果它像key,offset一样简单,那么索引可能很好地适合内存.我当然在寻找存储中10亿个或更多实体的东西.

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

Answer 1

简单的方法:使用像Berkeley DB这样的东西.它为任意字节字符串提供键值存储,并为您完成所有艰苦工作.如果需要,它甚至可以为索引提供"辅助数据库".

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

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

Answer 2

如果您的 ID 是数字并且不是很稀疏，一种选择是在一个文件中使用一个简单的（偏移量、长度）表，引用另一个文件中的数据。这将使您的查找时间复杂度为 O(1)，并且更新/插入/删除仅受您的自由空间跟踪机制的约束。