Quali sono i vantaggi degli alberi a T sugli alberi B +/-?

Question

Ho esplorato le definizioni degli alberi T-trees e B-/B +. Dai documenti sul Web comprendo che gli alberi B hanno un rendimento migliore nella memoria gerarchica, come le unità disco e la memoria cache.

Quello che non riesco a capire è il motivo per cui gli alberi a T sono stati utilizzati anche per la memoria piatta?

Sono pubblicizzati come alternativa efficiente in termini di spazio agli alberi AVL.

Nel caso peggiore, tutti i nodi foglia di un albero a T contengono solo un elemento e tutti i nodi interni contengono l'importo minimo consentito, che è quasi pieno. Ciò significa che in media viene utilizzata solo metà dello spazio allocato. A meno che non mi sbagli, questo è lo stesso utilizzo del caso peggiore degli alberi B, quando i nodi di un albero B sono mezzo pieno.

Supponendo che entrambi gli alberi archivino le chiavi localmente nei nodi, ma usano i puntatori per fare riferimento ai record, l'unica differenza è che gli alberi B devono memorizzare i puntatori per ciascuno dei rami. Ciò generalmente causerebbe fino al 50% di overhead o meno (su alberi a T), a seconda della dimensione dei tasti. In realtà, questo è vicino al sovraccarico previsto negli alberi AVL, supponendo che nessun puntatore padre, record incorporati nei nodi, chiavi incorporate nei record. È questo il guadagno di efficienza atteso che ci impedisce di usare gli alberi B invece?

Gli alberi di tipo T vengono solitamente implementati sopra gli alberi AVL. Gli alberi AVL sono più equilibrati rispetto agli alberi B. Questo può essere collegato all'applicazione di alberi a T?

Answer 1

Posso darti una storia personale che copre metà della risposta, cioè, perché ho scritto un codice Pascal per programmare B+ trees circa 18 anni fa.

il mio sistema di destinazione era un PC con due dischi, ho dovuto memorizzare un indice su memoria non volatile e volevo capire meglio cosa stavo imparando all'università. Ero molto insoddisfatto delle prestazioni di un pacchetto commerciale, probabilmente DBase III, o di qualche prodotto Fox, non ricordo.

comunque: Io necessarie queste operazioni:

• ricerca
• inserimento
• eliminazione
• reca

• elemento precedente

• dimensione massima di indice non era noto

• così dati dovevano risiedere su disco
• ogni accesso al supporto aveva elevato costo
• legge un intero blocco costo come leggere un byte

B + -alberi fatto che piccolo PC lento veramente vola attraverso i dati!

le ante avevano due puntatori supplementari in modo da formare una lista doppiamente collegata, per le ricerche sequenziali.

Answer 2

In realtà la differenza sta nel sistema che si utilizza. Come il mio tutor all'università ha commentato: se il tuo problema sta nella mancanza di memoria, o nella mancanza di hdd determinerà quale albero e in quale implementazione userai. Molto probabilmente sarà B + tree.

Perché esistono centinaia di implementazioni, ad esempio con la coda di 2direction e le code unidirezionali in cui è necessario eseguire il ciclo degli elementi di pensiero, e inoltre ci sono più modi per memorizzare l'indice e recuperarlo determinerà i veri svantaggi di qualsiasi implementazione.