Dans certaines situations, il est nécessaire d'utiliser un index pour rechercher efficacement des informations, mais l'utilisation d'un index B-tree peut s'avérer trop complexe et redondante. Dans ces cas, un index de hachage peut constituer une alternative plus appropriée.

Un index de hachage est un type d'index de base de données qui utilise une fonction de hachage pour associer les valeurs indexées à des emplacements dans une table de hachage.
Dans ce type d'index, les valeurs de la colonne cible sont hachées, c'est-à-dire transformées en une valeur de taille fixe ou en un code de hachage, qui est ensuite utilisé comme index pour retrouver les lignes de données.

Comment cela fonctionne-t-il ?

Dans un index de hachage, le processus de hachage consiste à transformer une valeur de clé d'index en un code de hachage à l'aide d'une fonction de hachage. Ce code de hachage est ensuite utilisé pour déterminer l'emplacement, ou le compartiment, où les données correspondantes sont stockées dans l'index.

Vous pouvez trouver plus d'informations sur le hachage dans le cours Aperçu des algorithmes et des structures de données.

Prenons l'exemple d'un index de hachage pour un système de catalogue de bibliothèque où chaque titre de livre est indexé par son ISBN (International Standard Book Number).

Dans cet exemple, une fonction de hachage est utilisée pour convertir l'ISBN d'un livre en un code de hachage hexadécimal, tel que 0x7FA4, à l'aide d'une série d'opérations mathématiques sur les chiffres de l'ISBN.
Ce code de hachage sert d'identifiant unique, déterminant l'emplacement dans la table de hachage où se trouve un lien vers la ligne correspondante dans la table, contenant toutes les informations sur ce livre en particulier.

Caractéristiques principales

1. Recherche rapide : Les index de hachage offrent des recherches rapides pour les comparaisons d’égalité. Lors de la recherche d’une valeur spécifique, PostgreSQL calcule le hachage de la valeur puis accède directement à l’emplacement correspondant dans l’index, ce qui rend la récupération très efficace ;

2. Prise en charge limitée des opérateurs : Contrairement aux index B-tree, les index de hachage ne prennent en charge que les comparaisons d’égalité (=), et non les requêtes de plage (<, >, <=, >=) ni le tri. Cette limitation rend les index de hachage moins polyvalents que les index B-tree ;

3. Plus rapide pour certains cas d’utilisation : Dans les scénarios où la charge de travail implique un grand nombre de recherches d’égalité, comme l’application de clés primaires ou de contraintes d’unicité, les index de hachage peuvent surpasser les index B-tree. Cependant, leur avantage de performance diminue pour les requêtes de plage ou les données qui ne s’adaptent pas bien à l’algorithme de hachage.

Implémentation

Nous pouvons implémenter un index de hachage en SQL avec l’instruction suivante :

CREATE INDEX hash_index_name ON table_name USING HASH (column_name1, column_name2,... );

En conséquence, les valeurs de column_name1, column_name2,... seront hachées et la table de hachage sera créée. Cela permettra une récupération plus rapide des lignes de données requises.