就像std::unordered_map<std::string, std::string>
但所有数据都应该存储在磁盘上而不是内存中。
据我了解,应该做两部分:索引和存储。我已经学习了一些关于索引的数据结构,例如 Linear-Hash 或 B-Tree,并且编写磁盘上的 int->int 数据库并不太难。问题是存储。
对于整数,所有记录的大小相同。一旦我们通过索引获得要记录的位置,我们就可以轻松地提取、修改或延迟删除。但是对于字符串,记录的大小是灵活的。它应该(至少)有以下问题:
put() 更长的字符串:我们不能简单地覆盖旧记录,我们敢于执行 del() 和 put() 并且旧记录的空间被浪费了。
del():旧记录的空间也被浪费了,不能再使用了。(也许我们可以用垃圾收集器收集已删除的空间,但它会花费额外的空间并产生碎片)
对于 int->int 数据库,为几个整数浪费空间并不是什么大问题。但是一个字符串更长,它会浪费更多的空间。
我需要一些建议/提示来解决问题。