Storing parent child mapping in memory. To list all reachable child for a parent efficiently

Question

I have parent and child mappings in reational database as below,

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

for performance optimization, i like to keep all these mappings in memory. Here, a child will be having more than one parent and a parent has more than 2 children. I guess, i should use "Graph" data structure.

Populating into memory is a one time activity. My concern is that, when I ask to list all child (not only immediate child) it should return them as fast as possible. Addition and deletion happens rarely. What data structure and algorithm I should use?

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

Answer 1

Have a graph data structure for parent-child relationships. Each GraphNode can just have an ArrayList of children.

Then have HashMap that maps ID to GraphNode.

You need to figure something out so you don't create a cycle (if this is possible) which will cause an infinite loop.