Qualche consiglio su come gestire gli alberi gerarchici nel modello relazionale?

Question

Ho una struttura ad albero che può essere n livelli in profondità, senza restrizioni. Ciò significa che ogni nodo può avere altri n nodi.

Qual è il modo migliore per recuperare un albero del genere senza inviare migliaia di query al database?

Ho esaminato alcuni altri modelli, come il modello di tavolo piatto, Preorder Tree Traversal Algorithm e così via.

Avete suggerimenti o suggerimenti su come implementare un modello di albero efficiente? Il mio obiettivo nella realtà è di avere una o due domande che sputerebbero l'intero albero per me.

Con un'elaborazione sufficiente posso visualizzare l'albero in dot net, ma quello sarebbe nella macchina client, quindi, non è un grosso problema.

Oh basta cadere un po 'di informazioni qui:

ambiente: Oracle o PostgreSQL, C# e WinForms.

Grazie per l'attenzione

Answer 1

Supponendo che la vostra unica preoccupazione è seleziona e non inserti/aggiornamenti/elimina, questo dipende dalle esigenze, come ad esempio:

• hai bisogno di sapere quale livello ogni nodo è a?
• Hai bisogno di sapere se ogni nodo ha figli mentre lo sta visualizzando?
• Hai bisogno di ordinare i fratelli per nome?

Tuttavia, se ci sono davvero delle modifiche minime all'albero che viene fatto, allora non importa quale schema si usa, dato che si può fare tutto il lavoro nel livello applicazione e mettere in cache l'output.

Edit:

Quando le questioni di ordine, di solito andare per il metodo materialized path, e aggiungere un SortPath colonna aggiuntiva.In questo modo puoi ottenere i risultati ordinati per fratello, che è una denormalizzazione che rende estremamente facile il rendering dell'albero in HTML, dato che puoi scrivere l'intero albero (o qualsiasi porzione) esattamente nell'ordine in cui ricevi i record usando una singola query . Questo è ottimale per la velocità ed è il modo più semplice per ordinare più di un livello alla volta.

Es,

CREATE TABLE [dbo].[MatPath](
    [ID] [int] NULL, 
    [Name] [varchar](50) NULL, 
    [Path] [varchar](max) NULL, 
    [SortPath] [varchar](max) NULL 
) 

insert into MatPath (ID, Name, Path, SortPath) values (1, 'Animal', '1', 'Animal-1') 
insert into MatPath (ID, Name, Path, SortPath) values (2, 'Dog', '1.2', 'Animal-1|Dog-2') 
insert into MatPath (ID, Name, Path, SortPath) values (3, 'Horse', '1.3', 'Animal-1|Horse-3') 
insert into MatPath (ID, Name, Path, SortPath) values (4, 'Beagle', '1.2.4', 'Animal-1|Dog-2|Beagle-4') 
insert into MatPath (ID, Name, Path, SortPath) values (5, 'Abyssinian', '1.3.5', 'Animal-1|Horse-3|Abyssinian-5') 
insert into MatPath (ID, Name, Path, SortPath) values (6, 'Collie', '1.2.6', 'Animal-1|Dog-2|Collie-6') 

select * 
from MatPath 
order by SortPath 

uscita:

ID  Name   Path  SortPath 
------ --------------- ----------- -------------------------------- 
1  Animal   1   Animal-1 
2  Dog    1.2   Animal-1|Dog-2 
4  Beagle   1.2.4  Animal-1|Dog-2|Beagle-4 
6  Collie   1.2.6  Animal-1|Dog-2|Collie-6 
3  Horse   1.3   Animal-1|Horse-3 
5  Abyssinian  1.3.5  Animal-1|Horse-3|Abyssinian-5 

(6 row(s) affected) 

È possibile determinare il livello di ciascun nodo contando tubi (o periodi) nello strato di applicazione, o in SQL usando qualsiasi funzione built-in o personalizzata che può count occurrences of a string.

Inoltre, noterete che aggiungo lo ID allo Name durante la creazione di SortPath. Questo per garantire che due nodi fratelli con lo stesso nome vengano sempre restituiti nello stesso ordine.

