高效查找标记的引用记录

Question

我有

• 数据库中有几百万条记录
• 互相引用（有向无环图）。有直接引用（A -> B）和间接引用（如果 A -> B 且 B -> C，则 A -> C）。间接引用可以有任意递归深度，但实际上深度最多为 100。这与面向对象语言中的对象可以递归引用其他对象非常相似，只是不允许循环。
• 一条记录可以有 0 到 100 个直接引用。
• 每条记录可以标记也可以不标记（大多数记录没有标记）。

问题

我正在寻找一种有效的数据结构和算法来找到所有给定一组记录（通常只有一个，或最多 100 个）的所有标记引用（直接或间接引用）记录。存在直接标记的记录（如果标记了直接引用的记录）或间接标记的记录（如果标记了间接引用的记录）。

读取记录相对较慢，假设每条记录 2 毫秒。

我是不想在这里使用更快的存储或类似的存储。我知道这是可能的，但保持同步非常困难。我正在尝试添加仅包含相关数据的辅助数据结构。这将大大加快速度（可能是 10 倍甚至 100 倍），但会带来恒定因子的改进。我仍然有兴趣了解如果数据量增加，是否可以改进算法。

想法

我考虑过以下选项：

• 蛮力：一种算法是搜索所有（直接或间接引用的）条目，并过滤标记的条目。但这显然很慢，因为我必须处理所有（直接或间接）引用的条目。也许没有被标记，但有 20,000 个被引用。

• 影子标记：另一种算法是有一个反向索引（哪些条目引用哪些其他条目），然后每次标记一个条目时，也递归地“影子标记”引用该条目的所有条目。这样，当搜索标记条目时，我们可以过滤那些设置了“shadow-mark”的条目。缺点是如果标记了条目，则需要进行多次更新。一个相关的选项是使用布隆过滤器进行阴影标记。但这只会减少内存使用量。

• 假设我们维护一个“最大深度”，它是树的最大深度（任何记录的最大跳数）。然后我们使用上面的阴影标记算法，但只是部分使用：仅达到最大深度/2个递归级别。所以我们限制阴影标记的传播。然后，对于一个查询，我们还将递归深度限制为最大深度/2。这样，在最坏的情况下我们将“在中间相遇”。（我可能应该画一张图。）一个子问题是如何有效地维持这个最大深度。

我想知道，是否有类似这种方法的东西？在标记条目时不需要太多更新，并且在查询时不需要太多读取的东西？或者也许是一个允许逐步更新条目（如果条目被标记）的解决方案？

例子

在这个例子中（蓝色是“标记”），例如，如果我搜索（间接）引用标记记录 5，我想快速找到 1 和 3。

Answer 1

您可以在每个节点上保留一个表，记录可以从该节点访问哪些标记的节点，并在每当从图中添加或删除节点（或边）时保持更新，类似于为网络中的每个节点保留网络路由表。不过，有关您的问题的一些具体细节使其比网络路由表更简单：

• 您不想知道从给定节点到标记节点的实际路径，只想知道存在一个（或多个）。
• 该图是非循环的。
• 它不是一个分布式系统，因此您可以完全控制（显然......）。

因为您不关心路径，并且图是非循环的，所以每个节点上的表可以是一个映射，marked_node_id -> count其中 count 是从给定节点到给定标记节点的路径数。添加新节点时，新节点的表将构建为与新节点相邻的所有节点表的并集，其中count是总和。此外，必须通过将新节点的表添加到每个节点来更新与新节点相邻的所有节点的表，并且必须在相邻链上递归地完成此操作。当删除节点时，您必须执行类似的操作。

基本复杂度分析：查找给定节点的所有标记节点的时间复杂度为 O(1)，并且可以通过存储在单个节点上的信息来完成 - 这就是重点。一般来说，添加和删除边（或新节点及其边）将需要递归更新所有连接节点的表（调用深度最多为 100，分支因子最多为 100）。通过从标记节点进行反向泛洪，最初构建表的时间复杂度为 O（节点数）。

代码示例：

这是抽象的代码内解决方案，但应该翻译。我使用 Python (+GraphViz) 是因为您没有指定一种语言，它可能最适合最广泛的受众，并且很容易原型化。我也将只实现添加/删除节点操作（以修改节点可以删除然后添加不同的初始化）并从头开始构建图表，这并不现实，但是您可以通过从标记的节点向后工作来非常轻松地构建最初给定现有图表的表。另请注意：

• 以下要求每个节点adjacent_from除了adjacent_to列表之外还拥有/维护一个列表，以便在删除给定节点时我们可以从路径中递归相邻的路径。
• 我假设每个标记的节点都可以从自身访问 - 只是使事情更容易实现。

