Jak zbudować bazę danych dla szybkiego dostępu do węzła?

Question

Poszukuję sposobu na uporządkowanie bazy danych z VirtualTreeView i bazą danych SQLite w celu szybkiego pobrania danych. Z VirtualTreeView jest zdarzenie OnNodeInit bu, które nie zawsze jest w tym celu praktyczne.

Dane są pobierane z grup dyskusyjnych Usenet i muszą być wątkowane. Dane przydatne w wątkach to: id_początkowy (int64, także klucz podstawowy), odwołania (łańcuchy, które odnoszą się do poprzednich postów w wątku).

Program wyszukuje ciągi w odnośnikach i określa, w których postidach ma jechać. Tak na przykład postu id = 1234, a potem następny wpis może być 1235, a następnie 1236 może być odpowiedź na 1234.

Oto możliwe przykład bazy danych:

post id references parent id 
    1234  .... ....  0 
    1235  .... ....  0 
    1236  .... ....  1234 

więc teraz tak to wygląda w prawo teraz.

Problem polega na tym, jak uporządkować te dane, aby uzyskać szybsze pobieranie. Jeśli istnieje tylko węzeł główny, mogę przypisać wartość RootNodeCount na podstawie wpisów w bazie danych, a następnie w OnNodeInit przeczytać je kolejno jeden po drugim, zgodnie z żądaniem. Mając sub-węzły, muszę jakoś zmienić bazę danych tak, aby wiedziała jak uzyskać podwęzły szybciej w zależności od tego, który węzeł jest otwarty.

Myślałem, aby przypisać dodatkowe pole "has_subnodes" z identyfikatorem pod-węzła, który następuje. Po kliknięciu węzła odczytuje ten węzeł i każdy połączony węzeł.

Jak zorganizowałbyś tę bazę danych, aby mogła być ładnie odczytywana w OnNodeInit lub w ogóle byś wykorzystał to wydarzenie? Węzły mogą być również inicjowane za pomocą metody AddChildNoInit(). Wszelkie pomysły i wskazówki byłyby mile widziane.

UPDATE (i jak ja rozwiązałem)

Istnieją pewne informacje nie VirtualTreeView związanych dostępny tutaj: Implementing a hierarchical data structure in a database

Co skończyło się robi korzysta Modified Preorder przechodzenie drzewa do przechowywania informacji w baza danych o węzłach i za każdym razem, gdy dany węzeł jest żądany jako pierwszy:

a) jest wyszukiwany w wewnętrznej pamięci podręcznej, która zasadniczo posiada identyczną strukturę ze strukturą VirtualTreeView.

b) jeśli znajdują się w pamięci podręcznej, to zapis podręczny jest usuwany (nigdy nie posiada więcej niż 100 pozycji)

c) Jeżeli nie znaleziono, dodatkowe 100 elementy są dodawane w pamięci podręcznej (50 up od żądanego węzła, a 50 w dół). Ta liczba oczywiście może być modyfikowana do 500 lub 1000 przedmiotów, jeśli to konieczne. Istnieje kilka dodatkowych sprawdzeń, aby zobaczyć, ile do odczytu musi być w górę/w dół, aby uniknąć zbyt dużej ilości powtarzających się wpisów.

d) jeśli potrzebuję więcej prędkości, mogę zastosować dodatkową technikę - ładuję węzły z bazy danych w zależności od tego, jak bardzo użytkownik przewija widok wirtualny - podobnie jak std :: wektor przydziela pamięć - najpierw ładuję tylko 100 węzłów, a następnie, jeśli użytkownik przewija dużo, ładuję 200, potem 400 itd. ... im więcej użytkownik przewija, tym szybciej ładuje całe drzewo, ale wciąż nie ładuje go, jeśli on/ona nigdy nie przewija.

W ten sposób węzły, które nigdy nie były widziane, nigdy nie są ładowane z bazy danych. Działa dobrze podczas przewijania za pomocą kółka myszy (przy sporadycznym krótkim opóźnieniu, gdy przechodzi przez punkt, w którym pamięć podręczna jest pusta i potrzebuje więcej danych z dysku) i do przewijania za pomocą przycisków/klawiszy strzałek.Jest nieco wolniejszy, gdy przeciągasz pasek przewijania do określonej pozycji (powiedzmy od dołu do środka), ale jest to oczekiwane, ponieważ dane nie mogą być natychmiast pobrane z dysku.

Najlepiej jest, jeśli wcześniej ustalę, ile pamięci, którą chcę zużyć dla pamięci podręcznej/elementów przed ich włożeniem, tym bardziej szybsze jest przewijanie, ale oczywiście używa więcej pamięci, jeśli dane nigdy nie są wyświetlane.

Answer 1

Szukasz do przechowywania danych hierarchicznych w bazie danych.
Problem polega na tym, że SQL nie jest dobrze przygotowany do radzenia sobie z tego rodzaju danymi.

Masz wiele rozwiązań, każdy ma swoje minusy i zalety.
Oto link, jeśli chcesz przeczytać na każdej metody:

http://www.sitepoint.com/hierarchical-data-database/
http://www.sitepoint.com/hierarchical-data-database-2/

Moim ulubionym jest Modified Preorder Tree Traversal

