2

我们有这样一个场景：

  • 数百万条记录（记录 1、记录 2、记录 3...）
  • 划分为数百万个不相交的小组（A 组、B 组、C 组...）
  • 成员资格会随着时间逐渐改变，即一条记录可能会重新分配给另一个组。

我们正在重新设计数据模式，我们需要支持的一个用例是给定一条特定记录，查找在给定时间点属于同一组的所有其他记录。或者，这可以被认为是两个单独的查询，例如：

  1. 三年前，记录 15544 属于哪个组？（将此组称为 g）。
  2. 三年前，哪些记录属于g组？

假设我们使用关系数据库，记录和组之间的关联很容易使用记录 id 和组 id 的两列表来建模。允许历史查询的常用方法是添加时间戳列。这使我们可以如下回答上述问题：

  1. 查找记录 15544 的行，该行具有给定日期之前的最新时间戳。这告诉我们 Group g。
  2. 查找在任何时候都属于组g的所有记录。
  3. 对于这些记录中的每一个，找到在给定日期之前具有最新时间戳的行。如果这表明该记录当时在组g中，则将其添加到结果集中。

这还不错（假设该表由记录 id 和组 id 分别索引），甚至可能是刚刚描述的朴素表结构的最佳算法，但它确实需要对步骤 2 中找到的每条记录进行索引查找.是否有可以更有效地回答查询的替代数据结构？

ETA：这只是系统的几个用例之一，所以我们不希望以降低对当前分组的查询为代价来加速这个查询，也不希望在空间消耗等方面付出巨大的代价.

4

1 回答 1

1

如何创建两个表：

  1. (recordID, time-> groupID) - key 是 recordID, time - 按 recordID 排序，次要按时间 (Let that be map1)
  2. (groupID, time-> List) - key 是 groupID, time - 按 recordID 排序，次要按时间 (Let that be map2)

在每次记录更改时：

  • 检索您正在更改的记录的当前 groupID
  • 放t <- current time
  • map1为旧组创建一个新条目： (oldGroupID,t,list')- 其中 list' 是同一个列表，但没有您刚从那里移出的条目。
  • map1为新组添加新条目： (newGroupId,t,list'')- 其中 list'' 是新组的旧列表，其中添加了更改的记录。
  • 将新条目 (recordId,t,newGroupId) 添加到 map1

查询期间：

  • 您需要找到map2“最接近”且小于 的条目(recordId,desired_time)- 这是排序数据结构中的经典O(logN)操作。
  • 这将为您提供g该元素在所需时间所属的组。
  • 现在，类似地在 map1 中查找键最接近但小于 的条目(g,desired_time)。该值是在所需时间在组中的所有记录的列表。

这需要相当多的空间（尽管在常数因子下......），但每个操作都是O(logN)-N记录更改的数量在哪里。

对于大部分存储在磁盘上的条目，一个有效的排序 DS 是B+ 树，它也由许多关系 DS 实现实现。

于 2014-02-18T09:42:31.200 回答