Buenas descripciones

En términos generales, está tomando una decisión entre tiempos de lectura rápidos (por ejemplo, conjunto anidado) o tiempos de escritura rápidos (lista de adyacencia). Por lo general, terminas con una combinación de las siguientes opciones que mejor se adaptan a tus necesidades. Lo siguiente proporciona una lectura en profundidad:

Una comparación más de Intervalos anidados vs. Lista de adyacencia: la mejor comparación de Lista de adyacencia, Ruta materializada, Conjunto anidado e Intervalo anidado que he encontrado.Modelos para datos jerárquicos: diapositivas con buenas explicaciones de compensaciones y ejemplos de usoRepresentando jerarquías en MySQL: muy buena visión general del conjunto anidado en particularDatos jerárquicos en RDBMS: el conjunto de enlaces más completo y bien organizado que he visto, pero no hay muchas explicaciones

Opciones

Los que conozco y las características generales:

Lista de adyacencia:Columnas: ID, ParentIDFácil de implementar.El nodo barato se mueve, inserta y elimina.Caro para encontrar el nivel, ascendencia y descendientes, caminoEvite N + 1 a través deExpresiones de tabla comunes en bases de datos que los soportanConjunto anidado (tambien conocido comoRecorrido de árbol de pedido anticipado modificado)Columnas: izquierda, derechaAscendencia barata, descendientesMuy caroO(n/2) mueve, inserta, elimina debido a la codificación volátilMesa de puente (tambien conocido como.Tabla de cierre / desencadenantes w)Utiliza una tabla de unión separada con: ancestro, descendiente, profundidad (opcional)Ascendencia barata y descendientesEscribe costosO(log n) (tamaño del subárbol) para insertar, actualizar, eliminarCodificación normalizada: buena para estadísticas RDBMS y planificador de consultas en combinacionesRequiere varias filas por nodoColumna de linaje (tambien conocido como.Camino materializado, Enumeración de ruta)Columna: linaje (por ejemplo, / padre / hijo / nieto / etc.)Descendientes baratos mediante consulta de prefijo (p. Ej.LEFT(lineage, #) = '/enumerated/path')Escribe costosO(log n) (tamaño del subárbol) para insertar, actualizar, eliminarNo relacional: se basa en el tipo de datos de matriz o el formato de cadena serializadaIntervalos anidadosAl igual que el conjunto anidado, pero con real / float / decimal para que la codificación no sea volátil (movimiento / inserción / eliminación de bajo costo)Tiene problemas de representación real / flotante / decimal / precisiónVariante de codificación matricial agrega codificación ancestral (ruta materializada) para "libre", pero con trucos adicionales de álgebra lineal.Mesa planaUna Lista de adyacencia modificada que agrega una columna de Nivel y Rango (por ejemplo, ordenar) a cada registro.Barato para iterar / paginarMovimiento costoso y eliminarBuen uso: discusión con hilos - foros / comentarios de blogMúltiples columnas de linajeColumnas: una para cada nivel de linaje, se refiere a todos los padres hasta la raíz, los niveles inferiores al nivel del elemento se establecen en NULLAntepasados baratos, descendientes, nivelInserto barato, eliminar, mover las hojasCostoso insertar, eliminar, mover los nodos internosLímite estricto de cuán profunda puede ser la jerarquía

Notas específicas de la base de datos

MySQL

Usar variables de sesión para la Lista de adyacencia

Oráculo

UtilizarCONECTAR POR atravesar listas de adyacencia

PostgreSQL

tipo de datos ltree para camino materializado

servidor SQL

Resumen generalOfertas 2008JerarquíaId El tipo de datos parece ayudar con el enfoque de la columna de linaje y ampliar la profundidad que se puede representar.