Mis on andmeotsingu kiiruse keskmine väärtus B-Tree tüüpi indeksis andmebaaside haldussüsteemides?

Keskmine andmete otsimise kiirus B-Tree tüüpi indeksis andmebaasisüsteemis on tavaliselt hinnatud kui O(log n), kus n on indeksi elementide arv. See tuleneb sellest, et B-Tree on tasakaalustatud puu, mille kõrgus kasvab logaritmiliselt vastavalt kirje arvule.

Näiteks, kui tabelis on miljon kirjet, võtab otsing B-Tree-s ligikaudu logaritmi alusel puu järgu (tavaliselt umbes 100 või rohkem) miljonist, pakkudes väga kiire juurdepääsu võrreldes lineaarse otsinguga.

# Pseudo-kood B-Tree otsingute arvutamiseks
import math

n = 1_000_000  # elementide arv
order = 100    # B-Tree järk (maksimaalne laste arv sõlmes)
height = math.ceil(math.log(n, order))
print(f"Keskmine tasemete arv otsinguks: {height}")