Gestión de jerarquías en SQL: MPTT / sets nesteds vs lists de adyacencia vs routes de almacenamiento

Por un time ahora he estado luchando con la mejor forma de manejar las jerarquías en SQL. Frustrado por las limitaciones de las lists de adyacencia y la complejidad de los sets MPTT / nesteds, comencé a pensar simplemente en almacenar las routes key en su lugar, como una simple node_key/node_key/... Decidí recostackr los pros y los contras de las tres técnicas:

Número de llamadas requeridas para crear / eliminar / mover un nodo:

  • Adyacencia = 1
  • MPTT = 3
  • Path = 1 (Reemplazar la ruta del nodo anterior con la nueva ruta del nodo en todos los nodos que contienen esa ruta)

Número de llamadas requeridas para get un tree:

  • Adyacencia = [número de subniveles]
  • MPTT = 1
  • Ruta = 1

Número de llamadas necesarias para get la ruta a un nodo / ascendencia:

  • Adyacencia = [número de super-niveles]
  • MPTT = 1
  • Ruta = 0

Número de llamadas requeridas para get el número de subnodos:

  • Adyacencia = [número de subniveles]
  • MPTT = 0 (puede calcularse a partir de valores derecha / izquierda)
  • Ruta = 1

Número de llamadas requeridas para get la profundidad del nodo:

  • Adyacencia = [número de super-niveles]
  • MPTT = 1
  • Ruta = 0

Campos DB requeridos:

  • Adyacencia = 1 (padre)
  • MPTT = 3 (padre, derecha, izquierda)
  • Ruta = 1 (ruta)

Conclusión

La técnica de ruta almacenada utiliza las mismas o less llamadas que las otras técnicas en cada caso de uso excepto uno. Según este análisis, el almacenamiento de paths es un claro ganador. Sin mencionar, es mucho más simple de implementar, legible para los humanos, etc.

Entonces, la pregunta es, ¿no deberían las routes almacenadas considerarse una técnica más sólida que MPTT? ¿Por qué las routes almacenadas no son una técnica más comúnmente utilizada, y por qué no las usarías sobre MPTT en una instancia determinada?

Además, si cree que este análisis está incompleto, por favor hágamelo saber.

ACTUALIZAR:

Aquí hay al less 2 cosas que MPTT puede hacer de la caja que una solución de ruta almacenada no:

  1. Permite el cálculo del recuento de subnodos para cada nodo sin consultas adicionales (mencionado anteriormente).
  2. Impone un pedido en nodos en un nivel determinado. Las otras soluciones están desorderadas.

También podría considerar el layout de la tabla de clausura que describo en mi respuesta a ¿Cuál es la forma más eficiente / elegante de analizar una tabla plana en un tree?

Llamadas requeridas para crear / eliminar / mover un nodo:

  • Cierre = 1

Llamadas requeridas para get un tree:

  • Cierre = 1

Llamadas requeridas para get ruta a un nodo / ascendencia:

  • Cierre = 1

Llamadas requeridas para get el número de subnodos:

  • Cierre = 1

Llamadas requeridas para get la profundidad del nodo:

  • Cierre = 1

Campos DB requeridos:

  • Adjancency = 1 campo / fila más
  • Ruta = 1 campo / fila más
  • MPTT = 2 o 3 campos / fila más
  • Cierre = 2 o 3 campos en la tabla adicional. Esta tabla tiene O (n ^ 2) filas peor caso, pero mucho less que eso en la mayoría de los casos prácticos.

Hay un par de otras consideraciones:

Admite profundidad ilimitada:

  • Adyacencia = sí
  • MPTT = sí
  • Ruta = no
  • Cierre = sí

Apoya la integridad referencel:

  • Adyacencia = sí
  • MPTT = no
  • Ruta = no
  • Cierre = sí

También cubro Closure Table en mi presentación Modelos para datos jerárquicos con SQL y PHP , y mi libro, SQL Antipatterns: Cómo evitar las trampas de la progtwigción de bases de datos .

El problema con su conclusión es que ignora la mayoría de los problemas relacionados con el trabajo con treees.

Al networkingucir la validez de una técnica al "número de llamadas", se ignoran todos los problemas que las estructuras de datos y algorithms bien entendidos intentan resolver; es decir, la ejecución más rápida y poca memory y la huella de resources.

El "número de llamadas" a un server SQL puede parecer una buena métrica ("mirar código ma less"), pero si el resultado es un progtwig que nunca termina, se ejecuta lentamente o ocupa mucho espacio, es de hecho, una métrica inútil.

Al almacenar la ruta con cada nodo, no está creando una estructura de datos de tree. En cambio, estás creando una list. Cualquier operación que un tree está diseñado para optimizar se pierde.

Esto puede ser difícil de ver con pequeños sets de dates (y en muchos casos de treees pequeños una list es mejor), pruebe algunos ejemplos en sets de datos de tamaño 500, 1000, 10k – Verá rápidamente por qué no se almacena el path completo una buena idea.

    Intereting Posts