Cómo estructurar la base de datos para acceso rápido a los nodos

Question

Estoy buscando una manera de estructurar la base de datos con VirtualTreeView y la base de datos SQLite para la recuperación rápida de datos. Con VirtualTreeView hay un evento OnNodeInit pero no siempre es práctico para este propósito.

Los datos se obtienen de los grupos de noticias de Usenet y deben enhebrarse. Los datos útiles para el enhebrado son la identificación posterior (int64, también la clave principal), las referencias (cadenas que se refieren a publicaciones anteriores en el hilo).

El programa busca cadenas en las referencias y determina bajo qué postid debería ir. Así, por ejemplo, ID = 1234, entonces el próximo post podría ser 1235, 1236 y luego podría ser la respuesta a 1234.

Aquí es un posible ejemplo de base de datos:

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

Así que ahora esta es la forma en que se ve bien ahora.

Ahora, el problema es cómo estructurar estos datos para una recuperación más rápida. Si solo hay un nodo raíz, puedo asignar RootNodeCount en base a las entradas de la base de datos y luego en OnNodeInit leerlos uno por uno según lo solicitado. Cuando tengo nodos secundarios, entonces tengo que reorganizar de alguna manera la base de datos para que sepa cómo obtener subnodos más rápidamente dependiendo de qué nodo se abre.

Estaba pensando en asignar el campo adicional "has_subnodes" con ID del subnodo que sigue. Cuando se hace clic en un nodo, entonces lee ese nodo y cada nodo vinculado.

¿Cómo organizarías esta base de datos para que se pudiera leer muy bien en OnNodeInit o usarías ese evento en absoluto? Los nodos pueden iniciarse también utilizando el método AddChildNoInit(). Cualquier idea o puntero sería bienvenida.

ACTUALIZACIÓN (y cómo lo resolví)

Hay alguna información no relacionada con VirtualTreeview disponible aquí: Implementing a hierarchical data structure in a database

Lo que terminé haciendo es utilizando Modificado Preordenes Árbol de recorrido para almacenar información en base de datos sobre nodos y cada vez que se solicita primero un nodo determinado:

a) se busca en la memoria caché interna que básicamente mantiene la estructura idéntica a la estructura VirtualTreeView.

b) si se encuentra en la memoria caché, se quita esta entrada de caché (nunca contiene más de 100 artículos)

c) si no se encuentra, 100 elementos adicionales se añaden en la memoria caché (50 hasta desde el nodo solicitado, y 50 abajo). Este número de curso se puede modificar a 500 o 1000 artículos si es necesario. Hay algunos controles adicionales para ver cuánto cuesta arriba/abajo necesita leer para evitar leer demasiadas entradas duplicadas.

d) si necesito más velocidad, puedo aplicar una técnica adicional: cargar nodos desde la base de datos en función de cuánto desplaza el usuario virtualtreeview, similar a como std :: vector asigna memoria, primero cargo solo 100 nodos, luego si el usuario se desplaza mucho, cargo 200, luego 400, etc. ... cuanto más se desplaza el usuario, más rápido carga todo el árbol, pero aún no lo carga si nunca se desplaza.

De esta manera, los nodos que nunca se ven nunca se cargan desde la base de datos. Funciona bien para desplazarse con la rueda del mouse (con un pequeño retraso ocasional cuando pasa el punto donde la memoria caché está vacía y necesita más datos del disco) y para desplazarse con las teclas/botones de flecha.Es un poco más lento cuando arrastra la barra de desplazamiento a cierta posición (por ejemplo, de abajo hacia el centro), pero eso es de esperar ya que los datos no se pueden obtener del disco de forma instantánea.

Lo mejor es determinar de antemano la cantidad de memoria que quiero usar para la memoria caché/elementos antes de cargarlos, cuanto más rápido sea el desplazamiento pero, por supuesto, utilizará más memoria si los datos nunca se muestran.

Answer 1

Usted está buscando para almacenar datos jerárquicos en una base de datos.
El problema es que SQL no está equipado para tratar este tipo de datos muy bien.

Tiene una serie de soluciones, cada una con sus inconvenientes y ventajas.
Aquí hay un enlace si quieres leer sobre cada uno de los enfoques:

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

Mi favorito personal es Modified Preorder Tree Traversal

Aquí tienda a la izquierda y el nodo justo en la base de datos en una muy contrario a la intuición, lo que hace que las inserciones de los nodos sean un poco lentas, pero la recuperación es muy rápida.

Puede codificar su lógica en Delphi, pero prefiero usar procedimientos almacenados en mi base de datos de elección.
De esa manera su lógica en Delphi se mantiene simple y si la base de datos cambia su código Delphi no tiene que ser así. Si lo desea, puedo incluir el código SQL para los procedimientos almacenados, pero no ahora, porque ese código no está en la computadora portátil que tengo ahora.

Answer 2

No es el más elegante, pero este es el método que utilizo para poblar mis árboles.

Solo requiere acceso de datos para dos consultas sencillas, y el resto se realiza por el lado del cliente.

Cargará decenas de miles de nodos con facilidad. (Mirándolo ahora, probablemente podría salirse con una sola consulta - es un poco viejo!):

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; 

Nota: la columna de la OrderBy es opcional, requiero como mis árboles son un orden específico.

Así que el PP tiene estas tres columnas, además de los datos personalizada que requiere:

ID, ParentID (-1 para ningún padre), OrderNo