Kokia yra vidutinė duomenų paieškos greičio reikšmė B-Tree tipo indekse duomenų valdymo sistemose?

Vidutinis duomenų paieškos greitis B-Tree tipo indekse duomenų bazės valdymo sistemoje paprastai įvertinamas kaip O(log n), kur n yra elemento skaičius indekse. Tai yra todėl, kad B-Tree yra subalansuotas medis, kurio aukštis auga logaritmiškai pagal įrašų skaičių.

Pavyzdžiui, jei lentelėje yra milijonas įrašų, paieška B-Tree užtruks maždaug logaritmą pagal medžio tvarką (dažniausiai apie 100 ar daugiau) iš milijono, užtikrinant labai greitą prieigą, palyginti su linijine paieška.

# Pseudokodas, įvertinantis paieškos operacijų skaičių B-Tree
import math

n = 1_000_000  # elementų skaičius
order = 100    # B-Tree tvarka (maksimalus vaikų skaičius mazge)
height = math.ceil(math.log(n, order))
print(f"Vidutinis lygių skaičius paieškai: {height}")