Estructura de base de datos para estructura de datos de árbol

151

¿Cuál sería la mejor manera de implementar una estructura de datos de árbol personalizable (es decir, una estructura de árbol con un número desconocido de nivel) en una base de datos?

He hecho esto una vez antes de usar una tabla con una clave foránea para sí mismo.

¿Qué otras implementaciones podrías ver, y tiene sentido esta implementación?

sql database-design tree CodeMonkey1313
fuente
3
Consulte: ¿Cuáles son las opciones para almacenar datos jerárquicos en una base de datos relacional?
cbare
SQL Server (desde 2008) ofrece el tipo de datos de jerarquía
BornToCode

Respuestas:

80

Menciona el más comúnmente implementado, que es la Lista de adyacencia: https://blogs.msdn.microsoft.com/mvpawardprogram/2012/06/25/hierarchies-convert-adjacency-list-to-nested-sets

También hay otros modelos, que incluyen rutas materializadas y conjuntos anidados: http://communities.bmc.com/communities/docs/DOC-9902

Joe Celko ha escrito un libro sobre este tema, que es una buena referencia desde una perspectiva general de SQL (se menciona en el enlace del artículo conjunto anidado anterior).

Además, Itzik Ben-Gann tiene una buena visión general de las opciones más comunes en su libro "Inside Microsoft SQL Server 2005: T-SQL Querying".

Los principales puntos a considerar al elegir un modelo son:

1) Frecuencia de cambio de estructura: con qué frecuencia cambia la estructura real del árbol. Algunos modelos proporcionan mejores características de actualización de estructura. Sin embargo, es importante separar los cambios de estructura de otros cambios de datos. Por ejemplo, es posible que desee modelar el organigrama de una empresa. Algunas personas modelarán esto como una lista de adyacencia, utilizando la ID del empleado para vincular a un empleado con su supervisor. Este suele ser un enfoque subóptimo. Un enfoque que a menudo funciona mejor es modelar la estructura de la organización por separado de los propios empleados y mantener al empleado como un atributo de la estructura. De esta manera, cuando un empleado deja la empresa, la estructura organizativa en sí misma no necesita ser cambios, solo la asociación con el empleado que se fue.

2) ¿El árbol es pesado para escribir o pesado? Algunas estructuras funcionan muy bien cuando se lee la estructura, pero incurren en gastos generales adicionales al escribir en la estructura.

3) ¿Qué tipo de información necesita obtener de la estructura? Algunas estructuras se destacan por proporcionar ciertos tipos de información sobre la estructura. Los ejemplos incluyen encontrar un nodo y todos sus elementos secundarios, encontrar un nodo y todos sus padres, encontrar el número de nodos secundarios que cumplen ciertas condiciones, etc. Debe saber qué información se necesitará de la estructura para determinar la estructura que mejor se ajuste tus necesidades.

JeremyDWill
fuente
Hola, me enfrento exactamente al mismo problema que aparece en la pregunta y me gustaría hacerle una pregunta sobre los temas anteriores. Teniendo en cuenta una estructura como en el tema número uno (tabla estructurada organizacional (no estructurada por el empleado) con ParentId referenciado en la misma tabla), necesito establecer quién es el jefe de un área determinada. Asignaré a todos los empleados de esa área específica directamente. ¿Dónde pondrías al jefe de esa área específica? ¿Dentro de la misma área o un grupo arriba? Mi enfoque es referirlo al grupo de arriba, eso me da una mejor estructura, creo. Gracias.
Marcos Buarque
1
El primer enlace parece estar roto.
Jorge Leitao
Excelente respuesta Gracias @JeremyDWill!
bobocopy
56

Eche un vistazo a Gestión de datos jerárquicos en MySQL . Discute dos enfoques para almacenar y administrar datos jerárquicos (en forma de árbol) en una base de datos relacional.

El primer enfoque es el modelo de lista de adyacencia, que es lo que esencialmente describe: tener una clave externa que se refiere a la tabla misma. Si bien este enfoque es simple, puede ser muy ineficiente para ciertas consultas, como construir todo el árbol.

El segundo enfoque discutido en el artículo es el modelo de conjunto anidado. Este enfoque es mucho más eficiente y flexible. Consulte el artículo para obtener explicaciones detalladas y consultas de ejemplo.

Ayman Hourieh
fuente
su enlace tiene un tema muy interesante en discusión. ¡Gracias!
Fritz
9

Si tiene que usar la base de datos relacional para organizar la estructura de datos de árbol, Postgresql tiene un módulo ltree genial que proporciona el tipo de datos para representar etiquetas de datos almacenados en una estructura jerárquica similar a un árbol. Puede obtener la idea desde allí. (Para obtener más información, consulte: http://www.postgresql.org/docs/9.0/static/ltree.html )

En común LDAP se utiliza para organizar registros en estructura jerárquica.

yurilo
fuente
2

Tener una mesa con una clave foránea para sí tiene sentido para mí.

A continuación, puede usar una expresión de tabla común en SQL o la instrucción connect by before en Oracle para construir su árbol.

Aaron Daniels
fuente
Tengo una tabla de registro, con una columna de identidad LogID, y una columna ParentLogID con un FK que apunta de nuevo a la columna LogID. Cuando se escribe la primera fila de registro en una transacción, tomo SCOPE_IDENTITY (). Todos los demás registros se escriben con este valor en la columna ParentLogID. Esto es realmente útil para agrupar filas que pertenecen juntas. Es la única forma real de ver lo que sucedió, sin esto, sería un gran desastre de filas de registro de múltiples transacciones, todas mezcladas.
KM.
@ KM - Dijo "tiene sentido" no "no tiene sentido"
John Rasch
1

He usado la siguiente implementación en SQL SERVER 2005. Marque aquí

emzero
fuente