Как структурировать базу данных для быстрого доступа к узлу

Question

Я ищу способ структурирования базы данных с помощью базы данных VirtualTreeView и SQLite для быстрого извлечения данных. В VirtualTreeView есть событие OnNodeInit bu, это не всегда удобно для этой цели.

Данные извлекаются из групп новостей Usenet и должны быть пронизаны резьбой. Данные, полезные для потоковой передачи, - это post id (int64, также первичный ключ), ссылки (строки, относящиеся к предыдущим сообщениям в потоке).

Программа ищет строки в ссылках и определяет, по какому положению она должна идти. Так, например, после ид = 1234, то следующая запись может быть 1235, а затем 1236 может быть ответом на 1234.

Вот возможный пример базы данных:

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

Так что теперь это, как она выглядит Теперь.

Теперь проблема заключается в том, как структурировать эти данные для более быстрого поиска. Если есть только корневой узел, я могу назначить RootNodeCount на основе записей базы данных, а затем в OnNodeInit читать их один за другим по запросу. Когда у вас есть суб-узлы, мне нужно как-то перегруппировать базу данных, чтобы он знал, как быстрее получать субноды в зависимости от того, какой узел открыт.

Я думал назначить дополнительное поле «has_subnodes» с последующим идентификатором нижележащего узла. При щелчке узла он считывает этот узел и каждый связанный узел.

Как бы вы организовали эту базу данных, чтобы ее можно было хорошо прочитать в OnNodeInit или вы вообще использовали бы это событие? Узлы могут быть инициированы с использованием метода AddChildNoInit(). Любые идеи или указатели приветствуются.

UPDATE (И КАК РЕШИТЬ ЭТО)

Существует некоторые не virtualtreeview связанные информации здесь: Implementing a hierarchical data structure in a database

То, что я в конечном итоге делает это с помощью Modified Preorder обходе дерева для хранения информации в база данных о узлах и каждый раз, когда запрашивается определенный узел:

a) он просматривается во внутреннем кеше, который в основном сохраняет идентичную структуру структуры VirtualTreeView.

б) если найдено в кэше, этот элемент кэша удаляется (он никогда не держит более 100 наименований)

С), если не найден, дополнительные 100 элементов добавляются в кэше (50 вверх от запрашиваемого узла, и 50 вниз). Этот номер может быть изменен до 500 или 1000 элементов, если это необходимо. Есть несколько дополнительных проверок, чтобы увидеть, как много вверх/вниз нужно читать, чтобы не читать слишком много дубликатов записей.

d) если мне нужна дополнительная скорость, я могу применить дополнительную технику - загружать узлы из базы данных в зависимости от того, сколько пользователь прокручивает virtualtreeview - подобно тому, как std :: vector выделяет память - сначала я загружаю только 100 узлов, тогда if пользователь прокручивает много, я загружаю 200, затем 400 и т. д. ... чем больше пользователь прокручивает, тем быстрее он загружает все дерево, но все равно не загружает его, если он никогда не прокручивает.

Таким образом, узлы, которые никогда не видны, никогда не загружаются из базы данных. Он отлично работает для прокрутки с колесиком мыши (при случайной короткой задержке, когда он проходит точку, где кеш пуст и для этого требуется больше данных с диска) и для прокрутки со стрелками/клавишами.Это немного медленнее, когда вы перетаскиваете полосу прокрутки в определенную позицию (скажем, снизу до середины), но это ожидается, поскольку данные не могут быть извлечены с диска мгновенно.

Лучше всего, если я предварительно определю, сколько памяти я хочу использовать для кеша/элементов, прежде чем загружать их, тем больше ускорение прокрутки, но, конечно же, оно использует больше памяти, если данные никогда не отображаются.

Answer 1

Вы хотите хранить иерархические данные в базе данных.
Проблема в том, что SQL не имеет возможности хорошо разбираться с такими данными.

У вас есть ряд решений, каждый из которых имеет свои недостатки и преимущества.
Вот ссылка, если вы хотите, чтобы прочитать о каждом из подходов:

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

Мой личный фаворит Modified Preorder Tree Traversal

Здесь вы занесения левый и правый узел в базе данных в очень контрастный интуитивный способ, который делает вставки узлов немного медленными, но быстро восстанавливает молнию.

Вы можете закодировать свою логику в Delphi, но я предпочитаю использовать хранимые процедуры в моей базе данных по выбору.
Таким образом, ваша логика в Delphi остается простой, и если база данных изменит ваш код Delphi, это не обязательно. Если вы хотите, я могу включить SQL-код для хранимых процедур, но не сейчас, потому что этот код не находится на ноутбуке, который у меня есть сейчас.

Answer 2

Не самый элегантный, но это метод, который я использую для заполнения моих деревьев.

Для получения двух простых запросов требуется только данные, а остальная часть - на стороне клиента.

Он будет легко загружать десятки тысяч узлов. (Глядя на него сейчас, я мог бы, вероятно, сойти с рук только один запрос - его староват!):

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; 

Замечание: при OrderBy столбец является необязательным, я требовать его как мои деревья порядок специфичны.

Так DB имеет эти три столбца, а также любые пользовательские данные вам потребуется:

ID, ParentID (-1 для без родителя), OrderNo