Indexation par Hachage

Dans certaines situations, nous avons besoin d'un index pour rechercher efficacement des informations, mais utiliser un index B-tree peut être trop complexe et redondant. Dans de tels cas, un index de hachage peut être 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 mapper les valeurs indexées aux emplacements dans une table de hachage. Dans ce type d'index, les valeurs de la colonne cible sont hachées, c'est-à-dire qu'elles sont transformées en une valeur de taille fixe ou un code de hachage, qui est ensuite utilisé comme index pour récupérer les lignes de données.

Comment ça fonctionne ?

Dans un index de hachage, le processus de hachage implique de 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 Structures de Données.

Considérons 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, nous utilisons une fonction de hachage pour convertir l'ISBN d'un livre en un code de hachage hexadécimal, tel que 0x7FA4, en utilisant 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ù il y a un lien vers la ligne correspondante dans la table, contenant toutes les informations sur ce livre particulier.

Caractéristiques clés

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, rendant la récupération très efficace ;

2. Support limité des opérateurs : Contrairement aux index B-tree, les index de hachage ne supportent que les comparaisons d'égalité (=), pas les requêtes de plage (<, >, <=, >=) ou le tri. Cette limitation rend les index de hachage moins polyvalents par rapport aux index B-tree ;

3. Plus rapide pour certains cas d'utilisation : Dans les scénarios où la charge de travail implique un volume élevé de recherches d'égalité, comme l'application de clés primaires ou de contraintes uniques, 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.

Mise en œuvre

Nous pouvons implémenter un index de hachage en SQL en utilisant l'instruction suivante :

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.