代码之家 › 专栏 › 技术社区 › George Shuklin

保存聚合网络流数据的数据结构

netflow data-structures

0

George Shuklin · 技术社区 · 12 年前

是否有标准的方法来保存网络流数据(按端口和目标IP聚合,按源IP区分)?

数据输入:netflow数据(源IP、时间戳、八位字节),更新非常频繁

请求输入:IP,范围(两个时间戳)

请求输出:八位字节数

是否可以获得O(log(n))或更好的数据存储和请求?怎样

1 回复 | 直到 12 年前

1

Bernhard Barker 12 年前

有一个 (hash) map IP到 binary search tree 按时间戳索引。

为了有效地计算二进制搜索树中两个节点之间的元素数,可以让每个节点在其左侧子节点的子树中存储节点数(类似于 a rope ,然后可以确定BST中开始和结束时间戳的索引,并给出其间的元素数。

映射查找预期为O(1),BST查询每个为O(log n),总计为O(logn)。