Perché gli alberi B + hanno un'occupazione minima del 50%?

5

Per quanto posso dire, le operazioni di base (aggiunta, eliminazione, ricerca) su un albero B + funzionerebbero allo stesso modo se l'occupazione minima era 1, o 1/3 o qualsiasi altra funzione sulla dimensione del nodo.

Tutte le fonti disponibili danno l'occupazione minima del 50%. Perché il 50%?

    
posta romnempire 25.11.2014 - 04:50
fonte

2 risposte

5

Le occupazioni minime superiori al 50% non funzionano, perché quando è necessario dividere un nodo perché il nodo è troppo pieno, sarebbe impossibile tagliare un nodo in modo tale che i due nodi risultanti fossero pieni del 50% pieni . (Si potrebbe fare 60/40 o qualcosa del genere ma il nodo più piccolo fallirebbe sempre nell'invarianza della struttura dati di ogni nodo maggiore del 60%, per esempio)

Occupazione minima di meno del 50% di spazio di scarto perché l'obiettivo è quello di leggere il minor numero di nodi dalla memoria secondaria / memoria e aumentare la quantità di spazio vuoto in ogni nodo significa che la richiesta media deve essere letta un numero maggiore di nodi dal disco. (Sarebbe anche difficile da implementare in modo efficace dato che l'operazione di divisione deve essere suddivisa in blocchi 1 / (rapporto) invece di 2 blocchi)

    
risposta data 25.11.2014 - 17:49
fonte
3

Un minimo di occupazione di 1 non è possibile con un albero B + poiché ogni nodo deve avere una voce dal nodo genitore.

Occupazioni inferiori al 50% significa che l'albero può essere reso più efficiente ridistribuendo le voci tra i nodi e se due nodi hanno meno del 50% di occupazione, vengono uniti in un nodo. O come sottolinea Billy ONeal, l'albero cresce dividendo i nodi, per avere meno del 50% di occupazione, dovrai dividere un nodo in 3 o più.

    
risposta data 25.11.2014 - 11:16
fonte

Leggi altre domande sui tag