def main():
  ''' Build a test graph, then test. '''
  graph = Graph()
  a = graph.add_node('a', marked=True)
  b = graph.add_node('b', marked=True)
  c = graph.add_node('c', marked=True)
  d = graph.add_node('d', adjacent_to=[a])
  e = graph.add_node('e', adjacent_to=[d])
  f = graph.add_node('f',adjacent_to=[c])
  g = graph.add_node('g', adjacent_to=[d,f])
  h = graph.add_node('h', adjacent_to=[e,g])
  i = graph.add_node('i')
  j = graph.add_node('j', marked=True, adjacent_to=[i])
  k = graph.add_node('k', adjacent_to=[j])
  l = graph.add_node('l', adjacent_to=[k])
  m = graph.add_node('m', adjacent_to=[j])
  with open('main0.dot', 'w') as f:
    f.write(graph.gviz())
  graph.delete_node('f')
  with open('main1.dot', 'w') as f:
    f.write(graph.gviz())
  graph.delete_node('e')
  with open('main2.dot', 'w') as f:
    f.write(graph.gviz())
  graph.delete_node('g')
  with open('main3.dot', 'w') as f:
    f.write(graph.gviz())
  # Run this script to process graphviz files: for i in *.dot; do dot -Tpng $i > "${i%%.dot}.png"; done

class Graph:
  ''' Container for nodes. '''
  def __init__(self):
    self.nodes = {}

  def add_node(self, id, marked=False, adjacent_to=[]):
    assert id not in self.nodes
    self.nodes[id] = Node(id, marked, adjacent_to)
    return self.nodes[id]

  def delete_node(self, id):
    assert id in self.nodes
    node = self.nodes[id]
    self._recursive_subtract_table_on_delete(node, node)
    for adjacent_from_node in node.adjacent_from:
      adjacent_from_node._remove_adjacent_node(node.id)
    del self.nodes[id]

  def _recursive_subtract_table_on_delete(self, node, deleted_node):
    for adjacent_from_node in node.adjacent_from:
      self._recursive_subtract_table_on_delete(adjacent_from_node, deleted_node)
    node._delete_reachability_table(deleted_node)

  def gviz(self):
    return 'strict digraph {\n%s}' % ''.join([n._gviz_edges() for n in self.nodes.values()])

class Node:
  def __init__(self, id, marked=False, adjacent_to = []):
    ''' Init node. Note only adjacent_to not adjacent_from node are allowed,
    which measn we dno't have to update adjacent_from reachable_marks.  '''
    self.id = id
    self.marked = marked
    self.adjacent_to = adjacent_to
    self.adjacent_from = []
    self.reachable_marks = {}

    if marked:
      self.reachable_marks[id] = 1
    for adjacent_node in adjacent_to:
      adjacent_node.adjacent_from.append(self);
      self._add_reachability_table(adjacent_node)

  def _add_reachability_table(self, node):
    ''' Add the reachable_marks table from node to self. '''
    for (marked_node_id, k) in node.reachable_marks.items():
      self.reachable_marks[marked_node_id] = self.reachable_marks[marked_node_id] + 1 if marked_node_id in self.reachable_marks else 1

  def _delete_reachability_table(self, node):
    ''' Delete the reachable_marks table from node from self. '''
    for (marked_node_id, k) in node.reachable_marks.items():
      self.reachable_marks[marked_node_id] = self.reachable_marks[marked_node_id] - 1 if marked_node_id in self.reachable_marks else 0
    self.reachable_marks = {k: v for k,v in self.reachable_marks.items() if v}

  def _remove_adjacent_node(self, id):
    self.adjacent_to = list(filter(lambda n: n.id != id, self.adjacent_to))

  def _gviz_edges(self):
    ''' Helper to print graphviz edges adjacent to this node. '''
    _str = ''
    if self.marked:
      _str += ' %s[style=filled,fillcolor=blue]\n' % (self._gviz_name(),)
    else:
      _str +=  self._gviz_name() + '\n'
    for adjacent_node in self.adjacent_to:
      _str += ' %s -> %s\n' % (self._gviz_name(), adjacent_node._gviz_name())
    return _str;

  def _gviz_name(self):
    ''' Helper to print graphviz name with reachable marks. '''
    return '"' + self.id + '(' + ','.join(self.reachable_marks.keys()) + ')"'

if __name__ == '__main__':
  main()

结果：

输出图显示了从括号中的每个节点可到达的标记节点。

最初的：

删除节点 f：

删除节点 e：

删除节点g：