我有100万亿个元素,每个元素的大小从1字节到1万亿字节(0.909 TiB).如何存储和访问它们非常有效？

Question

这是一个面试问题:

假设:我有100万亿个元素,每个元素的大小从1字节到1万亿字节(0.909 TiB).如何存储和访问它们非常有效？

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

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

实际上我对这种开放式问题没有任何想法.

任何帮助都非常感谢.

Answer 1

这实际上取决于所讨论的数据集.我认为关键在于您讨论替代方案并描述各种利弊.

也许你应该回答更多问题!

• 它将如何被访问？(顺序,随机,一些可预测的分布？)
• 元素的顺序是否重要？
• 元素的大小会改变吗？
• 插入/删除性能有多重要？

您选择的数据结构取决于您愿意做出的权衡取舍.

例如,如果您只需要按顺序遍历集合,也许您可​​以使用链表,因为它具有相对较小的存储开销.

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

• 散列表(常量时间查找,但需要一个良好的数据散列函数)
• 某种索引/树结构？
• 缓存!您可能无法将其全部保留在内存中 - 即使您可以在可能的情况下利用数据位置.

TL; DR:这一切都与问题有关.有很多选择.

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