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

Question

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

B树似乎是一个常用的结构，但主要用于固定长度的记录。与插入和删除相比，我还期望获得和更新的数量会大大增加。我可以摆脱B树的O（log m）查找吗？

我很高兴能成为一个组合系统，例如，ISAM结合了B树和线性文件存储，这似乎可以使其与可变长度记录一起使用。有更好的东西吗？

一些其他限制：

1）ID可能稀疏，但可以使它们以线性数字块出现-但范围较大（64位）

2）我不想使用DBMS，但针对我的特定问题的性能尚未证明非常好。我不需要完整的DBMS使用的任何操作，也不需要搜索。我需要可以轻松调整和优化的内容。称其为学术上的好奇心，如果它是MySQL所无法完成的，那我会用它，但我必须尝试并加快步伐。

3）数据集大于可容纳在内存中的数据集，但是如果索引与键，偏移量一样简单，则索引很可能适合于内存。我当然正在寻找大约10亿个实体或更多的存储空间。

4）理想情况下，删除记录时应恢复空间。那可能是通过压缩，但是我很想看看是否有更好的方法（例如，一个B树很容易恢复空间）。

Answer 1

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

自己动手的方式：使用协议缓冲区（或您选择的二进制格式）来定义B树节点和数据项结构。对数据库使用仅附加文件。要写入新记录或修改现有记录，您只需将记录本身写入文件末尾，然后写入任何已修改的B-Tree节点（例如，记录的父节点，

its父节点等等）直到根）。然后，将树的新根的位置写入文件开头的标头块中。要读取文件，您只需找到最新的根节点并像读取其他任何文件一样读取B树。这种方法有几个优点：

由于从未修改过写入的数据，因此读者无需锁定，就无需在开始阅读时根据根节点获得数据库的“快照”视图。
• 通过在节点和记录中添加“先前版本”字段，您可以从本质上免费访问数据库的先前版本。
• 与大多数支持修改的磁盘文件格式相比，它真的很容易实现和调试。
• 压缩数据库只需简单地读取数据和B-Tree的最新版本，然后将其写入新文件。

Answer 2

如果您的ID是数字并且不是很稀疏，则一种选择是在一个文件中使用一个简单的表（偏移量，长度），并引用另一个文件中的数据。这将使您可以进行O（1）查找，并且仅通过您的自由空间跟踪机制来绑定更新/插入/删除。

Answer 3

最好是使用商用数据库引擎。

您可以通过将索引（即{“逻辑ID”映射到“物理位置”}值对）存储在哈希映射中（散列在逻辑上，从而摆脱对B树的任何O（log m）查找。 ID）...，或者甚至将索引存储在连续的向量中（逻辑ID用作偏移值向量的索引），如bdonlan建议的那样，如果ID值不稀疏。

一个重要的实现细节可能是您用来访问索引的API：是否将其存储在RAM中（O / S随系统页面文件一起支持）并使用指针在进程中对其进行访问，和/或存储它放在磁盘上（O / S缓存在文件系统缓存中）并使用文件I / O API对其进行访问。

Answer 4

如果数据库对您来说很沉重，请考虑使用键值存储。

Answer 5

您可以基于长度可变的记录文件创建索引。