data-structures - 设计一个数据结构来保存大量数据

Question

我在一次采访中被问到以下问题，我无法解决任何对此问题的指示都会非常有帮助。

我有 100 个文件，每个文件大小为 10 MB，每个文件的内容都是一些映射到整数值的字符串。

string_key=整数值

 a=5
 ba=7
 cab=10 etc.. 

可用的物理 RAM 空间为 25 MB。如何设计数据结构:

For any duplicate string_key, the integer values can be added
Display the string_key=integer value sorted in a alphabetical format

约束:

All the entries of a file could be unique. All of the 10*1000MB of data could be unique string_key mapping to an integer value. 

解决方案 1:

我正在考虑一个接一个地加载每个文件并将信息存储在 HashMap 中，但是这个 HashMap 将非常庞大并且如果所有文件都包含唯一数据则 RAM 中没有足够的可用内存.

还有其他想法吗？

使用 noSqldb 不是一种选择。

Answer 1

这是我的尝试。基本上这个想法是使用一系列小的二叉树来保存排序的数据，动态创建并将它们保存到磁盘以节省内存，并使用链表对树本身进行排序。

手波版本:

创建一个二叉树，根据其条目的键按字母顺序排序。每个条目都有一个键和一个值。每棵树都有其第一个和最后一个键的名称作为属性。我们分别加载每个文件，并逐行插入一个条目到树中，树会自动对其进行排序。当树的内容大小达到 10 mb 时，我们将树分成两棵 5 mb 的树。我们将这两棵树保存到磁盘中。为了跟踪我们的树，我们保留了一组树及其名称/位置以及它们的第一个和最后一个属性的名称。从现在开始，对于 fileN 中的每一行，我们使用我们的列表来定位适当的树以将其插入，将该树加载到内存中，并执行必要的操作。我们继续这个过程，直到我们到达终点。

使用这种方法，加载到内存中的最大数据量不会超过 25 MB。总是有一个文件 N 被加载(10mb)，一个树被加载(最多 10mb)，以及一个树数组/列表(希望不会超过 5mb)。

稍微严谨一点的算法:

1. 初始化排序的二叉树 B其条目是 (key, value)元组，根据条目的属性排序 key并具有属性 name, size, first_key, last_key其中 name是一些任意的唯一字符串和 size是以字节为单位的大小。

2. 初始化一个排序链表L其条目是 (tree_name, first_key) 形式的元组根据条目的属性排序 first_key .这是我们的树木 list 。添加元组 (B.name, B.first_key)至 L .

3. 假设文件名为 file1, file2, ..., file100我们继续使用以下伪代码编写的算法，该伪代码恰好与 python 非常相似。 (我希望我在这里使用的未声明函数是不言自明的)

   for i in [1..100]:
       f = open("file" + i)   # 10 mb into memory
       for line in file:
           (key, value) = separate_line(line)
   
           if key < B.first_key or key > B.last_key:
               B = find_correct_tree(L, key)
   
           if key.size + value.size + B.size > 10MB:
               (A, B) = B.split()     # supp A is assigned a random name and B keeps its name
               L.add(A.name, A.first_key)
               if key < B.first_key:
                   save_to_disk(B)
                   B = A      # 5 mb out of memory
               else:
                   save_to_disk(A)
   
           B.add(key)
   save_to_disk(B)
   

然后我们只是遍历列表并打印出每个关联的树:

    for (tree_name, _) in L:
        load_from_disk(tree_name).print_in_order()

这有点不完整，例如要完成这项工作，您必须不断更新列表 L每次first_key变化;而且我还没有严格证明这在数学上使用了 25 mb。但我的直觉告诉我，这可能会奏效。可能还有比保持排序的链表(也许是哈希表？)更有效的方法来对树进行排序。