c# - 过滤(可能)1.000.000+ 项的子集

Question

我有一个很大的数据集，其中可能有超过一百万个条目。所有项目都有分配的时间戳，并且项目在运行时添加到集合中(通常但不总是使用更新的时间戳)。我需要在给定的时间范围内显示此数据的子集。与总数据集相比，这个时间范围通常非常小，即在 1.000.000 多个项目中，给定时间范围内的项目不超过 1000 个。这个时间范围以恒定的速度移动，例如时间范围每秒移动一秒。此外，用户可以随时调整时间范围(在数据集中“移动”)或设置额外的过滤器(例如按某些文本过滤)。

到目前为止，我并不担心性能，而是试图把其他事情做好，并且只使用较小的测试集。我不太确定如何有效地解决这个问题，并且会很高兴收到每一份意见。谢谢。

编辑:使用的语言是 C# 4。

更新:我现在使用的是区间树，实现可以在这里找到: https://github.com/mbuchetics/RangeTree

它还有一个异步版本，使用任务并行库 (TPL) 重建树。

Answer 1

我们在开发中遇到了类似的问题 - 必须收集数百万个按某个键排序的项目，然后根据需要从中导出一页。我发现您的问题有点相似。

为此，我们调整了 red-black tree结构，通过以下方式:

• 我们向其中添加了迭代器，因此我们可以在 o(1) 中获取“下一个”项目
• 我们添加了从“索引”中查找迭代器，并设法在 O(log n) 中完成

RB Tree具有 O(log n) 插入复杂度，所以我猜你的插入会很好地适合那里。

迭代器上的

next()是通过添加和维护所有叶节点的链表实现的——我们原来采用的RB Tree实现不包括这一点。

RB Tree也很酷，因为它允许您根据需要微调节点大小。通过试验，您将能够找出适合您问题的正确数字。