Sto leggendo su B Trees e sembra che realizzino le operazioni con i set dinamici in O (lg n) time. Anche l'albero nero rosso (TreeMap in java) raggiunge la stessa operazione in modo asintotico nello stesso intervallo di tempo. Quindi vorrei sapere cosa rende gli alberi B più utili per database e file systemPerché abbiamo bisogno di un datastructure separato come B-Tree per database e file system?
Il motivo principale dell'esistenza di B-Trees è utilizzare al meglio il comportamento dei dispositivi che leggono e scrivono grandi blocchi di dati. Due proprietà sono importanti per rendere il B-Tree meglio di alberi binari, quando i dati devono essere memorizzati su disco:
Quindi, possiamo utilizzare i pro del secondo fatto, riducendo al contempo anche il numero di accessi al disco.
Quindi, invece di archiviare un solo numero in ogni nodo che ci dice se dovremmo continuare a sinistra o a destra, possiamo creare un indice più grande che ci dice se dovremmo continuare con il primo 1/100 , al secondo o al 99 ° (immagina i libri in una libreria ordinati per la prima lettera, poi per il secondo e così via). Finché tutti questi dati si adattano a un singolo settore, verranno caricati comunque, quindi potremmo anche utilizzarlo completamente.
Questo risulta approssimativamente nel registro b N ricerche, dove N è il numero di record. Questo numero, pur essendo asintoticamente uguale al log N, è in realtà un paio di volte più piccolo con N e b sufficientemente grandi - e poiché si tratta di memorizzare dati su disco per l'utilizzo in database, ecc., La quantità di dati di solito è abbastanza grande da giustificare questo.
Il resto della decisione di progettazione viene fatto principalmente per rendere efficiente questo lavoro, poiché la modifica di un albero N-ary è più complicata di una binario.
Grazie! Ho almeno letto circa 50 articoli sull'utilizzo dell'albero B, ma nessuno ha menzionato il secondo cono di accesso al disco che l'albero B si trasforma in un professionista. – ernesto
Gli alberi di RB sono alberi di ricerca binari. Gli alberi B possono avere più di due nodi figlio. In effetti, il numero di nodi figli è variabile.
Quindi, è possibile variare il numero di nodi figlio in modo che la dimensione di un nodo sia sempre un multiplo della dimensione del blocco del filesystem. Ciò riduce gli sprechi durante la lettura: non puoi leggere meno di un blocco, devi sempre leggere il blocco completo, quindi potresti anche riempirlo di dati utili. Aumentando il numero di nodi figli sarà anche diminuire la profondità dell'albero, riducendo così il numero medio di "hop" (cioè letture del disco), che aumenta nuovamente le prestazioni.
Ricorda: alberi B sono di solito utilizzati per strutture di dati dei negozi che sono ordini di grandezza più grande della memoria, mentre gli alberi RB sono tipicamente utilizzati per strutture di dati dei negozi che sono ordini di grandezza più piccola della memoria. In effetti, gli alberi B sono specificamente progettati come una struttura di dati su disco rispetto a una struttura di dati in memoria.
Questa è la frase chiave dal Wikipedia article (sottolineatura mia):
il B-albero è ottimizzato per i sistemi che leggono e scrivono grandi blocchi di dati
Noi hanno bisogno di algoritmi diversi perché la velocità di accesso in memoria è molto più veloce che su disco. Un albero rosso/nero rende molti accessi alla memoria, quindi funziona bene con la velocità di accesso veloce della memoria. Un b-tree rende gli accessi meno numerosi perché il disco che accede è lento.
Wikipedia ha una descrizione abbastanza buona dei problemi risolti da un albero B: http://en.wikipedia.org/wiki/B-tree#The_database_problem. –
@IvanVergiliev Ti dispiacerebbe riassumere la sezione pertinente dalla wiki sotto forma di risposta in modo che io possa accettarla. – Geek