Recupero di una struttura dati dell'albero memorizzata in modo errato

Non è necessariamente così male come pensi e potrebbe anche essere la rappresentazione ottimale se hai un indice su parent_id .

Supponiamo che tu sia interessato ai discendenti di B sopra. In tal caso, devi prima eseguire una query per i nodi che hanno parent_id che corrisponde all'ID di B . Questo ti dà D,E. Ora cerca i nodi che hanno l'ID principale di uno di questi. Questo ti dà H,I,J . Fai ancora una volta per H,I,J , non otteniamo nulla e quindi abbiamo finito.

Supponendo che le query siano in tempo costante (indice hash, ad es.), ciò è effettivamente ottimale dal punto di vista della complessità algoritmica (il caso peggiore presenta complessità lineare). Ogni query per trovare i nodi figlio di un nodo genitore in quel caso sarebbe O (1). Anche se le query sono logaritmiche, in realtà è ottimale in termini di numero di query (logN) a meno che non si sia effettivamente memoizzato l'intero elenco di discendenti in ciascun nodo (che sarebbe esplosivo in termini di utilizzo della memoria) e sicuramente non così male come quadratico complessità come pensi.

Per un RDBMS, mi sembra davvero molto ottimale archiviare le cose in questo modo bottom-up, specialmente se l'albero è n-ario e non solo binario. Non preoccuparti, sii felice. Penso che l'unica cosa in cui memorizzare ID figlio nei nodi ti salverà è la necessità di un indice, ma equivale allo stesso numero di query e praticamente alla stessa quantità di lavoro per ottenere un elenco di tutti i discendenti.

Se hai bisogno di più velocità, e l'albero si adatta, puoi trasferire l'albero in memoria, costruendo linearmente l'albero dai nodi nella memoria del client e poi fai semplicemente la ricerca in memoria, aggiornandolo quando il database è modificato. Ma potresti anche non averne bisogno.

Con un indice su parent_id, in realtà penso che questo sia un buon modo per organizzare la relazione, e lo stiamo usando in questo modo in molti posti. Inoltre, non vedo un modo migliore ovvio, dato che la relazione è 1: N, quindi se provi a memorizzare parent- > child, hai bisogno di una tabella aggiuntiva, e ti ritrovi sempre con la stessa logica.

Il punto centrale sta avendo l'indice su parent_id; con questo, l'accesso è veloce e facile e potresti creare un vero albero nella memoria se ne hai bisogno continuamente.

Esistono diversi modi per memorizzare una gerarchia in un database relazionale. Questi includono

• Elenco di adiacenze. Questa è la tua attuale implementazione.
• Enumerazione dei percorsi.
• Set nidificato
• Tabella di chiusura

Ognuno di questi ha caratteristiche di inserimento, eliminazione, lettura adiacenti e di set-read diversi. L'elenco di adiacenze ha il sovraccarico più basso per le gerarchie che cambiano rapidamente. Tuttavia, è meno utile enumerare i sub-alberi. Gli altri pre-calcolano i discendenti di ciascun nodo in modi diversi, il che rende la ricerca rapida al costo di un'ulteriore amplificazione di scrittura.

A seconda del tuo rapporto di lettura / scrittura, uno di questi potrebbe aiutarti.

Ho trovato il libro di Joe Celko "Trees and Hierarchies in SQL for Smarties" per essere più leggibile e informativo.

C'è una discussione su Stackoverflow che discute ampiamente di questo.