Implementazione di una struttura gerarchica di dati in un database

Question

So che ci sono due approcci: elenco di adiacenza e albero nidificato. Si dice che la lista di adiacenza può essere lenta da utilizzare in attraversamento a causa di numerose query. Ma non conosco cifre realistiche per questo. Il sito che sto realizzando avrà nella regione 200 pagine. Traversal genera (per esempio) una sitemap che impiega più tempo di circa 0,3 secondi?

In esecuzione su MySQL (innoDB) con stack LAMP.

Preferirei implementare l'adiacenza se possibile a causa del design più semplicistico.

Grazie.

Answer 1

Qui ci sono un paio di domande che potrebbero aiutarvi:

SQL how to store and navigate hierarchies

Which is the best database schema for my navigation

Answer 2

L'altro approccio è chiamato "insieme nidificate", penso, non "albero nidificato".

In ogni caso, un aspetto positivo di una mappa del sito è che potresti conoscere la sua profondità massima. Penso che il problema con il modello di adiacenza sia che l'SQL corrispondente funziona su un livello alla volta, quindi se hai livelli 'n' allora hai bisogno di un ciclo di istruzioni SQL 'n' ... ma io penso (I ' Non sono sicuro) che se si conosce il massimo 'n' in anticipo, è possibile codificare il corrispondente numero di SQL a numero fisso di multipli.

0,3 secondi mi sembra un tempo molto lungo per calcolare 200 pagine, quindi probabilmente è OK.

Anche una mappa del sito non viene aggiornata molto spesso; quindi, anche se richiede molto tempo per recuperare da SQL, è possibile memorizzare nella cache l'albero recuperato/calcolato nella RAM.

In alternativa, anziché preoccuparsi dell'SQL per costruire un albero, è possibile archiviarlo il più semplicemente possibile (come elenco di adiacenza), recuperarlo dal database come un semplice insieme di righe e creare l'albero nella RAM (usando loop nel linguaggio di programmazione di alto livello) invece di usare loop in SQL per costruire l'albero usando istruzioni SQL.

Answer 3

L'articolo Managing Hierarchical Data in MySQL descrive in dettaglio questo.

Suggerirei la tecnica "nested set", in quanto consente di ottenere l'intero albero (ei relativi figli) in un'unica query. Fondamentalmente le letture sono economiche ma le scritture sono costose perché l'intero albero deve essere riequilibrato. Ma nei casi in cui si ha il 99% delle letture, allora è totalmente giustificabile.

Answer 4

Per completezza: Oracle ha gli operatori START_WITH e CONNECT_BY: vedere questo documento Hierarchical Queries.

Answer 5

Ci sono più opzioni che solo le due che hai menzionato.Ci sono:

• lista di adiacenza (il "parent_id" uno quasi tutti usano)
• annidata Imposta
• Percorso Enumeration
• Chiusura Table (aka adiacenza Relation)

Vedere la mia risposta a "What is the most efficient/elegant way to parse a flat table into a tree?"

O un paio di libri:

• "Trees and Hierarchies in SQL for Smarties" di Joe Celko.
• "SQL Design Patterns" di Vadim Tropashko.

Answer 6

L'approccio ingenuo di analisi di un elenco di adiacenze richiede molte query e per gli elenchi di grandi dimensioni potrebbe richiedere una quantità significativa di tempo per la creazione in memoria. Per riferimento, l'approccio ingenuo a cui mi riferisco potrebbe essere riassunto come segue: Seleziona tutti gli elementi senza alcun genitore, Quindi per ogni oggetto ricorsivamente ottieni i suoi figli. Questo approccio richiede n + 1 query di database.

Ho utilizzato il seguente approccio per creare un elenco di adiacenze con 1 query. Seleziona tutti gli elementi dal database. Trasferisci tutti gli elementi in una matrice indicizzata dalla loro chiave. Attraversa l'array e assegna un riferimento dall'oggetto padre a ciascuno dei suoi figli. Attraversare la matrice una seconda volta e rimuovere tutti gli oggetti figlio lasciando solo gli oggetti di livello root.

Dal momento che lei ha citato stack LAMP, codice PHP per fare questo è più o meno la seguente:

<?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. 
?> 

Si prega di notare questo codice ha lo scopo di illustrare una tecnica per la costruzione di una lista di adiacenza da una singola query di database. Probabilmente potrebbe essere ottimizzato per un minore consumo di memoria, ecc. Inoltre non è stato testato.

Jim,