1

好的，到目前为止，我一直在主内存中开发一个系统，该系统具有许多不同的对象，每个对象都存储系统中其他对象的列表。现在我想将其移至持久存储。我不是在寻找使用 DBMS 的明显答案，因为重点是我正在为我的系统编写自定义数据库。

现在为每个对象分配一个 ID。可以在表中查找 id，以找到该对象的数据位置的块和偏移量。现在每个对象都有指向系统中其他对象的列表/集合。所以很明显，在存储中，它们将是 8 字节的列表（使用 long 作为 id）id，可用于查找其他对象。现在我的问题是，我知道这些列表会随着时间的推移而增长，因此它们需要增长空间。到目前为止，我存储列表以便在对象增长时不需要在对象周围移动的最佳想法是为每个列表分配一个 id，就像对象一样，以便它们可以像要查找的对象一样在表中查找它们在磁盘上。

现在每个列表部分将有一组分配的空间来存储 10 个对象，然后如果它包含更多对象，最后将是下一个列表部分的 id。这似乎是一种不错的方法来处理不断增长的对象，但我想知道是否有更好的方法。我会将索引存储在内存中（空间允许），因此给定一个对象 id，查找在内存中，然后需要 1 个 I/O 才能找到从磁盘获取它的数据和列表 id。然后对于您要遍历的每个列表，如果块被缓存，则列表中的每 10 个对象或更少的对象将进行另一次查找和 I/O。

I/O 的数量并不可怕，我会尝试保持列表部分的局部性以消除不必要的 I/O，但是有更好的方法吗？我是否应该尝试将列表与对象分开存储，或者我应该考虑将它们与对象数据一起存储的方法。我对此的担心是，随着一个列表的增长，它会进入另一个列表，然后需要被分割，这可能会变得更加复杂。任何建议表示赞赏并提前感谢。

4

1 回答 1

1

您拥有这些可扩展列表的想法很好。我认为您的解释缺少一些细节（即：有序列表与否，尝试将列表与对象分开是什么意思，这些列表的图表可能会有所帮助）。

我会在内存中保留一个排序索引以便快速访问。索引将具有列表 ID 和磁盘上的位置。如果您对范围查询感兴趣，请使用 B 树方法，否则您可以使用哈希图来存储这些索引。

如果您在列表上进行搜索，进一步的改进是保持它们排序......或至少半排序，以便您可以将相似的列表分组在同一个块中。如果您经常缓存到内存中说每个块的边界（值为 b/w 1-9、10-25 等的节点），这将加快在列表中的搜索速度。合并排序可能是列表的最佳排序。甚至更好的是，当您在列表中插入节点时，插入正确的位置，以便列表始终排序。然后用二分查找查找。如果数据未正确索引且未排序，您将多次访问磁盘进行查询，在这种情况下，由于磁盘时间，您使用的任何搜索都会为您提供线性时间。

您还可以缓存 10% 最常查找的节点/列表的数据节点。

根据这些列表的大小（以及您拥有的多少个块），您可以使用一些 RAID，以便获得一些并行读/写。

于 2011-12-14T15:15:35.663 回答