我正在寻找一种适用于基于大型块的设备（例如机械硬盘驱动器）的算法/数据结构，该结构针对插入、获取、更新和删除进行了优化，其中搜索始终使用数据的 id 进行，并且数据在何处任何 ID 的字段都有可变长度。
B-Tree 似乎是一种常用的结构，但主要用于固定长度的记录。我还期望获取和更新比插入和删除要多得多。我可以摆脱 B 树的 O(log m) 查找吗？
我很高兴它是一个组合系统，例如 ISAM 组合了 B 树和线性文件存储，看起来它可以作为一种方法来处理可变长度记录。还有更好的吗？
一些进一步的限制：
1) ID 可能是稀疏的，但可以将它们制成线性数字块 - 但范围很大（64 位）
2）我不想使用DBMS，我的特定问题的性能还没有被证明很好。我不需要完整的 DBMS 使用的任何操作，我不需要搜索。我需要一些可以轻松调整和优化的东西。称之为学术好奇心，如果 MySQL 无法胜任，那么我会使用它，但我必须尝试更快。
3）数据集比内存大，但是如果索引像键、偏移量一样简单，那么索引可能很适合内存。我当然会在存储中查看大约 10 亿个或更多的实体。
4) 理想情况下，删除记录时应恢复空间。这可能是通过压缩来实现的，但我有兴趣看看是否有更好的方法（例如，B 树可以轻松恢复空间）。
简单的方法：使用 Berkeley DB 之类的东西。它为任意字节字符串提供键值存储，并为您完成所有艰苦的工作。如果您需要的话，它甚至还提供用于索引的“辅助数据库”。
DIY 方式：使用 Protocol Buffers（或您选择的二进制格式）来定义 B 树节点和数据项结构。对数据库使用仅附加文件。要写入新记录或修改现有记录，只需将记录本身写入文件末尾，然后写入任何修改的 B-Tree 节点（例如，记录的父节点、its父节点，依此类推直到根）。然后，将树的新根的位置写入文件开头的标头块。要读取该文件，您只需找到最近的根节点并像读取任何其他文件一样读取 B 树。这种方法有几个优点：
- 由于写入的数据永远不会被修改，因此读取器不需要锁定，并根据开始读取时的根节点获取数据库的“快照”视图。
- 通过将“先前版本”字段添加到节点和记录中，您基本上可以免费访问数据库的先前版本。
- 与大多数支持修改的磁盘文件格式相比，它确实很容易实现和调试。
- 压缩数据库只需读出最新版本的数据和 B-Tree 并将其写入新文件。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
