java - 将父子映射存储在内存中。有效地为父母列出所有可到达的孩子

Question

我在理性数据库中有父子映射，如下所示，

relationship_id | parent_id | child_id
1               | 100009    | 600009
2               | 100009    | 600010
3               | 600010    | 100008

为了性能优化，我喜欢将所有这些映射保存在内存中。在这里，一个孩子将有一个以上的父母，而一个父母有两个以上的孩子。我想，我应该使用“Graph”数据结构。

填充到内存中是一次性的活动。我担心的是，当我要求列出所有孩子（不仅仅是直系孩子）时，它应该尽快返回它们。添加和删​​除很少发生。我应该使用什么数据结构和算法？

尝试了MultiHashMap，以实现O(1)搜索时间，但它有更多的冗余。

Answer 1

具有用于父子关系的图形数据结构。每个 GraphNode 只能有一个ArrayList子节点。

然后HashMap将 ID 映射到 GraphNode。

你需要弄清楚一些事情，这样你就不会创建一个会导致无限循环的循环（如果可能的话）。

Answer 2

您将需要一个自定义Node类和一个 hashmap 来存储节点引用以便于查找。

for each row in database
if parent node exists in map
  get it
else
  create it and add it

if child node exists in map
  get it
else
  create it and add it

set relationship between parent and child

节点类看起来像；

public class Node {

  private int id;

  private List<Node> parents = new ArrayList<Node>();
  private List<Node> children = new ArrayList<Node>();

  //getters and setters

}