设计一个支持海量数据存储和查询的系统
面试官要求我设计一个存储千兆字节数据的系统，系统也必须支持某种查询。
描述：
在IDC中生成大量记录，每个记录由URL，访问URL的IP以及访问发生的时间组成。 该记录可能被声明为这样的结构，但我不确定应该选择哪种数据类型来代表它们：
struct Record { url; //char * IP; //int? visit_time; //time_t or simply a number? } 要求：
设计一个存储1000亿条记录的系统，系统至少支持2种查询：
首先，给定时间段（t1，t2）和IP，查询该IP在给定时间段内访问了多少URL。
其次，给定时间段（t1，t2）和URL，查询该URL被访问的次数。
我被绊倒了，这是我的愚蠢解决方案：
分析：
因为每个查询都是在给定的时间段内执行的 ，所以：
1. 创建一个集合 ，将所有访问时间放入集合中，并根据从旧到最新的时间值保持集合的顺序。
2. 使用散列（visit_time）作为键创建散列表，该散列表称为时间散列表，然后特定桶中的每个节点 具有分别指向另外2个散列表的2个指针 。
另外两个哈希表是ip-hash-table和url-hash-table 。
ip-hash-table使用hash（ip）作为密钥，同一ip-hash-table中的所有ips具有相同的访问时间;
url-hash-table使用hash（url）作为密钥，同一url-hash-table中的所有url都具有相同的访问时间。
给出如下图纸：
time_hastbl [] [] []-->[visit_time_i]-->[visit_time_j]...[visit_time_p]-->NIL [] | | [] ip_hastbl url_hastbl [] [] : : [] [] [] []
所以，在（t1，t2）上进行查询时：
-
从时间设置中找到最接近的匹配，假设匹配为（t1’，t2’），则所有有效访问时间将落入从t1’到t2’开始的集合部分;
-
对于时间集[t1’：t2′]中的每个访问时间t，执行hash（t）并找到t的ip_hastbl或url_hastbl，然后计算并记录给定ip或url出现的次数。
问题：
我的解决方案很愚蠢，希望你能再给我一个解决方案。
2.关于如何将大量记录存储在磁盘上，有什么建议吗？ 我想到了B-tree，但是如何使用它或者B-tree适用于这个系统？
我相信面试官期待一个基于分布式计算的解决方案，特别是涉及“1000亿条记录”时。 由于我对分布式计算的了解有限，我建议你研究一下Distributed Hash Table和map-reduce （用于并行查询处理）
在我看来，创建一个B +树使用时间作为关键，以帮助您快速定位磁盘中给定时间段（t1，t2）内的记录范围。 然后使用（t1，t2）期间的记录分别构建IP和URL哈希表。
老问题，但最近碰到了这里还有一些其他需要考虑的事情：
假设您没有其他索引，您需要考虑的是除了列出的要求之外的一些非常简单的边界限制：
首先，给定时间段（t1，t2）和IP，查询该IP在给定时间段内访问了多少URL。
如果你有10k用户，那么在最坏的情况下，你可以预期在一个时间窗口中扫描所有记录将导致只需要返回10k记录（平均）。
其次，给定时间段（t1，t2）和URL，查询该URL被访问的次数。
根据您在系统中有多少url说1000，这再次意味着简单的扫描会导致扫描的1000条记录中有999条未被返回。
假设您只有100,000个唯一的URL，可以大大减少数据库占用的空间（通过使用guid / int外键），这也意味着在100Bn记录上访问平均URL的次数是1M次。
即便如此，它也完全没有告诉我们，因为我们没有关于记录在给定搜索时间内如何按时间聚集的数字/统计数据。 我们每秒收到1000页请求并搜索12个月的时间范围，或者我们每秒获得100个请求并搜索1小时的时间块（360k请求）。
假设100Bn代表12个月的数据，即每秒3170个请求。 这听起来合理吗？
为什么这很重要？ 因为它突出了你在答案中忽略的一个关键因素。
在过去的12个月里有100Bn的记录，这意味着在12个月的时间里你将有200Bn的记录来处理。 如果1000亿条记录是20年，那么这不是一个问题，未来5年你可能会再增加25-30亿美元……但你现有的数据不太可能在这么长的时间内完成。
您的解决方案只回答方程式的一侧（读取数据），您不会考虑编写那么多数据的任何复杂性。 绝大多数情况下，您将数据插入到您创建的任何数据存储中，它是否能够每秒处理一个恒定的3k插入请求？
如果您插入3k记录，并且每条记录只是3x 64位整数，表示时间（以刻度表示），IP地址和URL的外键。 那么只有~75kb / s的写入数据，维护得很好。 如果假定每个URL都是唯一的，那么由于IO速度（忽略空间要求），您可能很容易遇到性能问题。
面试官有兴趣看到的另一件事是你对支持IPv6的看法。
最后，如果您提供了类似于您的解决方案，那么面试官应该提出后续问题。 “如果我现在想知道特定IP地址上次访问特定url的时间，您的系统将如何执行？”
所以，是的，如果您不了解MapReduce和其他分布式处理查询系统，那么您的应该是一个合理的答案。
它将是一个间隔树，也是一个B树。 区间树，因为所有查询仅作为时间间隔输入，而B-Tree由于输入的大小（数十亿）。