Entwickler-Ecke

Datenbanken - Komplizierter Baumaufbau aus Datenbank


darksign - Do 22.03.07 12:05
Titel: Komplizierter Baumaufbau aus Datenbank
Hallo!

Ich habe folgende Tabelle, und will daraus einen Baum aufbauen:

Tabelle View

ID Parent Caption
1 0 'View 1'
2 1 'View 2'
3 0 'View 3'
4 3 'view 4'
5 6 'view 5'
6 0 'View 6'
7 6 'view 7'


Ok, das ganze soll nun als Baum dargestellt werden, ca. so:

View 1
...View 2
View 3
...View 4
View 6
...View 5
...View 7

Das Problem ist, dass das ganze leider nicht der Reihe nach in der Tabelle steht (siehe Beispiel), und außerdem macht mir die Spalte "Parent" zu schaffen, welche eigentlich auf die Tabelle selber wieder zeigt.
Kann mir jemand Pseudocodemäßig erklären, wie ich das machen könnte (wahrscheinlich irgendwie rekursiv)

danke schon mal


UGrohne - Do 22.03.07 12:10

Um was für eine Datenbank handelt es sich denn?

Wenn es um Firebird geht, dann hilft Dir vielleicht dieser Thread [http://www.delphi-forum.de/viewtopic.php?t=15238&highlight=baum%2A] weiter, da habe ich ein wenig Code für den TreeView und eine Stored Procedure für denselben Tabellenaufbau.


mkinzler - Do 22.03.07 12:14

Die Reihenfolge der datensätze in der Datenbank ist eigentlich egal, da man sie ja in der Abfrage verändern kann.
Für diesen Zweck bietet sich ein rekursiver Algorithmus an.


Stefan.Buchholtz - Do 22.03.07 13:24

Was für eine Datenbank hast du denn? Wenn es Oracle ist, kannst das der DB überlassen, Oracle kennt für diesen Zweck hierarchische Queries mit der CONNECT BY Bedingung. Das ist aber soweit ich weiss kein Standard-SQL und existiert auf anderen Datenbanken nicht.

Mit anderen Datenbanken machst du am besten eine rekursive Funktion. Das könnte z.B. so aussehen:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
procedure ReadTreeNodes(const AParent: Integer; const ALevel: Integer);
var
  qry : TQuery;
begin
  qry := TQuery.Create(nil);
  try
    qry.SQL.Text := 'SELECT id, name FROM tabelle WHERE parent = :parent';
    qry.ParamByName('parent').AsInteger := AParent;
    qry.Open;
    while not qry.Eof do
    begin
      memo1.Lines.Add(DupeString(' ', ALevel) + qry.FieldByName('name').AsString);
      ReadTreeNodes(qry.FieldByName('id').AsInteger, ALevel + 1);
      qry.Next;
    end;
  finally
    qry.Close();
    qry.Free();
  end;
end;


Das rufst du einfach mit ReadTreeNodes(00) auf und die Funktion läuft rekursiv durch den Baum und schreibt dir die Baumstruktur in ein Memo.
Keine Garantie auf Funktionsfähigkeit, ich hab das einfach mal so runtergeschrieben...

Stefan


wulfskin - Do 22.03.07 13:56

Hallo Stefan,

rekursiv durch eine Datenbank durchzugehen, halte ich für eine schlechte Methode, da man die Datenbank somit unnötig oft abfrägt und dafür Zeit verschwendet.
Was spricht denn dagegen alle Werte sortiert abzufragen und dann diese durchzugehen und nacheinandern einzufügen?

Gruß Hape!


Stefan.Buchholtz - Do 22.03.07 14:11

user profile iconwulfskin hat folgendes geschrieben:
rekursiv durch eine Datenbank durchzugehen, halte ich für eine schlechte Methode, da man die Datenbank somit unnötig oft abfrägt und dafür Zeit verschwendet.
Was spricht denn dagegen alle Werte sortiert abzufragen und dann diese durchzugehen und nacheinandern einzufügen?


Da spricht nichts dagegen, ausser dass es mehr Arbeit ist ;)
Ob sich der erhöhte Aufwand lohnt, hängt von diversen Faktoren ab:
- wie häufig wird die Abfrage ausgeführt
- wie gross ist die Baumstruktur
- was ist die erwartete Antwortzeit
- wieviel Last ist sonst noch auf der DB

Ich halte es normalerweise so, nur dann zu optimieren, wenn absehbar ist, dass die einfache Lösung zu langsam ist. Mit einem Index auf PARENT dürfte die Abfrage oben aber sehr schnell sein.

Stefan


UGrohne - Do 22.03.07 15:06

Ich habe oben einen Link zu einer Stored Procedure von mir gepostet inkl. Quellcode. Dabei ist die Last auf dem Server und es werden die benötigten Daten nur einmal abgefragt. Sollte performance-mäßig für die DB eigentlich am Besten sein.

Wenn es sich aber um sehr große Bäume handelt mit hoher Tiefe, dann würde ich Stefans Methode vorziehen und dann nur Ebenenweise abfragen, also wie im Windows Explorer wird die nächste Ebene erst aufgebaut, wenn sie benötigt wird.