Kāda ir vidējā datu meklēšanas ātruma vērtība B-Tree tipa indeksā datu pārvaldības sistēmās?

Vidējais datu meklēšanas ātrums B-Tree tipa indeksā datu bāzes pārvaldības sistēmā parasti tiek novērtēts kā O(log n), kur n ir elementu skaits indeksā. Tas ir tāpēc, ka B-Tree ir līdzsvarots koks, kura augstums pieaug logaritmiski attiecībā uz ierakstu skaitu.

Piemēram, ja tabulā ir miljons ierakstu, meklēšana B-Tree aizņems aptuveni logaritmu pēc kārtas (parasti ap 100 vai vairāk) no miljoniem, nodrošinot ļoti ātru piekļuvi salīdzinājumā ar lineāro meklēšanu.

# Pseido-kods, lai novērtētu meklēšanas operāciju skaitu B-Tree
import math

n = 1_000_000  # elementu skaits
order = 100    # B-Tree kārtība (maksimālais bērnu skaits mezglā)
height = math.ceil(math.log(n, order))
print(f"Vidējais līmeņu skaits meklēšanai: {height}")