java - 实现范围索引，以便在时间复杂度方面非常有效地计算包含集

Question

这是我在这种形式的数据库中的数据集(56, 102, 数据 1)(61, 106, 数据 2)(45, 200, 数据 3)....百万行假设我有内存来管理 JVM 堆中的这些数据。

给一个范围 (60,100) 它应该找到包含它的范围...比如 (56,102) 和 (45,200)，避免全扫描的最佳算法是什么。是否有任何框架可以自然地为我索引数据以执行包含搜索。当然，我可以将它存储在 RDBMS 中并使用 SQL 获取它。是否有纯 Java 解决方案？

Answer 1

您可以尝试构建一个 https://en.wikipedia.org/wiki/Interval_tree

引用维基百科:

结果是一个三叉树，每个节点存储:

A center point
A pointer to another node containing all intervals completely to the left of the center point
A pointer to another node containing all intervals completely to the right of the center point
All intervals overlapping the center point sorted by their beginning point
All intervals overlapping the center point sorted by their ending point

(结束引用)

给定一个范围，如果你从顶部递归搜索这棵树，你可以丢弃很多节点。如果中心点在你的查询范围之外，你只需要调查与查询范围同侧的 child 。如果中心点在查询范围内，那么两个 child 都不包含任何包含中心点的区间，因此它们不能包含任何包含范围的区间(因为它确实包含中心点)所以你不需要担心任何一个 child 。

对于您访问的任何节点，您需要遍历已排序的间隔列表之一，但您可以选择哪一个。如果中心点小于大部分(或全部)查询范围，那么我会选择按端点排序的间隔列表，并从大到小处理它。在此列表的开头，您会发现的大部分或所有间隔都包含查询范围，一旦发现终点小于查询范围的末尾，您就可以停止遍历列表。

我不能保证会有改进，因为您查看的节点中可能堆积了很多无用的间隔，但根据您的数据，您可能会在实践中获得加速。