5

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

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

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

一些进一步的限制：

1) ID 可能是稀疏的，但它们可以以线性数字块的形式出现 - 但范围很大（64 位）

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

3）数据集大于内存，但是如果索引像键，偏移量一样简单，它可能很适合内存。我当然正在研究存储中的 10 亿个或更多实体。

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

4

5 回答 5

11

最简单的方法：使用像 Berkeley DB 这样的东西。它为任意字节字符串提供键值存储，并为您完成所有艰苦的工作。如果您愿意，它甚至提供用于索引的“二级数据库”。

自己动手的方式：使用协议缓冲区（或您选择的二进制格式）来定义 B-Tree 节点和数据项结构。为您的数据库使用仅附加文件。要写入新记录或修改现有记录，只需将记录本身写入文件末尾，然后写入任何修改后的 B-Tree 节点（例如，记录的父节点、其父节点等直到根）。然后，将树的新根的位置写入文件开头的标题块。要读取文件，您只需找到最近的根节点并像在任何其他文件中一样读取 B-Tree。这种方法有几个优点：

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

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

于 2009-05-17T19:43:36.597 回答
0

最好的可能是使用商业数据库引擎。

您可以通过将索引（即 {"logical ID" maps to "physical location"} 值对）存储在哈希映射中（对逻辑 ID 进行哈希处理）来摆脱 B-tree 的任何 O(log m) 查找...或者，甚至，如果 ID 值不是稀疏的，则将索引存储在连续向量中（逻辑 ID 用作偏移值向量的索引），如 bdonlan 建议的那样。

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

于 2009-05-17T20:57:46.430 回答
0

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

如果您真的要自己实现它，请使用基于磁盘的哈希表或 B 树。为避免可变长度值的问题，请将值存储在单独的文件中，并使用 B 树作为数据文件的索引。删除值后的空间回收会很棘手，但它是可能的（例如，通过数据文件中释放空间的位集）。

于 2009-05-18T07:03:30.040 回答
0

索引可变长度记录文件。

索引可变长度记录文件可能看起来像一项艰巨的任务，但一旦您确定哪些是移动部分，它真的非常简单。

为此，您应该以固定大小的块（即 128、256 或 512 等）读取文件。您的记录还应该有一个易于识别的记录结束字符。这意味着该字符不能作为常规字符出现在您的记录中。

接下来是扫描文件以查找每条记录的开头，创建具有以下结构的索引文件：

key, 0, 0
........
........
key, block, offset

这里的key是您索引文件的键（字段）（可以是复合键）。block是记录开始的（从 0 开始的）块编号，offset是记录开始到块开始的（从0开始的）偏移量。根据您使用的块大小，您的记录可能跨越多个块。因此，一旦您找到记录的开头，您需要获取尽可能多的连续块来检索整个记录。

如果您需要搜索不同的条件，完全可以同时创建多个索引文件。

创建此索引文件后，下一步是按关键字段对其进行排序。或者，您可以使用插入排序机制，在创建索引文件时对其进行排序。

使用类似文件搜索的函数检索按该键排序的记录，在索引文件上查找键并检索其记录偏移量对。在这种情况下，二分搜索似乎表现得相当好，但您可以使用任何类型。

这种结构允许您的数据库接受记录的添加、删除和更新。在文件末尾进行添加，将其键添加到索引文件中。要删除记录，只需将记录的第一个字符更改为唯一字符，0x0然后从索引文件中删除条目。更新可以通过删除然后在文件末尾添加更新的记录来实现。

如果您打算处理非常大的文件，那么为索引使用类似B-Tree的结构可能会有很大帮助，因为B-Trees 索引不需要完全加载到内存中。B-Tree 算法进一步将索引文件划分为页面，然后根据需要将这些页面加载到内存中。

于 2019-12-27T13:01:31.790 回答