mysql - ventajas - elementos del modelo jerarquico de base de datos

Implementar una estructura de datos jerárquica en una base de datos

Question

Sé que hay dos enfoques: lista de adyacencia y árbol anidado. Se dice que la lista de adyacencia puede volverse lenta en el cruce debido a numerosas consultas. Pero no conozco ninguna cifra realista para esto. El sitio que estoy creando tendrá una extensión de 200 páginas. ¿Es posible generar (por ejemplo) un mapa del sitio que tarde más de aproximadamente 0.3 segundos?

Ejecutando en MySQL (innoDB) con la pila LAMP.

Prefiero implementar la adyacencia si es posible debido a un diseño más simple.

Gracias.

Answer 1

Aquí hay un par de preguntas que podrían ayudarlo:

SQL cómo almacenar y navegar las jerarquías

¿Cuál es el mejor esquema de base de datos para mi navegación?

Answer 2

El artículo Managing Hierarchical Data in MySQL contiene detalles sobre esto.

Recomendaría la técnica de "conjunto anidado", ya que le permite obtener todo el árbol (y sus hijos) en una consulta. Básicamente, las lecturas son baratas, pero las escrituras son costosas porque todo el árbol debe ser reequilibrado. Pero en los casos en que tienes un 99% de lecturas, entonces es totalmente justificable.

Answer 3

El enfoque ingenuo para analizar una lista de adyacencia requiere una gran cantidad de consultas, y para listas grandes puede tomar una cantidad significativa de tiempo para construir en la memoria. Como referencia, el enfoque ingenuo al que me refiero podría resumirse de la siguiente manera: Seleccione todos los elementos sin padre, luego, para cada elemento recursivamente, obtenga sus hijos. Este enfoque requiere n + 1 consultas de base de datos.

He utilizado el siguiente enfoque para construir una lista de adyacencia con 1 consulta. Seleccione todos los elementos de la base de datos. Transfiera todos los elementos a una matriz indexada por su clave. Recorre la matriz y asigna una referencia desde el objeto principal a cada uno de sus elementos secundarios. Atraviese la matriz por segunda vez y elimine todos los objetos secundarios, dejando solo los objetos de nivel raíz.

Como mencionó la pila LAMP, el código PHP para hacer esto es más o menos así:

<?php
// Assumes $src is the array if items from the database.
$tmp = array();

// Traverse the array and index it by id, ensuing each item has an empty array of children.
foreach ($src as $item) {
  $item[''children''] = array();
  $tmp[$item[''id'']] = $item;
}

// Now traverse the array a second time and link children to their parents.
foreach ($tmp as $id => $item) {
  if ($item[''parent_id''] != 0 || $item[''parent_id''] !== NULL) {
    $tmp[$item[''parent_id'']][''children''][$id] = &$tmp[$id];
  }
}

// Finally create an array with just root level items.
$tree = array();
foreach ($tmp as $id => $item) {
  if ($item[''parent_id''] == 0 || $item[''parent_id''] === NULL) {
    $tree[$id] = $item;
  }
}

// $tree now contains our adjacency list in tree form.
?>

Tenga en cuenta que este código está destinado a ilustrar una técnica para crear una lista de adyacencia a partir de una única consulta de base de datos. Probablemente podría optimizarse para un menor consumo de memoria, etc. Tampoco se ha probado.

Jim,

Answer 4

El otro enfoque se llama "conjunto anidado", creo, no "árbol anidado".

De todos modos, una cosa buena acerca de un mapa del sitio es que usted puede conocer su profundidad máxima. Creo que el problema con el modelo de adyacencia es que el SQL correspondiente funciona en un nivel a la vez, por lo que si tiene ''n'' niveles, entonces necesita un bucle de ''n'' declaraciones de SQL ... pero creo (I '' m no estoy seguro) de que si conoce la ''n'' máxima por adelantado, entonces puede codificar el correspondiente SQL de número fijo de niveles múltiples.

0,3 segundos me parece mucho tiempo para calcular 200 páginas, por lo que probablemente esté bien.

Además, un mapa del sitio no se actualiza con mucha frecuencia; por lo tanto, incluso si lleva mucho tiempo recuperar de SQL, probablemente pueda almacenar en caché el árbol recuperado / calculado en la RAM.

Alternativamente, en lugar de preocuparse por el SQL para construir un árbol, puede simplemente almacenarlo de la manera más simple posible (como lista de adyacencia), recuperarlo de la base de datos como un conjunto simple de filas y construir el árbol en RAM (usando loops en su lenguaje de programación de alto nivel) en lugar de usar bucles en SQL para construir el árbol usando sentencias de SQL.

Answer 5

Hay más opciones que solo las dos que mencionas. Existen:

• Lista de adyacencia (el "parent_id" que casi todos usan)
• Conjuntos anidados
• Enumeración de ruta
• Tabla de cierre (también conocida como Relación de adyacencia)

Ver mi respuesta a " ¿Cuál es la forma más eficiente / elegante de analizar una tabla plana en un árbol? "

O un par de libros:

• " Árboles y jerarquías en SQL para Smarties " por Joe Celko.
• " SQL Design Patterns " por Vadim Tropashko.

Answer 6

Para completar: Oracle tiene los operadores START_WITH y CONNECT_BY : vea este documento de Consultas jerárquicas .