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

Question

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

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

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

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

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

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

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

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

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

ОБНОВЛЕНИЕ (И КАК Я РЕШЕН ЭТО)

Существует некоторая информация, не относящаяся к виртуальному дереву, доступная здесь: Реализацияиерархическая структура данных в базе данных

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

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

b) при обнаружении в кеше эта запись в кеше удаляется (она никогда не содержит более 100 элементов)

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

d) если мне нужно больше скорости, я могу применить дополнительную технику - загружать узлы из базы данныхна сколько пользователь прокручивает virtualtreeview - аналогично тому, как std :: vector выделяет память - сначала я загружаю только 100 узлов, затем, если пользователь много прокручивает, я загружаю 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 является необязательным, я требую его, так как мои деревья расположеныспецифические.

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

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