database - 执行 : a string-to-string database

Question

就像std::unordered_map<std::string, std::string>但所有数据都应存储在磁盘上而不是内存中。

按照我的理解，应该做两部分:索引和存储。我已经学习了一些关于索引的数据结构，比如 Linear-Hash 或 B-Tree，并且编写一个磁盘上的 int->int 数据库并不太难。问题是存储。

对于整数，所有记录的大小相同。一旦我们通过索引获得记录的位置，我们就可以轻松地提取、修改或延迟删除。但对于字符串，记录的大小是灵活的。它应该(至少)有以下问题:

1. put() 更长的字符串:我们不能简单地覆盖旧记录，我们必须执行 del() 和 put()，旧记录的空间被浪费了。

2. del():旧记录的空间也被浪费了，不能再次使用。 (也许我们可以用垃圾收集器收集删除的空间，但它会花费额外的空间并产生碎片)

3. 对于 int->int 数据库来说，为几个整数浪费空间不是什么大问题。但是字符串越长，浪费的空间就越多。

我需要一些建议/提示来解决问题。

Answer 1

您可以举个例子，文件系统如何管理可变大小的文件。

它们以固定大小的 block 分配文件空间，每个 block 大约几千字节，并将这些 block 链接在一起以形成任意长度的整个文件。

如果你需要增加你的文件，你分配和链接更多的 block 。如果您需要缩小或删除它，您可以取消链接并释放一个或多个 block 。

这里唯一值得注意的碎片是内部碎片，即每个文件最后一 block 中的浪费空间。

如果你使用文件实现这个，其中每个 block 要么是潜在大文件的一部分，要么是它自己的文件，你不需要立即删除/释放它。您可以在您的控制/元数据中将其标记为免费，然后在以后重用。您可以将压缩(删除所有空闲 block )作为不经常执行的单独操作来实现。