nicht angemeldet
Baumstruktur aus Datenbank auslesen
Hallo!
Ich habe mich einmal durch sämtliche Forumsbeiträge durchgewälzt um mir ein Bild darüber zu mache wie ich eine Baumstruktur in eine Datenbank speichere und auslese. Aber irgendwie verstehe ich das einfach nicht. Vielleicht kann mir wer einmal die Grundfunktionsweise etwas näherbringen.
Das habe ich aus einem alten Forum Thread:
---------------------------------------------------------------
ID ParentID FirstChildID NextID Text
1 0 2 4 h2: Kapitel 1
2 1 0 3 item1: Abschnit 1 zu Kapitel 1
3 1 0 0 item2: Abschnit 2 zu Kapitel 1
4 0 5 0 h2: Kapitel 2
5 4 0 6 item3: : Abschnit 1 zu Kapitel 2
6 4 0 0 item4: : Abschnit 2 zu Kapitel 2
Je nach DB-Engine soll anstelle des Werts 0 der Wert 'null' (für nicht definiert, != Zahl 0) verwendet werden.
Die Bedeutung der Felder:
ID: Eindeutiger Wert für jeden Datensatz.
ParentID: ID des hierarchisch übergeordneten Elementes (Knoten). Falls ParentID 'Null' ist, dann ist das Element in der obersten Hierarchistufe.
FirstChildID: ID des ersten darunterliegenden (Kind-)Elemenentes. Falls FirstChildID 'Null' ist, befinden sich keine Kind-Elemente unter dem Element. Das Element ist ein sog. Blatt des Baumes (=> also kein Knoten).
NextID: ID des nächsten Elementes in derselben Hierarchiestufe. Mit FirstChildID und NextID wird die Sortierreihenfolge innerhalb eines Astes festgelegt. Falls NextID 'Null' ist, ist es das letzte Element innerhalb des Astes.
Text: Beliebiges Feld, das Informationen über das Element enthält. Es sind hier auch mehrere Felder möglich.
---------------------------------------------------------------
Wie zb schaffe ich es jetzt den ganzen Baum auszugeben, inklusive aller geöffneten Unterknoten?
Ich bin das Szenario jetzt schon 100e male durchgegangen und immer wieder verlaufe ich mich in irgendeinen Zweig aus dem ich dann nicht mehr herauskomme(die Baumstruktur ist natürlich viel umfangreicher und soll dynamisch veränderbar sein).
Laut dem Beispiel von Henryk Plötz mit dem Threadbasierenden Forum braucht man nach dem Auslesen aus der Datenbank zwei 2 Dimensionale Arrays (eines geordnet nach ID und eines geordnet nach FirstChild) aber damit komme ich nicht zurecht, denn dann gehe ich immer dem 1.besten Childknoten nach bis ich irgendeinmal anstehe.
Ich habe aber keine Ahnung wie ich das realisieren könnte, dass ich den ganzen Baum nach hierarchischer Ebene durchlaufe.Ich meine damit, wenn der Baum so aufgebaut ist wie ein Binärbaum, der von oben nach unten immer verzweigter wird, dass ich immer Ebene um Ebene durchlaufe bis ich ganz durch bin - so kann ich mich nicht in einen enzelnen Ast verlaufen.
Ist mein Denkansatz überhaupt richtig oder denke ich zu kompliziert?
Grüsse,
Daniel
-
Hallo Daniel!
Nur kurz zur Theorie:
Wie man Bäume speichert, hast Du ja beschrieben. Eine "Id" und eine "ParentId" wird für die Struktur benötigt - damit lassen sich Bäume in beliebiger Tiefe darstellen.
Zum Auslesen eignet sich grundsätzlich eine rekursive (sich selbst aufrufende) Funktion - hängt natürlich von der Programmierumgebung ab.
Also im Prinzip (mal ein php-Pseudocode):
function getnodeitems($spacer, $id)
{
/* Alle Einträge auslesen, welche die angegebene ID aufweisen.
Für jeden der gefundenen Einträge dann diese (!) Funktion erneut aufrufen und die jeweilige ID mit übergeben. Also zB: */while (datengefunden)
{
/* Zuerst die Daten des aktuellen Eintrages ausgeben */print($spacer . 'Daten des Eintrags');
/* Und nun weitere Einträge zu dieser ID suchen - also weiter in die Tiefe ... */
getnodeitems($spacer . '-', diejeweiligeid);
}
}Gestartet wird das Ganze dann mit einmaligem Aufruf mit der "Root-ID":
getnodeitems('-', 0);
Das Ergebnis des Beispiels müsste dann in etwa so aussehen:
- Daten des Eintrags
-- Daten des Eintrags
--- Daten des Eintrags
-- Daten des Eintrags
Sieht etwas doof aus - aber als Grundlage sollte es reichen - ein wenig Datenbankmanipulation drumrum und es läuft.
Soweit zur Theorie - praktisch wird auch noch gerne aus Performancegründen ein "Pfad" mitverwaltet, der sich aus allen übergeordneten IDs zusammensetzt (zB 0_12_23_2) - könnte bei Such- oder Gruppierfunktionen ganz hilfreich sein ( ... where Path like '0_12%' - also alle Einträge zu einem bestimmten Zweig).
Mehr lässt sich dazu sicher im Archiv finden ;-)
mfg
norbert =:-)
-
Hallo Norbert
Danke einmal für die Hilfe!
Also ich glaube ich weiss was mich so irritiert hat, nämlich die rekursive Funktion.Also kann man das etwa so verstehen:angenommen ich habe diese Struktur:
0:x <-Blatt
1:x <-Knoten1
2: x <-Knoten2
3: x <-Blatt
4: x <-Knoten3
5: x <-Blatt
6: x <-Blatt
7:x <-BlattDas heisst dann konkret:
"Gib mir solange den Namen des Elements zurück, bis du einen weiteren Knoten gefunden hast"
"Findest du einen weiteren Knoten, rufe dich selbst nocheinmal auf und das ganze beginnt von vorne"
Ist das letzte Blatt gefunden, tritt die Funktion wieder an den Ausfuhrungsort ein, an dem sie sich als letztes aufgerufen hat, in meinem Fall:steigt ein bei 0:, findet Blatt, weiter
findet einen Knoten bei 1: Selbstaufruf der Funktion (2:)
findet einen Knoten bei 2: Selbstaufruf der Funktion (3:)
findet ein Blatt bei 3, weiter
findet einen Knoten bei 4: Selbstaufruf der Funktion (5:)
findet ein Blatt bei 5: Ende der Rekursion von (5:)
sucht bei 4: weiter, findet nichts mehr, Ende der Rekursion von (3:)
sucht bei 6 weiter, findet letztes Blatt, Ende der Rekursion von (2:)
sucht bei 7 weiter, findet letztes Blatt, EndeWenn das so stimmt wie ich vermute dann bin ich zufrieden :)
Grüsse,
Daniel -
Hi#
Du hast nicht wirklich vor, über eine rekursiv laufende prozedurale Steuerungssprache, immer wiederkehrend Queries an eine DB abzusetzen?eine "goldene Regel" bei der DB-Entwicklung:
- vermeide rekursive Queries wenn es geht, vorallem, wenn man alles in einer Query unterbringen kann
Gruß, Frank
- Daten des Eintrags
-
Hallo,
[...] wie ich eine Baumstruktur in eine Datenbank speichere und auslese.
Vielleicht hilft Dir der Artikel "Das 'Nested Sets' Modell - Bäume mit SQL"
von Daniel T. Gorski weiter:
http://develnet.org/36.htmlGruesse,
Thomas