En programmation, on peut optimiser la performance des recherches en créant un arbre binaire. Cette technique consiste à maintenir un index des valeurs et peut être représentée sous la forme de branches d'arbre, partant de la racine, où chaque noeud est associé à une valeur unique qui se subdivise en deux éléments enfants. Ainsi, on pourra effectuer très rapidement une recherche dite "dichotomique" (couper en deux) dans un ensemble de valeurs très large.
Comme c'est un cas d'école, je laisserai les livres expliquer en détails tout le concept et je me contenterai de démontrer l'avantage de ce système de classement qui illustre bien ce qui se produit à l'interne. De façon plus concrète, on peut, dans une base de données, appliquer sur des champs des index déjà programmés pour améliorer la performance d'accès aux données, par exemple sur une clé primaire ou dans une jointure.
Pour mieux illustrer ce qui se passe, prenons par exemple un échantillon d'un million de cartes numérotées de 1 à 1 million. Si on recherche une valeur dans le lot sans qu'il y ait d'index, on risque de devoir comparer la valeur recherchée avec la valeur de chaque carte, jusqu'à ce qu'on la trouve (et on arrête de comparer dès qu'on l'a trouvée). Par exemple, si on recherche le nombre 420 003, le nombre nécessaire de comparaisons pourrait osciller entre une seule (si on est très chanceux et qu'on tombe sur la bonne carte dès le premier tour) et 1 million (si on est vraiment malchanceux et que c'est la dernière).
En maintenant un index binaire, c'est un peu comme si on classait les cartes en ordre croissant de valeur. Lorsque vient le temps d'en rechercher une, on prend la carte se trouvant au milieu du paquet et on la compare avec la valeur recherchée. Si elle est plus petite, on poursuivra la recherche avec la première moitié du paquet tandis que si elle est plus grande, on utilisera l'autre moitié, et ainsi de suite.
Nombre recherché : 420 003
- Cartes 1 à 1 000 000 (1 million de combinaisons possibles)
On coupe le paquet en deux pour trouver la carte 500000. Le nombre recherché est plus petit donc on garde la moitié de paquet inférieure - Cartes 1 à 500 000 (500 000 combinaisons)
On coupe le paquet en deux. Le nombre recherché est plus grand que 250 000, on poursuit avec la moitié de paquet supérieure - Cartes 250 000 à 500 000 (250 000 combinaisons)
On coupe encore le paquet en deux pour y trouver la carte 375 000. Le nombre recherché est plus grand, on utilise la moitié du paquet supérieure - Cartes 375 000 à 500 000 (125 000 combinaisons)
On coupe en deux : c'est la carte 437 500. Notre nombre est plus petit... - Cartes 375 000 à 437 500 (62 500)
On coupe en deux : voilà la carte 406 250. Notre notre est plus grande - Cartes 406 250 à 437 500 (31 250)
On divise le paquet en deux. La carte du milieu est 421 875. Notre nombre est plus petit - Cartes 406 250 à 421 875 (15 625)
On divise encore. La carte est 414 063, donc notre nombre est plus grand - Cartes 414 063 à 421 875 (7812)
On divise toujours... 417 969. Plus grand.
Ensuite... - Cartes 417 969 à 421 875 (3906)
- Cartes 419 922 à 421 875 (1953)
- Cartes 419 922 à 420898 (946)
- Cartes 419 922 à 420 395 (473)
- Cartes 419 922 à 420 159 (237)
- Cartes 419 922 à 420 040 (118)
- Cartes 419 981 à 420 040 (59)
- Cartes 419 981 à 420 011 (30)
- Cartes 419 996 à 420 011 (15)
- Cartes 419 996 à 420 004 (8)
- Cartes 420 000 à 420 004 (4)
- Cartes 420 002 à 420 004 (2)
- Carte 420 003 trouvée en seulement 21 comparaisons !
À titre d'information, PostgreSQL possède les types d'index suivants :
- B-tree : un arbre "balancé", similaire à l'arbre binaire, conçu pour un large volume de données
- R-tree : spécialisé pour les recherches spaciales et multidimentionnelles
- Hash : indexé comme une table d'hachage et performant avec l'opérateur =
- GiST : Generalized Search Tree, une infrastructure permettant d'implanter différentes stratégies d'index, comme par exemple un cube de données
