# Baumstruktur in Datenbank abbilden



## jambusa (19. Mai 2010)

Hallo zusammen.

Ich nutze Hibernate/Spring und eine MySQL Datenbank zur Datenhaltung.

Aktuell stelle ich in einer JTable eine Baumstruktur dar. Ein Baum kann mehrere Äste haben, welche wiederum mehrere Äste (bis zu 9 Ebenen), oder auf unterster Ebene Blätter haben können. Dies hat bisher auch super geklappt, nur leider stoße ich mittlerweile bei tiefen Ebenen auf Performanceprobleme.

Derzeit hab ich es so realisiert, dass ein Ast einen Foreign Key auf seinen Parent besitzt. Im Domainobject ist dieser dann als Ast-Objekt via getParent() verfügbar. Möchte ich nun auf tieferen Ebenen an einen vorhandenen Ast einen weiteren Ast anhängen, so dauert dies je tiefer die Ebene länger.

Grobe Werte aus einem Microbenchmark (Anlegedauer eines Astes):

Ebene1 : 32ms.
Ebene3 : 80ms.
...
Ebene9 : 232ms.

Da die Ebenen (somit die Anzahl der Parents) ganz offensichtlich eine Rolle spielen, wollte ich Fragen, ob es Ansätze gibt, die sich in der Praxis bewährt haben, um dieses Problem zu umschiffen. Mir ist nicht ganz klar, warum Hibernate beim Anlegen eines Datensatzes den gesamten Objektbaum bis zum Root auflösen muss. Dies kann aber die einzige Ursache sein, da ein Ast sonst keinerlei Relationen auf andere Objekte besitzt, oder liege ich da ganz falsch?

Für Tipps oder Anregungen wäre ich dankbar.

Grüße,
jambusa


----------



## maki (19. Mai 2010)

Nested Sets, oder eine Tree Tabelle, dessen PK in jedem Knoten mitgegeben wird, so könntest du alle Knoten auf einmal auslesen, müsstest diese aber auch wieder selber zusammenbauen.


----------



## jambusa (19. Mai 2010)

Danke für deine schnelle Antwort.

Meines Wissens nach hat man bei Nested Sets ähnliche Performance-Probleme, sofern man häufige Strukturänderungen durchführen möchte, da man laufend die Indizes vieler Knotenpunkte aktualisieren muss.

Die Idee mit der Zwischentabelle finde ich interessant, bin mir nur nicht ganz sicher, ob ich sie richtig verstanden habe. Ich würde also die Parentbeziehungen in dieser Zwischentabelle realisieren und dort festhalten, zu welchem Parent ein Ast gehört und lediglich diesen Datensatz via foreign key referenzieren, statt den Parent-Ast direkt zu referenzieren?

Da habe ich nur die Befürchtung das Hibernate trotzdem diese Beziehung weitergehend auflöst, aber da bin ich überfragt. Habe ich das so richtig wiedergeben oder was genau umfasst deine TreeTabellen Idee?


----------



## maki (19. Mai 2010)

Table Tree, Tabelle Nodes
Jede Node hat den PK ihres Trees, damit kannst du alles Nodes eines Trees auf einmal aus der DB lesen.

Nested Set lesen sehr schnell, können aber bei Änderungen relativ viel Zeit brauchen, bei deiner Struktur kannst du sehr schnell ändern, aber auslesen dauert etwas längern.


----------