Tutaj można przechowywać lewy i prawy węzeł w bazie danych w sposób bardzo sprzeczny z intuicją sposób, który sprawia, że ​​wstawianie węzłów jest nieco powolne, ale szybkie pobieranie błyskawic.

Możesz kodować swoją logikę w Delphi, ale wolę używać procedur przechowywanych w wybranej bazie danych.
W ten sposób twoja logika w Delphi pozostaje prosta i jeśli baza danych zmieni twój kod Delphi, nie musi. Jeśli chcesz, mogę dołączyć kod SQL do procedur przechowywanych, ale nie teraz, ponieważ ten kod nie znajduje się na laptopie, który mam ze sobą teraz.

Answer 2

Nie najbardziej elegancka, ale jest to metoda, której używam do zaludnienia drzew.

Wymaga tylko dostępu do danych dla dwóch prostych zapytań, a reszta to wszystko po stronie klienta.

Z łatwością załaduje dziesiątki tysięcy węzłów. (Patrząc na to teraz, prawdopodobnie mógłbym uciec za pomocą jednego zapytania - jego nieco stary!):

procedure TFrameComponentViewer.LoadComponentTree; 
var 
RootNodeData : PMasterComponent; 
CompQ,ParentQ : TMyQuery; 

procedure PopulateNodeData(Node: PVirtualNode;ComponentID : integer); 
var NodeData : PMasterComponent; 
begin 
    if CompQ.Locate('ComponentID',ComponentID,[loCaseInsensitive]) then 
    begin 
    NodeData := TreeComponents.GetNodeData(Node); 
    //Populate your desired TreeData 
    NodeData.ComponentID := CompQ.Fields[fldComponentID].AsInteger; 
    NodeData.ComponentCode := CompQ.Fields[fldComponentCode].AsString; 
    NodeData.ComponentType := CompQ.Fields[fldComponentType].AsInteger; 
    NodeData.IsPipeline := CompQ.Fields[fldComponentIsPipeline].AsBoolean; 
    NodeData.Description := CompQ.Fields[fldComponentDescription].AsString; 
    NodeData.StartKP := CompQ.Fields[fldComponentStartKP].AsFloat; 
    NodeData.EndKP := CompQ.Fields[fldComponentEndKP].AsFloat; 
    NodeData.Diameter := CompQ.Fields[fldComponentDiameter].AsFloat; 
    NodeData.WallThickness := CompQ.Fields[fldComponentWallThickness].AsFloat; 
    NodeData.CriticalSpanLength := CompQ.Fields[fldComponentCSL].AsFloat; 
    NodeData.Historical := CompQ.Fields[fldComponentHistorical].AsBoolean; 
    end; 
end; 

procedure AddNodesRecursive(ParentNode : PVirtualNode;ParentNodeID : Integer); 
var AddedNode : PVirtualNode; 
AddedNodeData : PMasterComponent; 
Children : Array of Integer; 
i : Integer; 
begin 
    try 
     ParentQ.Filtered := False; 
     ParentQ.Filter := 'Parent_ID = '+InttoStr(ParentNodeID); 
     ParentQ.Filtered := True; 
     ParentQ.First; 
     SetLength(Children,ParentQ.RecordCount); 
     for i:=0 to ParentQ.RecordCount-1 do 
     begin 
      Children[i] := ParentQ.Fields[0].AsInteger; 
      ParentQ.Next; 
     end; 
     for i:=0 to High(Children) do 
     begin 
      AddedNode := TreeComponents.AddChild(ParentNode); 
      AddedNodeData := TreeComponents.GetNodeData(AddedNode); 
      System.Initialize(AddedNodeData^); //initialize memory 
      PopulateNodeData(AddedNode,Children[i],CompQ); 
      AddNodesRecursive(AddedNode,AddedNodeData.ComponentID); 
     end; 
    finally 
    end; 
end; 

begin 
    TreeComponents.BeginUpdate; 
    treeComponents.Clear; 
    CompQ := TMyQuery.Create(nil); 
    ParentQ := TMyQuery.Create(nil); 
    try 
     CompQ.Connection := DataBaseline.BaseLineConnection; 
     CompQ.SQL.Add('SELECT * FROM Components'); 
     CompQ.Open; 
     ParentQ.Connection := DataBaseline.BaseLineConnection; 
     ParentQ.Close; 
     ParentQ.SQL.Clear; 
     ParentQ.SQL.Add('SELECT ComponentID,Parent_ID FROM Components ORDER BY OrderNo'); 
     ParentQ.Open; 
     RootNode := TreeComponents.AddChild(nil); 
     RootNodeData := TreeComponents.GetNodeData(RootNode); 
     System.Initialize(RootNodeData^); //initialize memory 
     RootNodeData.ComponentID := -1; 
     AddNodesRecursive(RootNode,-1); 
    finally 
    TreeComponents.EndUpdate; 
    TreeComponents.FullExpand; 
    CompQ.Close; 
    ParentQ.Close; 
    FreeandNil(CompQ); 
    FreeandNil(ParentQ); 
    end; 
end; 

Uwaga: kolumna OrderBy jest opcjonalny i wymaga to jako moje drzewa są specyficzne zamówienie.

Więc DB ma te trzy kolumny, plus wszelkie niestandardowe dane wymagają:

ID, ParentID (-1 bez rodzica) OrderNo