Wat is de gemiddelde waarde van de datasoeknelheid in een B-Tree index in databasebeheersystemen?

De gemiddelde zoektijd voor gegevens in een B-Tree-index in een databasebeheersysteem wordt meestal geschat op O(log n), waarbij n het aantal elementen in de index is. Dit komt doordat een B-Tree een gebalanceerde boom is, waarbij de hoogte van de boom logaritmisch toeneemt met het aantal records.

Bijvoorbeeld, als een tabel een miljoen records bevat, zal de zoekactie in een B-Tree ongeveer de logaritme in de basis van de orde van de boom (meestal rond de 100 of meer) van de miljoen bedragen, wat een zeer snelle toegang biedt in vergelijking met lineair zoeken.

# Pseudocode om het aantal zoekbewerkingen in een B-Tree te schatten
import math

n = 1_000_000  # aantal elementen
order = 100    # orde van de B-Tree (maximaal aantal kinderen per knoop)
height = math.ceil(math.log(n, order))
print(f"Gemiddeld aantal niveaus voor zoeken: {height}")