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

您可以以文件系统如何管理可变大小的文件为例。

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

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

这里唯一明显的碎片是内部的，即每个文件最后一块中浪费的空间。

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

Answer 2

首先实现一个映射器。每当您获得新字符串时，将它们按顺序存储在文件中，并将它们的位置存储在地图上。

Answer 3

对我来说，这听起来像是键/值存储的定义。你可以使用任何你喜欢的系统。从 Oracle 的 Berkeley DB 到 Cassandra 或 Riak。