data-structures - 数据结构以保持聚合的网络流数据

Question

是否有任何标准方法来保存 netflow 数据（按端口和目标 IP 聚合，按源 IP 区分）？

数据输入：netflow数据（源IP、时间戳、八位字节），更新非常频繁

请求输入：IP、范围（两个时间戳）

请求输出：八位字节数

是否有可能获得 O(log(n)) 或更好的数据存储和请求？如何？

Answer 1

将 IP的（散列）映射到按时间戳索引的二叉搜索树。

为了有效地计算二叉搜索树中两个节点之间的元素数量，您可以让每个节点存储其左子树的子树中的节点数（类似于绳索，然后您可以确定 BST 中的索引开始和结束时间戳，为您提供介于两者之间的元素数量。

地图查找预计 O(1)，BST 查询每个 O(log n)，总共 O(log n)。