609 votos

¿Cuáles son las opciones para almacenar datos jerárquicos en una base de datos relacional?

Las Buenas Descripciones

Generalmente hablando, usted está haciendo una decisión rápido entre los tiempos de lectura (p. ej. conjunto anidado) o de escritura rápida veces (lista de adyacencia). Por lo general, usted termina con una combinación de las siguientes opciones que mejor se adapten a sus necesidades. La siguiente proporciona algunos en la medición de la profundidad:

Opciones

Que yo soy consciente y características generales:

  1. Lista De Adyacencia:
    • Columnas: ID, ParentID
    • Fácil de implementar.
    • Hoteles de nodo se mueve, inserciones y eliminaciones.
    • Caro, difícil de encontrar de nivel (puede almacenar como una columna calculada), ancestros y descendientes (Puente de la Tabla combinada con el nivel de la columna puede resolver), la ruta (Linaje de la Columna puede resolver).
    • Uso de Expresiones de Tabla Comunes en las bases de datos que apoyan que las atraviesan.
  2. Conjunto anidado (a.k.a Modificado Preorden del Árbol de Recorrido)
    • Popularizado por Joe Celko en numerosos artículos y en su libro" Árboles y las Jerarquías en SQL para Lacasitos
    • Columnas: A La Izquierda, A La Derecha
    • Hoteles de nivel, ascendencia, descendencia
    • En comparación a la Lista de Adyacencia, se mueve, inserta, elimina más caro.
    • Se requiere un orden de clasificación específico (por ej. creado). Para la clasificación de todos los descendientes en un orden diferente, requiere un trabajo adicional.
  3. Intervalos Anidados
    • La combinación de Conjuntos Anidados y se Materializó Ruta de acceso donde la izquierda/a la derecha de las columnas de punto flotante son decimales en lugar de los números enteros y codificar la información de ruta de acceso. En el desarrollo posterior de esta idea anidadas intervalos dio lugar a la matriz de codificación.
  4. Tabla de puente (a.k.a. Cierre de la Tabla: algunas buenas ideas acerca de cómo utilizar desencadenadores para el mantenimiento de este enfoque)
    • Columnas: ancestro, descendiente
    • Se destaca de la tabla que describe.
    • Puede incluir algunos nodos en más de una jerarquía.
    • Hoteles de ascendencia y descendencia (aunque no se en qué orden)
    • Para completar el conocimiento de una jerarquía de necesidades a ser combinada con otra opción.
  5. Tabla Plana
    • Una modificación de la Lista de Adyacencia que añade un Nivel y Rango (por ej. el pedido) columna para cada registro.
    • Caro mover y eliminar
    • Hoteles de ascendencia y descendencia
    • Buen Uso: hilo de discusión de foros / comentarios del blog
  6. Columna de linaje (a.k.a. Ruta Materializada, La Ruta De La Enumeración)
    • Columna: el linaje (por ej. /padre/hijo/nieto/etc...)
    • Límite a la profundidad de la jerarquía puede ser.
    • Descendientes barato (por ej. LEFT(lineage, #) = '/enumerated/path')
    • De ascendencia difícil (base de datos de consultas específicas)
  7. Múltiples linaje columnas
    • Columnas: una para cada linaje nivel, se refiere a todos los padres a la raíz, disminuyen los niveles de los elementos de nivel se establecen en NULL
    • Límite a la profundidad de la jerarquía puede ser
    • Hoteles de antepasados, descendientes, nivel
    • Hoteles de insertar, eliminar, mover de las hojas
    • Caro insertar, eliminar, mover de los nodos internos

Base De Datos De Las Notas Específicas De La

MySQL

Oracle

PostgreSQL

SQL Server

  • Resumen General
  • 2008 ofrece HierarchyId tipo de datos aparece para ayudar con el Linaje de la Columna de enfoque y ampliar la profundidad que puede ser representado.

84voto

Tegiri Nenashi Puntos 1529

Esta es una pregunta que todavía es muy interesante, incluso después de que los 3 grandes vendedores implementado Recursiva WITH cláusula. Quisiera sugerir que los diferentes lectores estaría complacido con diferentes respuestas.

  1. Lista completa de las referencias por Troels Arvin.
  2. Por la falta de competencia, introducción al libro de texto por Joe Celko "los Árboles y las Jerarquías en SQL para Lacasitos" de hecho puede ser considerado un clásico.
  3. El examen de diversos árbol de codificaciones con énfasis en los intervalos anidados.

32voto

Quassnoi Puntos 191041

14voto

Paul Morgan Puntos 6058

Joe Celko escribió el libro sobre SQL Árboles y Hiearichies

Esta es la primera edición. Mira la segunda edición en el comentario de Bob.

12voto

CesarGon Puntos 8710

Esta es una visión muy parcial respuesta a tu pregunta, pero espero que todavía útil.

Microsoft SQL Server 2008 implementa dos funciones que son muy útiles para la gestión de datos jerárquicas:

  • el HierarchyId tipo de datos.
  • expresiones de tabla comunes, mediante la con la palabra clave.

Eche un vistazo a este artículo para el comienzo. Ver también mi propia pregunta aquí.

11voto

Jeff Moden Puntos 1279

Mi favorita respuesta es como lo de la primera frase en este hilo sugerido. El uso de una Lista de Adyacencia para mantener la jerarquía y uso de Conjuntos Anidados para la consulta de la jerarquía.

El problema hasta ahora ha sido que la coversion método de un Adjacecy Lista Anidada Conjuntos ha sido espantosamente lento debido a que la mayoría de la gente utilice la extrema RBAR método conocido como un "Empuje de la Pila" para hacer la conversión y ha sido considerado para ser bastante caros para alcanzar el Nirvana de la simplicidad de mantenimiento por la Adyacencia de la Lista y el impresionante rendimiento de Conjuntos Anidados. Como resultado, la mayoría de las personas terminan teniendo que conformarse con uno o el otro, sobre todo si no son más que, digamos, un pésimo 100,000 nodos o así. Mediante la inserción de la pila método puede tomar todo un día para hacer la conversión en lo MLM'ers consideraría un pequeño millones de nodo de jerarquía.

Pensé en darle Celko un poco de competencia por venir para arriba con un método para convertir una Lista de Adyacencia Anidadas conjuntos a velocidades que parecen imposibles. He aquí el desempeño de la inserción de la pila de método en mi i5 portátil.

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

Y aquí está la duración del nuevo método (con el empuje de la pila de método en paréntesis).

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

Sí, eso es correcto. 1 millones de nodos convertido en menos de un minuto y 100.000 nodos en menos de 4 segundos.

Usted puede leer sobre el nuevo método y obtener una copia del código en la siguiente URL. http://www.sqlservercentral.com/articles/Hierarchy/94040/

También he desarrollado un "pre-agregados" jerarquía utilizando métodos similares. MLM'ers y las personas que hacen las facturas de los materiales estará especialmente interesado en este artículo. http://www.sqlservercentral.com/articles/T-SQL/94570/

Si se detienen por echar un vistazo al artículo, saltar en el "de Unirse a la discusión" enlace y hazme saber lo que piensas.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X