sql - ¿Cuál es la forma más eficiente/elegante de analizar una mesa plana en un árbol?
algorithm recursion (14)
Supongamos que tiene una tabla plana que almacena una jerarquía de árboles ordenada:
Id Name ParentId Order
1 ''Node 1'' 0 10
2 ''Node 1.1'' 1 10
3 ''Node 2'' 0 20
4 ''Node 1.1.1'' 2 10
5 ''Node 2.1'' 3 10
6 ''Node 1.2'' 1 20
Aquí hay un diagrama, donde tenemos [id] Name . El nodo raíz 0 es ficticio.
[0] ROOT / / [1] Node 1 [3] Node 2 / / / [2] Node 1.1 [6] Node 1.2 [5] Node 2.1 / [4] Node 1.1.1
¿Qué enfoque minimalista utilizarías para mostrar eso en HTML (o texto, en realidad) como un árbol correctamente ordenado y con sangría?
Supongamos que, además, solo tiene estructuras de datos básicas (matrices y hashmaps), no hay objetos de fantasía con referencias de padres / hijos, no hay ORM, no hay marco, solo sus dos manos. La tabla se representa como un conjunto de resultados, al que se puede acceder de forma aleatoria.
El pseudo código o el inglés simple está bien, esta es una pregunta puramente conceptual.
Pregunta extra: ¿Existe una manera fundamental de almacenar una estructura de árbol como esta en un RDBMS?
EDICIONES Y ADICIONES
Para responder a la pregunta de un comentarista ( Mark Bessey ): un nodo raíz no es necesario, ya que de todos modos nunca se mostrará. ParentId = 0 es la convención para expresar "estos son de nivel superior". La columna Orden define cómo se ordenarán los nodos con el mismo padre.
El "conjunto de resultados" del que hablé puede representarse como una matriz de hashmaps (para permanecer en esa terminología). Porque mi ejemplo estaba destinado a estar ya allí. Algunas respuestas van más allá y lo construyen primero, pero eso está bien.
El árbol puede ser arbitrariamente profundo. Cada nodo puede tener N hijos. Sin embargo, no tenía exactamente en mente un árbol de "millones de entradas".
No confunda mi elección de nombre de nodo (''Nodo 1.1.1'') con algo en lo que pueda confiar. Los nodos también podrían llamarse ''Frank'' o ''Bob'', no hay una estructura de nombres implícita, esto fue simplemente para hacerlo legible.
He publicado mi propia solución para que ustedes puedan hacerla pedazos.
A partir de Oracle 9i, puede utilizar CONECTAR POR.
SELECT LPAD('' '', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)
A partir de SQL Server 2005, puede utilizar una expresión de tabla común (CTE) recursiva.
WITH [NodeList] (
[Id]
, [ParentId]
, [Level]
, [Order]
) AS (
SELECT [Node].[Id]
, [Node].[ParentId]
, 0 AS [Level]
, CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
WHERE [Node].[ParentId] = 0
UNION ALL
SELECT [Node].[Id]
, [Node].[ParentId]
, [NodeList].[Level] + 1 AS [Level]
, [NodeList].[Order] + ''|''
+ CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE('' '', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]
Ambos darán los siguientes resultados.
Name ''Node 1'' '' Node 1.1'' '' Node 1.1.1'' '' Node 1.2'' ''Node 2'' '' Node 2.1''
Ahora que MySQL 8.0 está a punto de publicarse, todas las bases de datos SQL populares admitirán consultas recursivas en la sintaxis estándar.
WITH RECURSIVE MyTree AS (
SELECT * FROM MyTable WHERE ParentId IS NULL
UNION ALL
SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;
Probé consultas recursivas en MySQL 8.0 en mi presentación Recursive Query Throwdown en 2017.
A continuación se muestra mi respuesta original de 2008:
Hay varias formas de almacenar datos estructurados en árbol en una base de datos relacional. Lo que se muestra en su ejemplo utiliza dos métodos:
- Lista de adyacencia (la columna "padre") y
- Enumeración de ruta (los números de puntos en su columna de nombre).
Otra solución se llama Conjuntos anidados , y también se puede almacenar en la misma tabla. Lea " Árboles y jerarquías en SQL para Smarties " por Joe Celko para obtener mucha más información sobre estos diseños.
Normalmente prefiero un diseño llamado Tabla de cierre (también conocido como "Relación de adyacencia") para almacenar datos estructurados en árbol. Requiere otra tabla, pero consultar árboles es bastante fácil.
Cubro Closure Table en mi presentación Modelos para datos jerárquicos con SQL y PHP y en mi libro Antipatterns de SQL: Evitando los escollos de la programación de bases de datos .
CREATE TABLE ClosureTable (
ancestor_id INT NOT NULL REFERENCES FlatTable(id),
descendant_id INT NOT NULL REFERENCES FlatTable(id),
PRIMARY KEY (ancestor_id, descendant_id)
);
Almacene todas las rutas en la Tabla de cierre, donde hay una ascendencia directa de un nodo a otro. Incluya una fila para que cada nodo haga referencia a sí mismo. Por ejemplo, utilizando el conjunto de datos que mostró en su pregunta:
INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
(1,1), (1,2), (1,4), (1,6),
(2,2), (2,4),
(3,3), (3,5),
(4,4),
(5,5),
(6,6);
Ahora puedes obtener un árbol que comienza en el nodo 1 de esta manera:
SELECT f.*
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;
La salida (en el cliente MySQL) se parece a lo siguiente:
+----+
| id |
+----+
| 1 |
| 2 |
| 4 |
| 6 |
+----+
En otras palabras, los nodos 3 y 5 están excluidos, porque forman parte de una jerarquía separada, no descienden del nodo 1.
Re: comentario de e-satis sobre niños inmediatos (o padre inmediato). Puede agregar una columna " path_length " a ClosureTable para facilitar la consulta específica de un hijo o padre inmediato (o cualquier otra distancia).
INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
(1,1,0), (1,2,1), (1,4,2), (1,6,1),
(2,2,0), (2,4,1),
(3,3,0), (3,5,1),
(4,4,0),
(5,5,0),
(6,6,0);
Luego, puede agregar un término en su búsqueda para consultar los hijos inmediatos de un nodo determinado. Estos son descendientes cuyo path_length es 1.
SELECT f.*
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
AND path_length = 1;
+----+
| id |
+----+
| 2 |
| 6 |
+----+
Re comentario de @ashraf: "¿Qué hay de clasificar todo el árbol [por nombre]?"
Aquí hay una consulta de ejemplo para devolver todos los nodos que son descendientes del nodo 1, unirlos a la FlatTable que contiene otros atributos de nodo como el name y ordenarlos por el nombre.
SELECT f.name
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;
Re comentario de @Nate:
SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id)
WHERE a.ancestor_id = 1
GROUP BY a.descendant_id
ORDER BY f.name
+------------+-------------+
| name | breadcrumbs |
+------------+-------------+
| Node 1 | 1 |
| Node 1.1 | 1,2 |
| Node 1.1.1 | 1,2,4 |
| Node 1.2 | 1,6 |
+------------+-------------+
Un usuario sugirió una edición hoy. SO moderadores aprobaron la edición, pero la estoy invirtiendo.
La edición sugirió que ORDER BY en la última consulta anterior debería ser ORDER BY b.path_length, f.name , probablemente para asegurarse de que el orden coincida con la jerarquía. Pero esto no funciona, porque ordenaría "Nodo 1.1.1" después de "Nodo 1.2".
Si desea que el orden coincida con la jerarquía de una manera sensata, es posible, pero no simplemente ordenando por la longitud de la ruta. Por ejemplo, vea mi respuesta a la base de datos jerárquica de la tabla de cierre de MySQL: cómo extraer la información en el orden correcto .
Bien dada la elección, estaría usando objetos. Me gustaría crear un objeto para cada registro donde cada objeto tenga una colección secundaria y almacenarlos en una matriz assoc (/ hashtable) donde el ID es la clave. Y bombardee a través de la colección una vez, agregando a los niños a los campos de niños relevantes. Sencillo.
Pero debido a que no te estás divirtiendo al restringir el uso de un buen OOP, probablemente lo repetiría en función de:
function PrintLine(int pID, int level)
foreach record where ParentID == pID
print level*tabs + record-data
PrintLine(record.ID, level + 1)
PrintLine(0, 0)
Edición: esto es similar a un par de otras entradas, pero creo que es un poco más limpio. Una cosa que agregaré: esto es extremadamente intensivo en SQL. Es desagradable Si tiene la opción, vaya a la ruta OOP.
Es una pregunta bastante antigua, pero como tiene muchos puntos de vista, creo que vale la pena presentar una solución alternativa, y en mi opinión muy elegante.
Para leer una estructura de árbol puede usar expresiones de tabla comunes (CTE) recursivas. Brinda la posibilidad de obtener toda la estructura de árbol a la vez, tener la información sobre el nivel del nodo, su nodo principal y el orden dentro de los hijos del nodo principal.
Déjame mostrarte cómo funcionaría esto en PostgreSQL 9.1.
Crear una estructura
CREATE TABLE tree ( id int NOT NULL, name varchar(32) NOT NULL, parent_id int NULL, node_order int NOT NULL, CONSTRAINT tree_pk PRIMARY KEY (id), CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) REFERENCES tree (id) NOT DEFERRABLE ); insert into tree values (0, ''ROOT'', NULL, 0), (1, ''Node 1'', 0, 10), (2, ''Node 1.1'', 1, 10), (3, ''Node 2'', 0, 20), (4, ''Node 1.1.1'', 2, 10), (5, ''Node 2.1'', 3, 10), (6, ''Node 1.2'', 1, 20);Escribe una consulta
WITH RECURSIVE tree_search (id, name, level, parent_id, node_order) AS ( SELECT id, name, 0, parent_id, 1 FROM tree WHERE parent_id is NULL UNION ALL SELECT t.id, t.name, ts.level + 1, ts.id, t.node_order FROM tree t, tree_search ts WHERE t.parent_id = ts.id ) SELECT * FROM tree_search WHERE level > 0 ORDER BY level, parent_id, node_order;Aquí están los resultados:
id | name | level | parent_id | node_order ----+------------+-------+-----------+------------ 1 | Node 1 | 1 | 0 | 10 3 | Node 2 | 1 | 0 | 20 2 | Node 1.1 | 2 | 1 | 10 6 | Node 1.2 | 2 | 1 | 20 5 | Node 2.1 | 2 | 3 | 10 4 | Node 1.1.1 | 3 | 2 | 10 (6 rows)Los nodos del árbol están ordenados por un nivel de profundidad. En la salida final los presentaríamos en las líneas posteriores.
Para cada nivel, están ordenados por parent_id y node_order dentro del padre. Esto nos dice cómo presentarlos en el nodo de enlace de salida al padre en este orden.
Teniendo tal estructura, no sería difícil hacer una presentación realmente agradable en HTML.
Los CTE recursivos están disponibles en PostgreSQL, IBM DB2, MS SQL Server y Oracle .
Si desea leer más sobre consultas SQL recursivas, puede consultar la documentación de su DBMS favorito o leer mis dos artículos que cubren este tema:
Esto fue escrito rápidamente, y no es bonito ni eficiente (además de que se autoxoxiza mucho, ¡convertir entre int y Integer es molesto!), Pero funciona.
Probablemente rompe las reglas ya que estoy creando mis propios objetos, pero bueno, estoy haciendo esto como una desviación del trabajo real :)
Esto también supone que el resultSet / table se lee completamente en algún tipo de estructura antes de comenzar a construir Nodos, lo que no sería la mejor solución si tiene cientos de miles de filas.
public class Node {
private Node parent = null;
private List<Node> children;
private String name;
private int id = -1;
public Node(Node parent, int id, String name) {
this.parent = parent;
this.children = new ArrayList<Node>();
this.name = name;
this.id = id;
}
public int getId() {
return this.id;
}
public String getName() {
return this.name;
}
public void addChild(Node child) {
children.add(child);
}
public List<Node> getChildren() {
return children;
}
public boolean isRoot() {
return (this.parent == null);
}
@Override
public String toString() {
return "id=" + id + ", name=" + name + ", parent=" + parent;
}
}
public class NodeBuilder {
public static Node build(List<Map<String, String>> input) {
// maps id of a node to it''s Node object
Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();
// maps id of a node to the id of it''s parent
Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();
// create special ''root'' Node with id=0
Node root = new Node(null, 0, "root");
nodeMap.put(root.getId(), root);
// iterate thru the input
for (Map<String, String> map : input) {
// expect each Map to have keys for "id", "name", "parent" ... a
// real implementation would read from a SQL object or resultset
int id = Integer.parseInt(map.get("id"));
String name = map.get("name");
int parent = Integer.parseInt(map.get("parent"));
Node node = new Node(null, id, name);
nodeMap.put(id, node);
childParentMap.put(id, parent);
}
// now that each Node is created, setup the child-parent relationships
for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
int nodeId = entry.getKey();
int parentId = entry.getValue();
Node child = nodeMap.get(nodeId);
Node parent = nodeMap.get(parentId);
parent.addChild(child);
}
return root;
}
}
public class NodePrinter {
static void printRootNode(Node root) {
printNodes(root, 0);
}
static void printNodes(Node node, int indentLevel) {
printNode(node, indentLevel);
// recurse
for (Node child : node.getChildren()) {
printNodes(child, indentLevel + 1);
}
}
static void printNode(Node node, int indentLevel) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indentLevel; i++) {
sb.append("/t");
}
sb.append(node);
System.out.println(sb.toString());
}
public static void main(String[] args) {
// setup dummy data
List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
resultSet.add(newMap("1", "Node 1", "0"));
resultSet.add(newMap("2", "Node 1.1", "1"));
resultSet.add(newMap("3", "Node 2", "0"));
resultSet.add(newMap("4", "Node 1.1.1", "2"));
resultSet.add(newMap("5", "Node 2.1", "3"));
resultSet.add(newMap("6", "Node 1.2", "1"));
Node root = NodeBuilder.build(resultSet);
printRootNode(root);
}
//convenience method for creating our dummy data
private static Map<String, String> newMap(String id, String name, String parentId) {
Map<String, String> row = new HashMap<String, String>();
row.put("id", id);
row.put("name", name);
row.put("parent", parentId);
return row;
}
}
Hay soluciones realmente buenas que explotan la representación interna de btree de los índices de SQL. Esto se basa en una gran investigación realizada alrededor de 1998.
Aquí hay una tabla de ejemplo (en mysql).
CREATE TABLE `node` (
`id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`name` varchar(255) NOT NULL,
`tw` int(10) unsigned NOT NULL,
`pa` int(10) unsigned DEFAULT NULL,
`sz` int(10) unsigned DEFAULT NULL,
`nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
PRIMARY KEY (`id`),
KEY `node_tw_index` (`tw`),
KEY `node_pa_index` (`pa`),
KEY `node_nc_index` (`nc`),
CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)
Los únicos campos necesarios para la representación del árbol son:
- tw: El índice de pre-pedido DFS de izquierda a derecha, donde root = 1.
- pa: La referencia (usando tw) al nodo padre, la raíz tiene un valor nulo.
- sz: El tamaño de la rama del nodo incluyéndose a sí mismo.
- nc: se utiliza como azúcar sintáctica. es tw + nc y representa el tw del "siguiente hijo" del nodo.
Aquí hay un ejemplo de 24 nodos de población, ordenados por tw:
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 1 | Root | 1 | NULL | 24 | 25 |
| 2 | A | 2 | 1 | 14 | 16 |
| 3 | AA | 3 | 2 | 1 | 4 |
| 4 | AB | 4 | 2 | 7 | 11 |
| 5 | ABA | 5 | 4 | 1 | 6 |
| 6 | ABB | 6 | 4 | 3 | 9 |
| 7 | ABBA | 7 | 6 | 1 | 8 |
| 8 | ABBB | 8 | 6 | 1 | 9 |
| 9 | ABC | 9 | 4 | 2 | 11 |
| 10 | ABCD | 10 | 9 | 1 | 11 |
| 11 | AC | 11 | 2 | 4 | 15 |
| 12 | ACA | 12 | 11 | 2 | 14 |
| 13 | ACAA | 13 | 12 | 1 | 14 |
| 14 | ACB | 14 | 11 | 1 | 15 |
| 15 | AD | 15 | 2 | 1 | 16 |
| 16 | B | 16 | 1 | 1 | 17 |
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
| 18 | D | 23 | 1 | 1 | 24 |
| 19 | E | 24 | 1 | 1 | 25 |
+-----+---------+----+------+------+------+
Cada resultado del árbol se puede hacer de forma no recursiva. Por ejemplo, para obtener una lista de ancestros de nodo en tw = ''22 ''
Los antepasados
select anc.* from node me,node anc
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw
order by anc.tw;
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 1 | Root | 1 | NULL | 24 | 25 |
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
+-----+---------+----+------+------+------+
Los hermanos y los niños son triviales, solo use el orden de campo pa por tw.
Descendientes
Por ejemplo, el conjunto (rama) de nodos que están enraizados en tw = 17.
select des.* from node me,node des
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw
order by des.tw;
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
+-----+---------+----+------+------+------+
Notas adicionales
Esta metodología es extremadamente útil para cuando hay un número mucho mayor de lecturas que inserciones o actualizaciones.
Debido a que la inserción, movimiento o actualización de un nodo en el árbol requiere que el árbol se ajuste, es necesario bloquear la tabla antes de comenzar con la acción.
El costo de inserción / eliminación es alto porque los valores del índice tw y sz (tamaño de rama) deberán actualizarse en todos los nodos después del punto de inserción, y para todos los ancestros respectivamente.
El movimiento de rama implica mover el valor tw de la rama fuera de rango, por lo que también es necesario deshabilitar las restricciones de clave externa al mover una rama. Hay, esencialmente, cuatro consultas requeridas para mover una rama:
- Mueve la rama fuera de rango.
- Cierra la brecha que dejó. (El árbol restante ahora está normalizado).
- Abre el hueco donde irá.
- Mueve la rama a su nueva posición.
Ajustar consultas de árbol
La apertura / cierre de brechas en el árbol es una subfunción importante utilizada por los métodos de creación / actualización / eliminación, por lo que la incluyo aquí.
Necesitamos dos parámetros: una marca que represente si estamos reduciendo o cambiando el tamaño y el índice tw del nodo. Entonces, por ejemplo, tw = 18 (que tiene un tamaño de rama de 5). Supongamos que estamos reduciendo (eliminando tw); esto significa que estamos usando ''-'' en lugar de ''+'' en las actualizaciones del siguiente ejemplo.
Primero usamos una función ancestral (ligeramente alterada) para actualizar el valor sz.
update node me, node anc set anc.sz = anc.sz - me.sz from
node me, node anc where me.tw=18
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));
Luego debemos ajustar el tw para aquellos cuyo tw es más alto que la rama que se va a eliminar.
update node me, node anc set anc.tw = anc.tw - me.sz from
node me, node anc where me.tw=18 and anc.tw >= me.tw;
Luego necesitamos ajustar el padre para aquellos cuyo tw de pa es más alto que la rama que se eliminará.
update node me, node anc set anc.pa = anc.pa - me.sz from
node me, node anc where me.tw=18 and anc.pa >= me.tw;
La respuesta de Bill es bastante buena, esta respuesta le agrega algunas cosas, lo que me hace desear que SO apoyara respuestas enraizadas.
De todos modos quería apoyar la estructura de árbol y la propiedad Orden. leftSibling una propiedad individual en cada Nodo llamado leftSibling que hace lo mismo que Order debe hacer en la pregunta original (mantener el orden de izquierda a derecha).
mysql> desc nodes ; +-------------+--------------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +-------------+--------------+------+-----+---------+----------------+ | id | int(11) | NO | PRI | NULL | auto_increment | | name | varchar(255) | YES | | NULL | | | leftSibling | int(11) | NO | | 0 | | +-------------+--------------+------+-----+---------+----------------+ 3 rows in set (0.00 sec) mysql> desc adjacencies; +------------+---------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +------------+---------+------+-----+---------+----------------+ | relationId | int(11) | NO | PRI | NULL | auto_increment | | parent | int(11) | NO | | NULL | | | child | int(11) | NO | | NULL | | | pathLen | int(11) | NO | | NULL | | +------------+---------+------+-----+---------+----------------+ 4 rows in set (0.00 sec)
Más detalles y código SQL en mi blog .
Gracias Bill, tu respuesta fue útil para empezar.
Para extender la solución SQL de Bill, básicamente puede hacer lo mismo utilizando una matriz plana. Además, si todas las cadenas tienen la misma longitud y se conoce el número máximo de hijos (por ejemplo, en un árbol binario), puede hacerlo utilizando una sola cadena (matriz de caracteres). Si tiene un número arbitrario de niños, esto complica un poco las cosas ... Tendría que revisar mis notas anteriores para ver qué se puede hacer.
Luego, sacrificando un poco de memoria, especialmente si su árbol es escaso o no balanceado, puede, con un poco de índice matemático, acceder a todas las cadenas aleatoriamente almacenando su árbol, primero el ancho en la matriz, así (para un binario árbol):
String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...
Sabes tu longitud de cuerda, lo sabes
Estoy en el trabajo ahora, así que no puedo dedicarle mucho tiempo, pero con interés puedo obtener un poco de código para hacer esto.
Lo utilizamos para buscar en árboles binarios hechos de codones de ADN, un proceso que construyó el árbol, luego lo aplanamos para buscar patrones de texto y cuando lo encontramos, aunque el índice de matemáticas (a la inversa de arriba) recuperamos el nodo ... muy Rápido y eficiente, difícilmente nuestro árbol rara vez tenía nodos vacíos, pero podíamos capturar gigabytes de datos en un santiamén.
Piense en usar herramientas nosql como neo4j para estructuras jerárquicas. por ejemplo, una aplicación en red como linkedin usa couchbase (otra solución de nosql)
Pero use nosql solo para consultas de nivel de data mart y no para almacenar / mantener transacciones
Puedes emular cualquier otra estructura de datos con un hashmap, por lo que no es una limitación terrible. Al escanear desde la parte superior a la inferior, crea un hashmap para cada fila de la base de datos, con una entrada para cada columna. Agrega cada uno de estos hashmaps a un hashmap "maestro", con clave en el id. Si algún nodo tiene un "padre" que aún no ha visto, cree una entrada de marcador de posición para él en el hashmap maestro y rellénelo cuando vea el nodo real.
Para imprimirlo, realice una simple pasada en profundidad a través de los datos, manteniendo un registro del nivel de sangría en el camino. Puede hacer esto más fácil manteniendo una entrada "secundaria" para cada fila y rellenándola mientras escanea los datos.
En cuanto a si hay una "mejor" forma de almacenar un árbol en una base de datos, eso depende de cómo se usen los datos. He visto sistemas que tenían una profundidad máxima conocida que usaba una tabla diferente para cada nivel en la jerarquía. Eso tiene mucho sentido si los niveles en el árbol no son muy equivalentes después de todo (las categorías de nivel superior son diferentes a las hojas).
Si los elementos están en orden de árbol, como se muestra en su ejemplo, puede usar algo como el siguiente ejemplo de Python:
delimiter = ''.''
stack = []
for item in items:
while stack and not item.startswith(stack[-1]+delimiter):
print "</div>"
stack.pop()
print "<div>"
print item
stack.append(item)
Lo que esto hace es mantener una pila que representa la posición actual en el árbol. Para cada elemento de la tabla, hace estallar elementos de la pila (cerrando los divs coincidentes) hasta que encuentra el elemento primario del elemento actual. Luego genera el inicio de ese nodo y lo empuja hacia la pila.
Si desea generar el árbol usando sangría en lugar de elementos anidados, simplemente puede omitir las declaraciones de impresión para imprimir los divs e imprimir una cantidad de espacios igual a algunos múltiplos del tamaño de la pila antes de cada elemento. Por ejemplo, en Python:
print " " * len(stack)
También podría usar fácilmente este método para construir un conjunto de listas o diccionarios anidados.
Edición: veo por su aclaración que los nombres no estaban destinados a ser rutas de nodo. Eso sugiere un enfoque alternativo:
idx = {}
idx[0] = []
for node in results:
child_list = []
idx[node.Id] = child_list
idx[node.ParentId].append((node, child_list))
Esto construye un árbol de matrices de tuplas (!). idx [0] representa la (s) raíz (s) del árbol. Cada elemento de una matriz es una tupla de 2 que consta del nodo en sí y una lista de todos sus elementos secundarios. Una vez construido, puedes aferrarte a idx [0] y descartar idx, a menos que quieras acceder a los nodos por su ID.
Si se pueden crear matrices o mapas hash anidados, entonces simplemente puedo bajar la tabla desde el principio y agregar cada elemento a la matriz anidada. Debo rastrear cada línea hasta el nodo raíz para saber en qué nivel de la matriz anidada insertar. Puedo emplear la memoria para no tener que buscar al mismo padre una y otra vez.
Edición: primero leería toda la tabla en una matriz, por lo que no consultará el DB repetidamente. Por supuesto, esto no será práctico si su mesa es muy grande.
Después de que se construya la estructura, primero debo hacer un recorrido profundo a través de ella e imprimir el HTML.
No hay una mejor manera fundamental de almacenar esta información utilizando una tabla (aunque podría estar equivocada;) y me encantaría ver una mejor solución. Sin embargo, si crea un esquema para emplear tablas de db creadas dinámicamente, entonces abre un mundo completamente nuevo a costa de la simplicidad y el riesgo del infierno de SQL;).
Si usa conjuntos anidados (a veces denominados Traversal de árbol de pedido previo modificado) puede extraer toda la estructura de árbol o cualquier subárbol dentro de él en orden de árbol con una sola consulta, a un costo de inserciones que son más costosas, como necesita gestione columnas que describan una ruta en orden a través de la estructura de árbol.
Para django-mptt , usé una estructura como esta:
id parent_id tree_id level lft rght -- --------- ------- ----- --- ---- 1 null 1 0 1 14 2 1 1 1 2 7 3 2 1 2 3 4 4 2 1 2 5 6 5 1 1 1 8 13 6 5 1 2 9 10 7 5 1 2 11 12
Lo que describe un árbol que se ve así (con id representa cada elemento):
1 +-- 2 | +-- 3 | +-- 4 | +-- 5 +-- 6 +-- 7
O, como un diagrama de conjunto anidado que hace más obvio cómo funcionan los valores lft y rght :
__________________________________________________________________________ | Root 1 | | ________________________________ ________________________________ | | | Child 1.1 | | Child 1.2 | | | | ___________ ___________ | | ___________ ___________ | | | | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | | 1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14 | |________________________________| |________________________________| | |__________________________________________________________________________|
Como puede ver, para obtener el subárbol completo para un nodo determinado, en el orden de árbol, simplemente tiene que seleccionar todas las filas que tengan valores lft y rght entre sus valores lft y rght . También es sencillo recuperar el árbol de ancestros para un nodo determinado.
La columna de level es un poco de desnormalización por conveniencia más que nada, y la columna tree_id permite reiniciar la numeración de lft y rght para cada nodo de nivel superior, lo que reduce el número de columnas afectadas por inserciones, movimientos y eliminaciones, como el lft y las columnas de rght deben ajustarse en consecuencia cuando estas operaciones tienen lugar para crear o cerrar brechas. Hice algunas notas de desarrollo en el momento en que intentaba envolver mi cabeza en torno a las consultas requeridas para cada operación.
En términos de trabajar realmente con estos datos para mostrar un árbol, creé una función de utilidad tree_item_iterator que, para cada nodo, debería proporcionarle información suficiente para generar cualquier tipo de visualización que desee.
Más información sobre MPTT:
Suponiendo que sabe que los elementos raíz son cero, aquí está el pseudocódigo para generar un texto:
function PrintLevel (int curr, int level)
//print the indents
for (i=1; i<=level; i++)
print a tab
print curr /n;
for each child in the table with a parent of curr
PrintLevel (child, level+1)
for each elementID where the parentid is zero
PrintLevel(elementID, 0)