Perché la ricerca in un albero B è più veloce della ricerca lineare?

La ricerca nell’albero B è più veloce grazie alla sua struttura, che minimizza il numero di confronti e operazioni su disco.

• Complessità logaritmica: Gli alberi B hanno una complessità temporale di ricerca logaritmica, O(log N), dove N è il numero di elementi. Ciò si ottiene rappresentando i dati come un albero bilanciato con più chiavi in ogni nodo.
• Ramificazione: Ogni nodo può contenere più chiavi e puntatori ai figli. Durante la ricerca, confrontiamo la chiave cercata con le chiavi nel nodo corrente, determinando il nodo figlio corretto per continuare. Questo riduce drasticamente il numero di nodi da visitare.
• Ottimizzazione per l’accesso su disco: La dimensione dei nodi nell’albero B è generalmente scelta per corrispondere alla dimensione di un blocco disco. Questo permette di caricare in memoria un nodo completo in una sola volta, leggendo grandi volumi di dati e minimizzando le operazioni lente di input/output su disco. La ricerca lineare, invece, richiede di leggere sequenzialmente ogni elemento.

Al contrario, la ricerca lineare ha una complessità lineare di O(N), richiedendo nel peggiore dei casi N confronti.