在重叠时找到重叠间隔很少见

Question

我有一个巨大的数据库表,有n个整数区间(例如{1-5},{4-16},{6434-114343}),需要找出哪些区间相互重叠.在SO上有很多 类似的问题,但不同之处在于我需要分别为每个区间返回一组重叠区间.

      ------------------ A -------------------
    ------ B -------               ----- D -----
          --------- C --------- 

对于这个例子,输出将是 A:{B,C,D} B:{A,C} C:{A,B} D:{A}

最坏的情况是,所有间隔可能相互重叠,产生大小为O(n ²)的输出.这并不比天真的解决方案好(比较每对间隔).然而,在实践中,我知道我的间隔很少会与其他间隔重叠,当它们发生时,最多只有5个其他间隔.

鉴于此信息,我该如何解决问题？(最好,我想要一个SQL查询解决方案,因为数据在数据库中,但我认为只有常规的算法解决方案是可能的.)

Answer 1

针对您的问题的典型编程解决方案是在所有范围之外构建间隔树,然后每个间隔执行一次查找,从而为您提供所有交叉时间间隔的列表O(log n).以下是这种间隔树的样子:

但是,在您的情况下,您也会将主键存储在树节点中,因此给定以下日期(查找重叠日期是可以使用间隔树解决的常见问题)

你的树看起来像这样

因此,如果我想知道哪些区间与C重叠,我会搜索C的开始,1843,树告诉我,这个值只在区间C内,这是我正在测试的区间,所以我可以忽略它.然后我搜索C,1907的结尾,树告诉我,它在区间A,B和C中,我再次忽略C,因此我的结果集是A和B.

我承认,在这样一棵树中的查找并不像人们所期望的那样直观.我会尝试在这里尽可能好地解释它:你从顶部根节点开始,每个节点决定向左或向右走,直到你到达一个离开节点(一个没有子节点的节点).如果节点值大于您要搜索的值,则向左移动.如果节点值小于您要搜索的值,则转到右侧.如果节点值完全等于您要搜索的值,该怎么办？这取决于!如果您正在搜索间隔的开始,则相等的值意味着您向右移动,如果您搜索间隔的结束,则相等的值意味着您向左移动.这是非常重要的.到达离开节点后,您就完成了,并且在前往该离开节点的任何节点中找到的所有间隔,包括存储在离开节点本身的间隔(如果有)构成了结果集,而不仅仅是存储的间隔在离开节点.这意味着您必须收集在执行搜索时遇到的任何间隔.

现在回到最初的问题:这一切都可以在SQL中完成吗？是的,可以做到.不过,我不确定你是否真的想这样做.您可以将当前SQL表数据转换为表示间隔树的SQL表,然后直接在该间隔树表中执行查找.至少我找到了那样做的人.他试图找到覆盖给定日期的所有日期范围,而不必将日期与数据库中的所有现有范围进行比较:

静态关系区间树

他甚至使用了一个漂亮的技巧来优化查找速度,显着降低CPU使用率,构建查找表和执行实际查找(这使得整个事情变得非常复杂).