Eltern-Child-Mapping im Speicher ablegen. Um all erreichbar Kind für einen Elternteil Liste effizient

Question

Ich habe Eltern und Kind Mappings in Freizeitaktivitä- Datenbank wie unten,

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

zur Performance-Optimierung, ich mag all diese Zuordnungen im Speicher zu halten. Hier hat ein Kind mehr als einen Elternteil und ein Elternteil hat mehr als 2 Kinder. Ich denke, ich sollte "Graph" Datenstruktur verwenden.

Das Einlagern in den Speicher ist eine einmalige Aktivität. Meine Sorge ist, dass wenn ich alle Kinder (nicht nur die unmittelbaren Kinder) auflisten möchte, sollten sie sie so schnell wie möglich zurückgeben. Hinzufügung und Löschung geschieht selten. Welche Datenstruktur und welchen Algorithmus sollte ich verwenden?

versucht MultiHashMap, um O(1) Suchzeit zu erreichen, aber es hat mehr Redundanz.

Answer 1

Haben Sie eine Diagrammdatenstruktur für Eltern-Kind-Beziehungen. Jeder GraphNode kann nur einen ArrayList von Kindern haben.

Dann haben Sie HashMap, die ID auf GraphNode abbildet.

Sie müssen etwas herausfinden, damit Sie keinen Zyklus erstellen (wenn dies möglich ist), der eine Endlosschleife verursacht.

Answer 2

Sie benötigen eine benutzerdefinierte Node Klasse und eine Hashmap zum Speichern von Knotenreferenzen zum einfachen Nachschlagen.

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 

Die Knotenklasse würde ungefähr so ​​aussehen;

public class Node { 

    private int id; 

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

    //getters and setters 

}