Utilisation d'Arbres binaires de recherches ?

Bonjour Griffin,
L'indexation des SGBD ne fonctionne pas exactement comme ça. On peut la considérer comme une implémentation d'arborescence mais ce n'est pas un arbre binaire.

Imagine une table contenant 1000 entrées. Pour que l'indexation soit possible, il faut qu'il existe une fonction de tri sur la colonne que tu souhaites indexer (tri naturel pour les int par exemple, tri alphabétique pour les varchar...).
L'indexation se fait de la manière suivante :
- le sgbd crée une première page contenant 10 valeurs (par exemple). Ici on va considérer qu'on utilise un index sur des int non signés : 0, 100, 200, .., 900
- le sgbd, pour chaque intervalle situé entre deux valeurs va créer une autre page (de façon récursive), par exemple la page 0 va pointer vers une page contenant 10, 20,... 90 ; et la page 30 va elle-même pointer vers une page contenant 31, 32, ... 39

Note bien qu'il n'est pas obligatoire de posséder absolument toutes les valeurs, comme dans mon exemple. Ce qu'il faut comprendre, c'est que le sgbd va simplement trier ta colonne, et stocker une liste de couples (valeur/adresse) dans plein de pages (dont la longueur est fonction de la taille de la pagination).

Ensuite, en ce qui concerne la recherche, ça se fait en complexité O(n log (n)), par dichotomie.
Exemple: tu recherches la valeur 43. Le sgbd va regarder dans la première page et va sélectionner la valeur médiane (ici 500). 43 est inférieur, donc on recherche dans la sous-partie (0, 500). Finalement, on se rend compte, à force de récurrence, que 43 se trouve dans la page pointée par 0 (car appartenant à (0,100)), donc on se déplace dans cette page et on continue le processus.

J'espère avoir été assez clair.

Cordialement,