Frage an die Experten für Sortier-Algo-Optimierung

[Codehunter]

Moin!

Ich habe eine Datenbanktabelle mit ca. 1600 Records. Jeder Record hat u.A. eine ID und eine ParentID. Letztere ist ein Verweis auf die ID eines anderen Datensatzes (beides Integer-Werte). Die Daten füttern einen VirtualTreeView. Hier mein bisheriger Code, der zwar ganz exakt das tut was er soll (die Baumstruktur anhand von ID und ParentID bilden), arbeitet aber gaaaanz schröcklich langsam.

Die jetzige Routine arbeitet so, dass zunächst der Baum als flache Liste gefüllt (das geht noch pfeilschnell) und dann über den Sortier-Algo (unterhalb des finally in der Prozedur LoadPlacesTree) die Nodes ihrem jeweiligen Parent "untergeschoben" werden. Das Problem dabei: Innerhalb des Algo laufen zwei verschachtelte Schleifen (Hauptschleife und die in GetPlaceParentNode), sodass im Extremfall 2,56 Mio Durchläufe und Integer-Vergleiche ablaufen.

Idealerweise müsste man den Baum bereits beim Auslesen der Daten aus qryPlacesList aufbauen. Nur kann ich nicht davon ausgehen, dass die Reihenfolge der Datensätze dazu führt, dass jeder ParentNode-Datensatz vor den betreffenden ChildNode-Datensätzen in der Datenmenge liegt. Auch eine Vorsortierung über ein ORDER BY ist nicht möglich, da sich die IDs und ParentIDs aus den Autoinc-Werten bei der Datensatzerstellung bilden und der User später die Sortierung der Nodes frei ändern kann (wobei die IDs erhalten bleiben und sich nur die ParentIDs entsprechend ändern). Es kann also durchaus vorkommen, dass die ParentID größer ist als die ID eines Datensatzes.

Ich wäre euch für Anregungen zur Optimierung sehr dankbar.

Delphi-Quellcode:

type
  PPlaceRec = ^TPlaceRec;
  TPlaceRec = record
    Id: Integer;
    ParentId: Integer;
    Name: string;
    TypeId: Integer;
    TypeName: string;
    AllowedChildTypes: string;
  end;

{...}

function TfrmMain.GetPlaceFromNode(ANode: PVirtualNode): PPlaceRec;
begin
  Result:= tvPlaces.GetNodeData(ANode);
end;

function TfrmMain.GetPlaceParentNode(APlace: PPlaceRec): PVirtualNode;
var
  Node: PVirtualNode;
  Place: PPlaceRec;
begin
  Result:= NIL;
  if APlace^.ParentId = 0 then Exit;

  Node:= tvPlaces.GetFirst;
  while Node <> NIL do begin
    Place:= PlaceFromNode[Node];
    if Place <> NIL then begin
      if Place^.Id = APlace^.ParentId then begin
        Result:= Node;
        Break;
      end;
    end;
    Node:= tvPlaces.GetNext(Node);
  end;
end;

{...}

procedure TfrmMain.LoadPlacesTree;
var
  Node, ParentNode: PVirtualNode;
  Place: PPlaceRec;
begin
  with qryPlacesList do begin
    if not Active then Active:= TRUE;
    if RecordCount > 0 then begin
      First;
      tvPlaces.BeginUpdate;
      try
        while not Eof do begin
          Node:= tvPlaces.AddChild(NIL);
          if Assigned(Node) then begin
            Place:= tvPlaces.GetNodeData(Node);
            if Assigned(Place) then begin
              with Place^ do begin
                Id:= Fields.FieldByName('id').AsInteger;
                ParentId:= Fields.FieldByName('parent_id').AsInteger;
                Name:= Fields.FieldByName('name').AsString;
                TypeId:= Fields.FieldByName('type_id').AsInteger;
                AllowedChildTypes:= Fields.FieldByName('allowed_child_types').AsString;
              end;
            end;
            Next;
          end;
        end;
      finally
        Node:= tvPlaces.GetFirst;
        while Node <> NIL do begin
          Place:= GetPlaceFromNode(Node);
          if Place <> NIL then begin
            ParentNode:= GetPlaceParentNode(Place);
            if Node.Parent = ParentNode then begin
              Node:= tvPlaces.GetNext(Node);
              Continue;
            end;
            if ParentNode <> NIL then begin
              tvPlaces.MoveTo(Node, ParentNode, amAddChildLast, FALSE);
              Node:= tvPlaces.GetNext(ParentNode);
            end else begin
              Node:= tvPlaces.GetNext(Node);
            end;
          end else begin
            Node:= tvPlaces.GetNext(Node);
          end;
        end;
        tvPlaces.FocusedNode:= NIL;
        tvPlaces.EndUpdate;
      end;
    end;
    Active:= FALSE;
  end;
end;