Hachage dans les SGBD : techniques de hachage statique et dynamique

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

Dans le SGBD, le hachage est une technique permettant de rechercher directement l'emplacement des données souhaitées sur le disque sans utiliser de structure d'index. La méthode de hachage est utilisée pour indexer et récupérer des éléments dans une base de données, car il est plus rapide de rechercher cet élément spécifique à l'aide de la clé hachée la plus courte au lieu d'utiliser sa valeur d'origine. Les données sont stockées sous forme de blocs de données dont l'adresse est générée en appliquant une fonction de hachage dans l'emplacement mémoire où ces enregistrements sont stockés, appelé bloc de données ou compartiment de données.

Pourquoi avons-nous besoin de hachage ?

Voici les situations dans le SGBD où vous devez appliquer la méthode Hashing :

Pour une énorme structure de base de données, il est difficile de rechercher toutes les valeurs d'index à tous ses niveaux et vous devez ensuite atteindre le bloc de données de destination pour obtenir les données souhaitées.
La méthode de hachage est utilisée pour indexer et récupérer des éléments dans une base de données, car il est plus rapide de rechercher cet élément spécifique à l'aide de la clé hachée la plus courte au lieu d'utiliser sa valeur d'origine.
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 les terminologies importantes utilisées dans le hachage :

Compartiment de données – Les compartiments de données sont des emplacements de mémoire où les enregistrements sont stockés. On l’appelle également unité de stockage.
ACTIVITES: Un Clé SGBD est un attribut ou un ensemble d'attributs qui vous aide à identifier une ligne (tuple) dans une relation (table). Cela vous permet de trouver la relation entre deux tables.
Fonction de hachage: Une fonction de hachage est une fonction de mappage qui mappe l'ensemble des clés de recherche à l'adresse où les enregistrements réels sont placés.
Sondage linéaire – Le sondage linéaire est un intervalle fixe entre les sondes. Dans cette méthode, le prochain bloc de données disponible est utilisé pour saisir le nouvel enregistrement, au lieu d'écraser l'ancien enregistrement.
Sondage quadratique– Il vous aide à déterminer la nouvelle adresse du compartiment. Il vous aide à ajouter un intervalle entre les sondes en ajoutant la sortie consécutive du polynôme quadratique à la valeur de départ donnée par le calcul d'origine.
Indice de hachage – C'est une adresse du bloc de données. Une fonction de hachage peut être une fonction mathématique simple, voire une fonction mathématique complexe.
Double Hachage -Double Le hachage est une méthode de programmation informatique utilisée dans les tables de hachage pour résoudre les problèmes de collision.
Débordement de godet: La condition de débordement du seau est appelée collision. C’est une étape fatale pour que tout statique doive fonctionner.

Types de techniques de hachage

Il existe principalement deux types de méthodes/techniques de hachage SQL :

Hashing statique
Hashing dynamique

Hachage statique

Lors du hachage statique, l’adresse du compartiment de données résultante 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 1. Ainsi, vous ne verrez aucun changement dans l’adresse du compartiment.

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

Fonctions de hachage statique

Insérer un enregistrement: Lorsqu'un nouvel enregistrement doit être inséré dans la table, vous pouvez générer une adresse pour le nouvel enregistrement à l'aide de sa clé de hachage. Lorsque l'adresse est générée, l'enregistrement est automatiquement stocké à cet emplacement.
Recherche: Lorsque vous devez récupérer l'enregistrement, la même fonction de hachage devrait être utile pour récupérer l'adresse du compartiment dans lequel les données doivent être stockées.
Supprimer un enregistrement: À l'aide de la fonction de hachage, vous pouvez d'abord récupérer l'enregistrement que vous souhaitez supprimer. Ensuite, vous pouvez supprimer les enregistrements de cette adresse en mémoire.

Le hachage statique est divisé en

Hachage ouvert
Fermez le hachage.

Hachage ouvert

Dans la méthode de hachage ouvert, au lieu d'écraser l'ancien, le prochain bloc de données disponible est utilisé pour saisir 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 elle est déjà occupée par une autre valeur. C'est pourquoi le système recherche le prochain compartiment de données 501 et lui attribue A2.

