Mekkora az adatkeresési sebesség átlagértéke a B-Tree típusú indexekben az adatbázis-kezelő rendszerekben?

A B-típusú indexben található adatok keresésének átlagos sebességét általában O(log n)-ként becsülik, ahol n az indexben lévő elemek száma. Ez azért van, mert a B-fa egy kiegyensúlyozott fa, ahol a fa magassága logaritmikusan nő a rekordok számával.

Például, ha egy táblában egymillió rekord van, a B-fa szerinti keresés körülbelül a fa rendjének (általában 100 vagy több) alapú logaritmusa lesz, ami nagyon gyors hozzáférést tesz lehetővé a lineáris kereséshez képest.

# Pseudokód a B-fa keresési műveletek számának becsléséhez
import math

n = 1_000_000  # elemek száma
order = 100    # B-fa rendje (maximális gyermekek száma egy csomópontban)
height = math.ceil(math.log(n, order))
print(f"Átlagos szintek száma kereséshez: {height}")