Che cos'è una pagina B-tree

Question

Penso di sapere cos'è un albero B ma cos'è una pagina B-tree?

Answer 1

Gli alberi B sono una struttura dati comune per raccolte molto grandi, come quelle presenti nei database. Spesso sono troppo grandi per essere conservati in memoria in una volta, quindi sono memorizzati in un file su disco e solo le parti necessarie per l'operazione corrente vengono letti in memoria.

Un pezzo di dati che viene archiviato su disco (e letto in memoria) come unità viene chiamato una pagina. È tipico per un albero B memorizzare il numero di record in un singolo nodo che rendono la dimensione del nodo uguale alla dimensione naturale della pagina del file system. In questo modo, le accesioni del disco possono essere ottimizzate.

Ad esempio, se il file system funziona naturalmente su blocchi di dati di 16 kb e se la dimensione dei record nell'albero B è 500 b (inclusi i collegamenti al livello successivo di nodi), allora 32 record potrebbero essere memorizzati nel nodo, rendendo la dimensione del nodo uguale alla dimensione della pagina e consentendo l'ottimizzazione dell'accesso al disco.

Answer 2

B-tree è un albero con n-arity, quindi la pagina è esattamente "n" celle per accogliere elementi dal nodo corrente e loro riferimento verso il basso. Per l'albero B + può essere come meta-nodi (che conserva solo riferimenti) e nodi foglia per memorizzare i dati.