Hachage dans les SGBD : techniques de hachage statique et dynamique

⚡ Résumé intelligent

Le hachage dans un SGBD est une technique qui calcule l'emplacement disque d'un enregistrement directement à partir de sa clé, sans parcourir l'index. Une fonction de hachage associe les clés de recherche à des compartiments de données, et le hachage statique ou dynamique gère la taille de ces compartiments.

| Idée de base : Une fonction de hachage transforme une clé en une adresse de compartiment, de sorte qu'un enregistrement est trouvé en une seule étape plutôt que par parcours d'index.
🪣 Compartiment de données : L'emplacement mémoire, ou unité de stockage, où sont placés les enregistrements ayant le même hachage.
📌 Hachage statique : Le nombre de compartiments est fixe, donc une clé donnée correspond toujours à la même adresse.
📈 Hachage dynamique : Des compartiments sont ajoutés et supprimés à la demande en fonction de l'évolution du volume de données.
💥 Collision: Carte des deux clésping dans le même compartiment, résolu par sondage, réhachage ou chaînage.
🔍 Meilleur pour : Recherche par correspondance exacte sur la clé de recherche, où le hachage surpasse l'indexation ordonnée.
(I.e. Compromis : L'indexation ordonnée est préférable pour les requêtes par plage ; le hachage est préférable pour les insertions constantes et les recherches ponctuelles.

Qu’est-ce que le hachage dans un SGBD ?

Dans un SGBD, le hachage est une technique permettant de rechercher directement l'emplacement des données souhaitées sur le disque sans utiliser d'index. Cette méthode est utilisée pour indexer et récupérer les éléments d'une base de données, car la recherche d'un élément spécifique est plus rapide grâce à sa clé hachée, plus courte, qu'à sa valeur originale. Les données sont stockées sous forme de blocs de données dont l'adresse est générée par l'application d'une fonction de hachage ; l'emplacement mémoire où ces enregistrements sont stockés est appelé un bloc. bloc de données ou compartiment de données.

Pourquoi avons-nous besoin du hachage ?

Voici les situations, dans un SGBD, où vous devez appliquer la méthode de hachage :

Pour une structure de base de données de grande taille, il est difficile de parcourir toutes les valeurs d'index à tous leurs niveaux, puis d'atteindre le bloc de données de destination pour obtenir les données souhaitées.
Le hachage est utilisé pour indexer et récupérer des éléments dans une base de données, car la recherche d'un élément spécifique est plus rapide avec la clé hachée plus courte qu'avec la valeur originale.
Le hachage est une méthode idéale pour calculer l'emplacement direct d'un enregistrement de données sur le disque sans utiliser de structure d'index.
C'est également une technique utile pour implémenter des dictionnaires.

Terminologies importantes dans le hachage

Voici quelques termes importants utilisés dans le hachage :

Compartiment de données : Les compartiments de données sont des emplacements mémoire où les enregistrements sont stockés. On les appelle également unités de stockage.
Clé: a Clé SGBD est un attribut ou un ensemble d'attributs qui vous aide à identifier une ligne (tuple) dans une relation (table).
Fonction de hachage : une carteping fonction qui associe chaque clé de recherche à l'adresse où se trouvent les enregistrements correspondants.
Sondage linéaire : Un intervalle fixe est utilisé entre les sondages. Dans cette méthode, le prochain bloc de données disponible est utilisé pour saisir le nouvel enregistrement, au lieu d'écraser l'enregistrement précédent.
Sondage quadratique : permet de déterminer la nouvelle adresse du compartiment en ajoutant la sortie consécutive d'un polynôme quadratique à la valeur initiale donnée par le calcul d'origine.
Index de hachage : L'adresse du bloc de données. Une fonction de hachage peut être une fonction mathématique simple ou complexe.
Double Hachage : une méthode utilisée dans les tables de hachage pour résoudre les collisions en appliquant une seconde fonction de hachage.
Débordement du seau : Le débordement du compartiment est appelé collision. Il s'agit d'une étape fatale pour toute fonction de hachage statique.

Types de techniques de hachage

Il existe principalement deux types de techniques de hachage dans les SGBD :

Hashing statique
Hashing dynamique

La principale différence entre les deux réside dans le fait que le nombre de compartiments est fixe ou non, comme l'expliquent les deux sections suivantes.

Hashing statique

En hachage statique, l'adresse du compartiment de données résultant restera toujours la même.

Par conséquent, si vous générez une adresse pour, par exemple, ID_étudiant = 10 en utilisant la fonction de hachage mod(3), l'adresse du bucket résultant sera toujours 1Vous ne constaterez donc aucun changement dans l'adresse du compartiment.

Par conséquent, dans la méthode de hachage statique, le nombre de compartiments de données en mémoire reste toujours constant.

Fonctions de hachage statique

Insertion d'un enregistrement : Lorsqu'un nouvel enregistrement doit être inséré dans la table, une adresse est générée à partir de sa clé de hachage. Une fois l'adresse générée, l'enregistrement est stocké à cet emplacement.
Recherche: Lorsque vous devez récupérer l'enregistrement, la même fonction de hachage est utilisée pour récupérer l'adresse du compartiment où les données sont stockées.
Supprimer un enregistrement : En utilisant la fonction de hachage, vous récupérez d'abord l'enregistrement que vous souhaitez supprimer, puis vous le supprimez de cette adresse en mémoire.

Le hachage statique se divise en plusieurs sous-catégories :

Hachage ouvert
Hachage fermé

Hachage ouvert

Dans la méthode de hachage ouvert, au lieu d'écraser l'enregistrement précédent, le prochain bloc de données disponible est utilisé pour insérer le nouvel enregistrement. Cette méthode est également connue sous le nom de sondage linéaire.

Par exemple, A2 est un nouvel enregistrement que vous souhaitez insérer. La fonction de hachage génère l'adresse 222, mais celle-ci est déjà utilisée. C'est pourquoi le système recherche le prochain emplacement de données, 501, et y assigne A2.

Comment fonctionne le hachage ouvert avec le sondage linéaire — Comment fonctionne le hachage ouvert

Hachage fermé

Dans la méthode de hachage fermée, lorsque les compartiments sont pleins, un nouveau compartiment est alloué pour le même hachage et le résultat est lié après le précédent.

Hashing dynamique

Le hachage dynamique offre un mécanisme permettant d'ajouter et de supprimer des compartiments de données de manière dynamique et à la demande. Dans cette méthode, la fonction de hachage permet de créer un grand nombre de valeurs, et la structure s'adapte en fonction des données. Cela la rend particulièrement adaptée aux tables dont la taille est imprévisible, pour lesquelles le hachage statique entraînerait un gaspillage d'espace ou un dépassement de capacité.

Différence entre l'indexation ordonnée et le hachage

Voici les principales différences entre l'indexation et le hachage :

Paramètres	Indexation ordonnée	Hachage
Stockage de l'adresse	Les adresses en mémoire sont triées selon une valeur clé appelée clé primaire.	Les adresses sont toujours générées à l'aide d'une fonction de hachage sur la valeur clé.
Performances	Elle peut diminuer à mesure que le nombre de données augmente, car les données sont stockées triées et chaque insertion, suppression ou mise à jour les réorganise.	Les performances sont optimales avec l'ajout et la suppression constants de données. Pour une base de données volumineuse, la maintenance du fichier de hachage devient plus coûteuse.
Utiliser pour	Privilégié pour la récupération de données par plage, lorsque les données sont extraites pour une plage particulière.	Idéal pour récupérer un enregistrement particulier en fonction de la clé de recherche, et ne fonctionne correctement que lorsque la fonction de hachage est appliquée à la clé de recherche.
Gestion de la mémoire	De nombreux blocs de données inutilisés résultent des opérations de suppression et de mise à jour et ne peuvent être libérés pour être réutilisés ; une maintenance régulière est donc nécessaire.	Dans le hachage statique et dynamique, la mémoire est toujours gérée et le débordement du compartiment est traité pour étendre le hachage statique.

En bref, choisissez ordonné indexage pour les requêtes par plage et le hachage pour les recherches par correspondance exacte sur la clé.

Qu'est-ce que la collision ?

Une collision de hachage se produit lorsque les hachages résultants de deux ou plusieurs éléments de l'ensemble de données pointent incorrectement vers le même emplacement dans la table. table de hachage.

Comment gérer une collision de hachage

Il existe deux techniques permettant d'éviter une collision de hachage :

Récapitulation : Cette méthode fait appel à une fonction de hachage secondaire, qui est appliquée en continu jusqu'à ce qu'un emplacement vide soit trouvé pour y placer un enregistrement.
Enchaînement : La méthode de chaînage crée une liste chaînée d'éléments dont les clés ont la même valeur de hachage. Cette méthode nécessite un champ de lien supplémentaire à chaque position du tableau.

FAQ

Le hachage statique conserve un nombre fixe de compartiments, ce qui peut entraîner un débordement lorsque les données augmentent. Le hachage dynamique, quant à lui, ajoute et supprime des compartiments à la demande, s'adaptant ainsi aux variations de volume de données sans nécessiter une reconstruction complète.

Pour les requêtes par plage, le hachage répartit les clés dans plusieurs compartiments, empêchant ainsi les requêtes de comparaison (entre ou supérieur à) de les parcourir dans l'ordre. Un index ordonné conserve les clés triées et est donc plus adapté.

Un compartiment déborde lorsque le nombre d'enregistrements hachés dépasse sa capacité. En hachage statique, ce phénomène est fréquent avec l'augmentation du volume de données et est géré par l'adressage ouvert, le chaînage ou l'utilisation de compartiments de débordement.

Les systèmes d'IA utilisent le hachage pour accélérer la recherche de caractéristiques et pour l'astuce de hachage, qui consiste à transformer les catégories à forte cardinalité en un vecteur fixe. Le hachage par similarité permet également de regrouper efficacement les enregistrements quasi-identiques.

Le rehachage permet de trouver un autre emplacement libre dans la même table grâce à une seconde fonction. Le chaînage conserve les enregistrements en conflit dans une liste chaînée associée au compartiment, de sorte que la table elle-même ne remplit jamais deux fois le même emplacement.