创建基于磁盘的数据结构

Question

我找不到关于此主题的任何资源。有几个问题的答案很好，描述了需要将数据存储在磁盘上的问题的解决方案（pickle、shelve、一般的数据库），但我想学习如何实现我自己的。

1) 如果我要在 Python 中创建一个基于磁盘的图形结构，我必须通过写入磁盘来实现必要的方法。但是我该怎么做呢？

2) 基于磁盘的结构的好处之一是在处理可能不适合内存的数据时具有结构的效率。如果数据不适合内存，一次只能访问其中的某些部分。如何一次只访问结构的一部分？

Answer 1

你可以从一些事情开始 simple。假设您将图表存储在字典中：

#!/usr/bin/env python2
# coding: utf-8

def read(filename):
    """
    Read a graph from a file. Returns a dictionary.
    The file must be in the format:

    SRC DST DST ...
    SRC DST
    ...

    where SRC and DST are names of nodes.
    Node names must not contain whitespace.
    """
    g = {}
    with open(filename) as handle:
        for line in handle:
            line = line.strip()
            if line == "":
                continue
            parts = line.split()
            src, targets = parts[0], parts[1:]
            if src not in g:
                g[src] = set()
            for target in targets:
                g[src].add(target)
    return g

def write(filename, g):
    """ Write dictionary `g` to file. """
    with open(filename, "w") as handle:
        for src, targets in g.iteritems():
            handle.write("%s %s\n" % (src, " ".join(targets)))

用法示例：

if __name__ == '__main__':
    g = {
        "A": ["B", "C"],
        "B": ["D"],
        "C": ["B"],
    }
    write("test.g", g)
    g = read("test.g")
    print(g) # {'A': set(['C', 'B']), 'C': set(['B']), 'B': set(['D'])}

以上定义了一个简单的图序列化格式，并实现了读写方法。虽然效率很低，但您可以单独使用这两种方法创建、更新和更改图形并将它们保存到磁盘。

这会将整个图形存储在内存中。作为下一个优化，您可以编写方法 - 例如read_node(filename, nodename) 只会将给定节点加载到内存中。这样，您可以存储和使用比可用内存更大的图形。

这当然仍然很低效，因为您需要读取整个文件才能找到您要查找的节点。

然后您可以添加进一步的优化，例如存储排序的数据并使用二进制搜索快速查找具有给定名称的节点。或者您将附加数据存储在图形数据中以用于索引目的。您可以将一个小索引加载到内存中，查找您关心的节点，然后查找存储数据的位置并只读取相关块。

等等。经过大量探索后，您可能会得到更高级的数据结构，例如 B-trees, Log-structured merge-trees or inverted indices.

Answer 2

你有很多问题要解决，有些很简单，有些比较复杂，但既然你想自己做，我认为你不介意自己填写细节（所以我会跳过一些部分）。

第一个简单的步骤是序列化和反序列化节点（以便能够完全存储在磁盘上）。这可以通过让您的节点具有 serialize/deserialize 方法以临时方式完成 - 此外，您可能希望序列化数据具有类型指示符，以便您可以知道哪个 class' deserialize 你应该用来反序列化数据。请注意，节点在磁盘上的表示必须通过文件偏移量（直接或间接）引用其他节点。

实际读取或写入数据是通过普通（二进制）文件操作完成的，但您必须先在文件中查找到正确的位置。

第二步是可以在文件中分配space。如果你只想有一个写一次的行为，那么只需要增加文件就可以了，但是如果你想修改文件中的数据（添加和删除节点甚至替换它们）你将不得不处理这样的情况文件中不再使用的区域并重新使用这些区域，甚至打包文件的布局。

进一步的步骤可能涉及在某种意义上使更新原子化。一种解决方案是有一个区域，您可以在其中写入足够的信息，以便更新可以完成（或放弃），如果它以最简单的形式过早终止，它可能只是一个幂等操作列表（如果操作会产生相同的结果）你重复它们，fx 将特定数据写入文件中的特定位置）。

请注意，虽然（某些）内置解决方案确实可以处理写入和读取整个图 to/from 磁盘，但它们并不能真正处理您只想读取部分图或修改图的情况图非常有效（你必须阅读整个图并一次性写出完整的图）。数据库是个例外，您可以随机 read/write 较小的数据部分。

创建基于磁盘的数据结构

Creating a disk-based data structure

python

file

disk

data-structures