De la performance en BDD : indexer correctement

Cette présentation s'est faite dans le cadre de la veille techno mise en place chez Axopen. Elle a pour objectif de rappeler aux développeurs les différentes méthodes pour indexer des données. Dans Postgres, il existe trois grandes familles d'indexs, qui ont tous des fonctionnements et des spécificités.

Bien savoir les choisir, c'est savoir derrière les optimiser, et c'est savoir comment les exploiter.

Les Slides

Un résumé rapide

Dans une table dans une base de données relationelle, les tuples sont insérés la plupart du temps sans ordre particulier.

Ainsi, quand on veut chercher un tuple précis (ou un ensemble de tuples qui valident une condition), on est obligé de parcourir toute la table jusqu'à le trouver.

Pour accélérer ça, il est possible de mettre en place un index : on utilise une structure de données optimisée pour chercher une valeur.

Pour parler crûment, on cherche à battre la complexité $Θ (n)$ .

La complexité

Le rappel ne fait jamais de mal à personne, on définit des "classes" de complexité. On en a trois (avec $f$ une fonction):

$O (f)$ , qui veut dire que ce qu'on étudie est plus petit ou équivalent (borné par le haut) à $f$ (qui en informatique sera souvent $n$ , $l o g (n)$ n ou $n^{2}$ )
$Ω (f)$ , qui signifie l'inverse, que la fonction $f$ borne par le dessous ce qu'on étudie
$Θ (f)$ , le combo des deux, qui signifie que l'on borne par le dessus et par le dessous l'objet de notre étude par $f$

Pour battre cette complexité, on a deux grands types de structures de données à notre disposition:

les tables de hachage
les arbres

Les tables de hachage

Pour les tables de hachage, l'idée derrière est simple : on a un grand tableau, et une fonction qui tourne en $O (1)$ qui nous détermine la position d'un objet dans le tableau. Pour retrouver un objet dans le tableau, on a juste à connaître sa position, et on fait ça en $O (1)$ , on bat donc à plates coutures la complexité en $O (n)$ .

Le seul problème des tables de hachage, c'est qu'il n'y a aucune propriété d'ordre dans la façon dont les données sont rangées à l'intérieur. Ainsi, pour chercher un tuple précis, c'est très efficace. Pour chercher tous les tuples plus grands qu'une certaine valeur, ça sera impossible.

Les arbres

L'idée derrière un arbre, c'est que chaque niveau nous permets de trier des valeurs. Ainsi, pour chercher un