Qual è il valore medio della velocità di ricerca dei dati in un indice di tipo B-Tree nei sistemi di gestione di database?

La velocità media di ricerca dei dati in un indice di tipo B-Tree in un sistema di gestione di database è generalmente stimata come O(log n), dove n è il numero di elementi nell'indice. Questo perché un B-Tree è un albero bilanciato, in cui l'altezza dell'albero cresce logaritmicamente rispetto al numero di record.

Ad esempio, se una tabella contiene un milione di record, la ricerca in un B-Tree richiederà circa il logaritmo in base dell'ordine dell'albero (solitamente circa 100 o più) del milione, offrendo un accesso molto rapido rispetto alla ricerca lineare.

# Pseudocodice per stimare il numero di operazioni di ricerca in un B-Tree
import math

n = 1_000_000  # numero di elementi
order = 100    # ordine del B-Tree (numero massimo di figli per nodo)
height = math.ceil(math.log(n, order))
print(f"Numero medio di livelli per la ricerca: {height}")