Answer 2

non esiste un modello albero efficiente.

SQL 2008 - hierarchyid. Esiste un nuovo tipo di dati per la gestione dei hiearchie, ma diventa grande nel tempo.

Oppure: solito. Campo padre nella tabella, che punta all'ID della tabella padre.

Per domande ...

• Si può fare un po 'di più ottimale con una migliore SQL (una dichiarazione per ogni livello, più l'uso di una tabella temporanea). Questa è la parte davvero difficile qui.
• Quello che abbiamo fatto in un CMS in cui avevamo lo stesso era che ogni nodo conosceva il suo genitore, il nodo superiore (per più grafici) e il successivo nodo contenitore più alto. Alcuni nodi sono stati contrassegnati come contenitori: contenevano elementi secondari, ma questi appartenevano logicamente a un altro contenitore (come: sito Web, con cartelle, quindi documenti con risorse come immagini).

Answer 3

Nested Sets - lento per l'aggiornamento ma veloce per l'esecuzione di query.

Answer 4

Abbiamo utilizzato un modello con grande successo in cui per ogni nodo è stata memorizzata una stringa contenente ciascun id di nodo dall'alto verso il nodo, separati da ".". Recuperare un albero diventa super efficiente, ordinare solo sulla stringa.

Questo modello ha una limitazione, ovviamente, per quanto profonda possa essere la gerarchia. Ma questo è principalmente limitato dalla dimensione massima della colonna stringa ID. In SQL Server utilizzando varchar (max) il limite è 2^31-1 byte, il che rende le gerarchie piuttosto profonde.

Answer 5

È possibile numerare i nodi da 1..M come si costruisce l'albero e memorizzare i riferimenti dei bambini in termini di questi indici, Ora basta scrivere l'albero. È possibile recuperare tutti i nodi in un'unica lettura. Lo schema di numerazione contiene le informazioni dell'albero,

Answer 6

Per me questo dipende dalla dimensione dell'albero e dal tipo di query che si desidera eseguire.

Da quello che posso dire hai due dati. MyId e MyParent. Se hai creato un tavolo semplicemente con queste due cose, puoi chiedere e rispondere a chi sono i miei figli e chi sono i miei genitori.

Se si desidera creare un albero completo per l'analisi intensiva, richiederei tutti i dati e li costruisco personalmente. Il database agisce solo come archiviazione delle informazioni a questo punto.

Se il mio albero era grande o richiedeva più di mezzo secondo per la creazione, lo manterrei sul mio server e lo renderò accessibile con le chiamate ajax al client. Funziona meglio se l'albero è statico per tutti i client.

Se l'albero è dinamico, vorrei insistere che il client attende mentre i dati vengono recuperati dal server e l'albero viene creato localmente. Ciò aumenterà la velocità di utilizzo.

Se hai fornito ulteriori informazioni su cosa stai dicendo quando hai detto "dividi l'albero", potrei essere in grado di offrire un'opinione migliore. Ma in generale non ho trovato un albero ideale in un database. Tuttavia, OLAP potrebbe avere uno strumento di cui non sono a conoscenza.

Answer 7

Joe Celko ha una soluzione per questo nel suo libro SQL for Smarties (capitolo 29). Inserti, aggiornamenti ed eliminazioni sono un po 'complicati, ma i selezioni sono molto veloci. Lo uso da alcuni anni e funziona molto bene.

Answer 8

Ho notato che hai elencato i tuoi DB come Oracle o PostgreSQL. Se è possibile attenersi a Oracle, è possibile utilizzare i comandi start with e connect by per fare facilmente ciò di cui si ha bisogno. Ci sono molte opzioni che gestiranno anche se ci sono loop, o se è necessario filtrare un ramo in base ad alcuni criteri. L'ho utilizzato personalmente in un sistema di produzione con letture e scritture pesanti senza problemi di prestazioni.

Una ricerca rapida mostra che è possibile eseguire un'operazione simile (anche se più complessa in termini di sql saggio) con postgreSQL utilizzando il comando with recursive. Non ho usato personalmente questo metodo, quindi non posso darti altre informazioni.