Quelle est la complexité temporelle de rechercher une entrée par son index dans une base de données?

La complexité temporelle de la recherche d'une entrée par son index dans une base de données est généralement O(log n), si un arbre d'index équilibré, comme un arbre B, est utilisé, ce qui est courant dans les systèmes de gestion de bases de données relationnelles.

Les index permettent de trouver rapidement des enregistrements sans parcourir toute la table (ce qui serait O(n)). Avec un index, la recherche se réduit à parcourir l'arbre, ce qui donne une complexité logarithmique.

Dans certains cas, par exemple avec des index de hachage, la recherche peut être proche de O(1), mais cela dépend de l'implémentation et du type d'index.

Ainsi, grâce aux index, la recherche par clé dans une base de données est généralement efficace et se scale bien.