Geek asks and answers

Storing the mapping of parent children in memory. That the list of all available child elements for the parent was effective

I have parent and child mappings in a relational database as shown below,

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

to optimize performance, I like to keep all these mappings in memory. Here the child will have more than one parent, and the parent will have more than 2 children. I think I should use the Chart data structure.

Filling in memory is a one-time job. My concern is that when I ask to list all the children (not just the immediate child), he should return them as soon as possible. Adding and removing is rare. What data structure and algorithm should I use?

Tried MultiHashMap to achieve search time O(1), but has more redundancy.

+5
source share
2 answers

Has a graph data structure for parent-child relationships. Each GraphNode can only be ArrayListfor children.

Then we have HashMap, which displays the ID in GraphNode.

You need to find out something so that you do not create a loop (if possible) that will cause an infinite loop.

+5
source

For a convenient search, you will need a custom class Nodeand a hash map for storing node links.

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

The node class will look something like this:

public class Node {

  private int id;

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

  //getters and setters

}
+1
source

More articles:


All Articles