创建一个可增量更新的高效文件索引

Question

作为一个研究项目，我正在用Python从头开始写一个文档导向的数据库。这个数据库像MongoDB一样，支持在任意文档的键上创建索引。现在，这些索引是用两个简单的字典来实现的：第一个字典的键是被索引字段的值（可能是经过哈希处理的），而值是所有与这个字段值相关的文档的存储键，这样数据库就能在磁盘上找到这些文档。第二个字典则是反向的，也就是说，它的键是某个文档的存储键，而值是被索引字段的（哈希）值（这样在从索引中删除文档时会更高效）。举个例子：

doc1 = {'foo' : 'bar'} # store-key : doc1
doc2 = {'foo' : 'baz'} # store-key : doc2
doc3 = {'foo' : 'bar'} # store-key : doc3

对于foo字段，这些文档的索引字典看起来会是这样的：

foo_index = {'bar' : ['doc1','doc3'],'baz' : ['doc2']}
foo_reverse_index = {'doc1' : ['bar'],'doc2' : ['baz'], 'doc3' : ['bar']}

（请注意，反向索引也由值的列表组成[而不是单个值]，以便能够索引列表字段，这样列表字段中的每个元素都会单独包含在索引中）

在正常操作中，索引会保存在内存中，并在每次插入、更新或删除操作后实时更新。为了持久化，它会被序列化（例如，作为JSON对象）并存储到磁盘上，这对于索引大小达到几十万条记录是比较有效的。然而，随着数据库的增大，程序启动时加载索引的时间会变得很长，而且实时将更改写入磁盘几乎变得不可能，因为写入索引会产生很大的开销。

因此，我在寻找一种持久化索引的实现方式，这种方式可以高效地进行增量更新，换句话说，就是在将索引持久化到磁盘时不需要重写整个索引。对于解决这个问题，有什么合适的策略吗？我考虑过使用链表来实现一个可寻址的存储空间，以便可以在其中写入对象，但我不确定这是否是正确的方法。

Answer 1

我的建议主要是关于如何更新索引以保持数据的持久性；程序启动时多花一点时间其实并不算太大，而且也没法完全避免。

一种方法是提前为索引预留磁盘空间（可能也包括其他数据集合）。在预留空间时，你需要为索引中的每个条目定义一个经验值大小，以及整个索引在磁盘上的总大小。比如说，每个索引条目占用1024字节，总共可以有1000个条目。这样做的好处是可以直接访问磁盘上每个索引条目。你只需要在内存中存储索引的位置信息。每当你在内存中更新一个索引条目时，可以直接指向它在磁盘上的确切位置，只需重写那个条目。

如果第一个索引文件满了，就创建第二个文件；始终在磁盘上预留文件空间（1024*1000字节）。你也应该为其他数据预留空间，并选择使用多个固定大小的文件，而不是一个大文件。

如果有些索引条目需要超过1024字节的空间，那就为这些较大的条目创建一个额外的索引文件；比如每个条目2048字节，总共100个条目。最重要的是，使用固定大小的索引条目，以便能够直接访问。

希望这些对你有帮助。