如何根据键和时间间隔高效地查找 parent 条记录？

Question

定义

一条 parent 记录的类型为 'P'，一个祖先键，一个日期间隔。

其 child 记录具有类型 'C'，一个相同的祖先键，并且具有匹配或落在其 parent 的间隔内的日期间隔。

• 所有记录都是唯一的
• Parent 记录可以共享相同的祖先键，但它们的日期间隔 不能重叠
• 一个parent条记录可以有很多child条记录

例子

Parent条记录可以是：

• P, 12345, (1000-01-01, 1000-12-31)
• P, 12345, (1001-01-01, 1001-12-31) // 没有重叠日期，有效

第一个 parent 记录的有效 children 可以是

• C, 12345, (1000-01-01, 1000-12-31) // 匹配所有内容，有效
• C, 12345, (1000-05-05, 1000-09-09) // 匹配祖先键，在parent的日期间隔内，有效

问题

给定一组包含 parents 和 children 的随机记录，我如何有效地将集合分为不同的组，包括一个唯一的 parent 及其有效的 children 基于键和时间间隔?

保证每个child，只有一个parent。但有可能 parent 没有任何 children.

暴力破解

以线性时间识别所有 parent 记录。然后遍历它们并在平方时间内成对匹配所有其他记录。

问题

有没有更快的方法？

Answer 1

最简单的方法是制作一个P记录列表和一个C记录列表，然后将它们都按(ancestor_key, interval.start)

排序

然后遍历 parents 列表，对于每个 parent，从 child 列表中提取它的 children。由于排序，parent 和 child 列表将按相应的顺序排列，因此两个列表中感兴趣的位置只会向前移动。

总复杂度为 O(n log n)，由排序决定。