¿Cómo se representa un árbol de datos en SQL?

Question

Estoy escribiendo una estructura de árbol de datos que se combina desde un árbol y un TreeNode. Tree contendrá la raíz y las acciones de nivel superior en los datos. Estoy usando una biblioteca de IU para presentar el árbol en un formulario de Windows donde puedo vincular el árbol a TreeView.

Necesitaré guardar este árbol y nodos en la base de datos. Cuál será la mejor manera de guardar el árbol y obtener las siguientes características:

1. Implementación intuitiva.
2. Unión fácil. Será fácil pasar del árbol a la estructura de la base de datos y viceversa (si corresponde)

Tenía 2 ideas. El primero es serializar los datos en un único trazador de líneas en una tabla. El segundo es guardar en tablas, pero luego, al moverme a las entidades de datos, perderé los estados de las filas en la tabla en los nodos modificados.

¿Alguna idea?

Answer 1

Depende de cómo va a consultar y actualizar los datos. Si almacena todos los datos en una fila, es básicamente una sola unidad en la que no puede realizar consultas o actualizar parcialmente sin volver a escribir todos los datos.

Si desea almacenar cada elemento como una fila, primero debe leer Managing Hierarchical Data in MySQL (específico de MySQL, pero el consejo se aplica a muchas otras bases de datos también).

Si solo está accediendo a un árbol completo, el modelo de lista de adyacencia hace que sea difícil recuperar todos los nodos bajo la raíz sin usar una consulta recursiva. Si agrega una columna adicional que enlaza con el encabezado, puede hacer SELECT * WHERE head_id = @id y obtener todo el árbol en una consulta no recursiva, pero desnormaliza la base de datos.

Algunas bases de datos tienen extensiones personalizadas que facilitan el almacenamiento y la recuperación de datos jerárquicos; por ejemplo, Oracle tiene CONNECT BY.

Answer 2

La aplicación más fácil es lista de adyacencia estructura:

id parent_id data 

Sin embargo, algunas bases de datos, en particular MySQL, tienen algunos problemas en el manejo de este modelo, ya que requiere una habilidad para ejecutar consultas recursivas, que MySQL carece.

Otro modelo es conjuntos anidados:

id lft rgt data 

donde lft y rgt son valores arbitrarios que definen la jerarquía (de lft cualquier niño, rgt debe estar dentro de cualquier padre de lft, rgt)

Este no requiere consultas recursivas, pero es más lento y más difícil de mantener.

Sin embargo, en MySQL esto se puede mejorar utilizando SPATIAL abitilies.

Consulte estos artículos en mi blog:

• Adjacency list vs. nested sets: PostgreSQL
• Adjacency list vs. nested sets: SQL Server
• Adjacency list vs. nested sets: Oracle
• Adjacency list vs. nested sets: MySQL

explicaciones más detalladas.

Answer 3

Algo así como la tabla de "nodos" donde cada fila nodo contiene ID de padre (además de los datos del nodo ordinarias). Para root, el padre es NULL.

Por supuesto, esto hace que la búsqueda de niños que consumen un poco más de tiempo, pero de esta manera la base de datos real será bastante simple.

Answer 4

que he marcado esta SlideShare acerca de SQL-antipatterns, que analiza varias alternativas: http://www.slideshare.net/billkarwin/sql-antipatterns-strike-back?src=embed

La recomendación de que hay que utilizar una tabla de cierre (se explica en las diapositivas).

Aquí está el resumen (diapositiva 77):

    | Query Child | Query Subtree | Modify Tree | Ref. Integrity 
Adjacency List | Easy  |  Hard  | Easy  |  Yes 
Path Enumeration | Easy  |  Easy  | Hard  |  No 
Nested Sets  | Hard  |  Easy  | Hard  |  No 
Closure Table  | Easy  |  Easy  | Easy  |  Yes 

Answer 5

La mejor manera, creo que de hecho es dar a cada nodo un identificador y una parent_id, donde el ID de padre es el id del nodo padre. Esto tiene un par de ventajas

1. Cuando quiere actualizar un nodo, solo tiene que volver a escribir los datos de ese nodo.
2. Cuando desea consultar solo un nodo determinado, puede obtener exactamente la información que desea, teniendo menos sobrecarga en la conexión de la base de datos
3. Muchos lenguajes de programación tienen la funcionalidad de transformar datos mysql en XML o json, que facilitará la apertura de su aplicación con una API.

Answer 6

Estoy sorprendido de que nadie mencionó la trayectoria materializada solución, que es probablemente la manera más rápida de trabajar con los árboles en SQL estándar.

En este enfoque, cada nodo en el árbol tiene una columna ruta, donde se almacena la ruta completa desde la raíz hasta el nodo. Esto implica consultas muy simples y rápidas.

Tener un vistazo a la tabla de ejemplo nodo:

+---------+-------+ 
| node_id | path | 
+---------+-------+ 
| 0  |  | 
| 1  | 1  | 
| 2  | 2  | 
| 3  | 3  | 
| 4  | 1.4 | 
| 5  | 2.5 | 
| 6  | 2.6 | 
| 7  | 2.6.7 | 
| 8  | 2.6.8 | 
| 9  | 2.6.9 | 
+---------+-------+ 

Con el fin de conseguir los hijos del nodo x, se puede escribir la siguiente consulta:

SELECT * FROM node WHERE path LIKE CONCAT((SELECT path FROM node WHERE node_id = x), '.%') 

Tenga en importa, que el camino de la columna debe ser indexado, con el fin de llevar a cabo rápidamente con el Noel COMO mi.

Answer 7

Si está utilizando PostgreSQL puede usar ltree, un paquete en la extensión contrib (viene por defecto) que implementa la estructura de datos del árbol.

Desde el docs:

CREATE TABLE test (path ltree); 
INSERT INTO test VALUES ('Top'); 
INSERT INTO test VALUES ('Top.Science'); 
INSERT INTO test VALUES ('Top.Science.Astronomy'); 
INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics'); 
INSERT INTO test VALUES ('Top.Science.Astronomy.Cosmology'); 
INSERT INTO test VALUES ('Top.Hobbies'); 
INSERT INTO test VALUES ('Top.Hobbies.Amateurs_Astronomy'); 
INSERT INTO test VALUES ('Top.Collections'); 
INSERT INTO test VALUES ('Top.Collections.Pictures'); 
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy'); 
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Stars'); 
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies'); 
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts'); 
CREATE INDEX path_gist_idx ON test USING GIST (path); 
CREATE INDEX path_idx ON test USING BTREE (path); 

Usted puede hacer preguntas como:

ltreetest=> SELECT path FROM test WHERE path <@ 'Top.Science'; 
       path 
------------------------------------ 
Top.Science 
Top.Science.Astronomy 
Top.Science.Astronomy.Astrophysics 
Top.Science.Astronomy.Cosmology 
(4 rows)