algorithm - 我有 100 万亿个元素，每个元素的大小从 1 字节到 1 万亿字节 (0.909 TiB) 不等。如何非常有效地存储和访问它们？

Question

这是一道面试题:

Suppose: I have 100 trillion elements, each of them has size from 1 byte to 1 trillion bytes (0.909 TiB). How to store them and access them very efficiently ?

我的想法:他们想测试有关有效处理大量数据的知识。这不是一个唯一正确答案的问题。

将它们保存到一些特殊的数据结构中？

其实我对这种开放式问题没什么想法。

非常感谢任何帮助。

Answer 1

这实际上取决于所讨论的数据集。我认为重点是让您讨论备选方案并描述各种优缺点。

也许你应该用更多的问题来回答他们的问题!

• 需要如何访问它？ (按顺序、随机、某种可预测的分布？)
• 元素的顺序重要吗？
• 元素的大小会改变吗？
• 插入/删除性能有多重要？

您选择的数据结构将取决于您愿意做出什么样的权衡。

例如，如果您只需要按顺序迭代集合，也许您应该使用链表，因为它的存储开销相对较小。

如果您需要随机访问，您可能需要查看:

• 哈希表(恒定时间查找，但需要一个良好的数据哈希函数)
• 某种索引/树结构？
• 缓存!您可能无法将所有内容都保存在内存中 - 即使可以，您也希望尽可能利用数据局部性。

TL;DR:这完全取决于问题。有很多选择。

这本质上与文件系统/数据库面临的问题相同。