Quelle est la valeur moyenne de la vitesse de recherche de données dans un index de type B-Tree dans les systèmes de gestion de bases de données?

La vitesse moyenne de recherche de données dans un index de type B-Tree dans un SGBD est généralement estimée comme O(log n), où n est le nombre d'éléments dans l'index. Cela est dû au fait qu'un B-Tree est un arbre équilibré, où la hauteur de l'arbre croît logarithmiquement en fonction du nombre d'enregistrements.

Par exemple, si une table contient un million d'enregistrements, la recherche dans un B-Tree prendra environ le logarithme en base de l'ordre de l'arbre (généralement autour de 100 ou plus) du million, ce qui permet un accès très rapide par rapport à une recherche linéaire.

# Pseudocode pour estimer le nombre d'opérations de recherche dans un B-Tree
import math

n = 1_000_000  # nombre d'éléments
order = 100    # ordre du B-Tree (nombre maximal d'enfants par nœud)
height = math.ceil(math.log(n, order))
print(f"Nombre moyen de niveaux pour la recherche : {height}")