Fermer le hachage

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

Hashing dynamique

Le hachage dynamique offre un mécanisme dans lequel des compartiments de données sont ajoutés et supprimés de manière dynamique et à la demande. Dans ce hachage, la fonction de hachage vous aide à créer un grand nombre de valeurs.

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

Vous trouverez ci-dessous les principales différences entre l'indexation et le hachage.

Paramètres	Indexation des commandes	Hachage
Stockage de l'adresse	Les adresses en mémoire sont triées selon une valeur de 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	Il peut diminuer lorsque les données augmentent dans le fichier de hachage. Comme il stocke les données sous une forme triée lorsqu'une opération (insertion/suppression/mise à jour) est effectuée qui diminue ses performances.	Les performances du hachage seront meilleures lorsqu’il y aura un ajout et une suppression constants de données. Cependant, lorsque la base de données est volumineuse, l’organisation des fichiers de hachage et leur maintenance seront plus coûteuses.
Utiliser pour	Préférée pour la récupération de données sur une plage, ce qui signifie que chaque fois qu'il existe des données de récupération pour une plage particulière, cette méthode est une option idéale.	Il s'agit d'une méthode idéale lorsque vous souhaitez récupérer un enregistrement particulier en fonction de la clé de recherche. Cependant, cela ne fonctionnera bien que lorsque la fonction de hachage sera sur la clé de recherche.
Gestion de la mémoire	Il y aura de nombreux blocs de données inutilisés en raison de l'opération de suppression/mise à jour. Ces blocs de données ne peuvent pas être libérés pour être réutilisés. C'est pourquoi un entretien régulier de la mémoire est nécessaire.	Dans les méthodes de hachage statiques et dynamiques, la mémoire est toujours gérée. Le débordement du bucket est également parfaitement géré pour étendre le hachage statique.

Qu'est-ce que la collision ?

La collision de hachage est un état dans lequel les hachages résultants de deux ou plusieurs données de l'ensemble de données mappent à tort le même endroit dans l'ensemble de données. table de hachage.

Comment gérer les collisions de hachage ?

Il existe deux techniques que vous pouvez utiliser pour éviter une collision de hachage :

ressasser: Cette méthode invoque une fonction de hachage secondaire, qui est appliquée en continu jusqu'à ce qu'un emplacement vide soit trouvé, où un enregistrement doit être placé.
Chaînage: La méthode de chaînage crée une liste liée d’éléments dont la clé est hachée à la même valeur. Cette méthode nécessite un champ de lien supplémentaire vers chaque position de la table.

Résumé

In SGBD, le hachage est une technique permettant de rechercher directement l'emplacement des données souhaitées sur le disque sans utiliser de structure d'index.
La méthode de hachage est utilisée pour indexer et récupérer des éléments dans une base de données, car il est plus rapide de rechercher cet élément spécifique à l'aide de la clé hachée la plus courte au lieu d'utiliser sa valeur d'origine.
Godet de données, clé, fonction de hachage, sondage linéaire, sondage quadratique, index de hachage, Double Hachage, Bucket Overflow sont des terminologies importantes utilisées dans le hachage
Il existe deux types de méthodes de hachage : 1) le hachage statique 2) le hachage dynamique
Lors du hachage statique, l’adresse du compartiment de données résultante restera toujours la même.
Le hachage dynamique offre un mécanisme dans lequel des compartiments de données sont ajoutés et supprimés de manière dynamique et à la demande.
Dans l'ordre, les adresses d'indexation dans la mémoire sont triées selon une valeur critique tandis que dans le hachage, les adresses sont toujours générées à l'aide d'une fonction de hachage sur la valeur clé.
La collision de hachage est un état dans lequel les hachages résultants de deux ou plusieurs données de l'ensemble de données mappent à tort le même endroit dans la table de hachage.
Le rehachage et le chaînage sont deux méthodes qui vous aident à éviter les collisions de hachage.

Tu pourrais aimer: