Introduction au hachage dans le SGBD
Lorsque nous parlons de l'énorme structure de la base de données et de sa complexité, il devient très inefficace de rechercher tous les index et atteindre les données souhaitées devient très vague et une possibilité complexe. En utilisant la technique de hachage, ces états peuvent être atteints et un pointeur direct peut être attribué pour connaître l'emplacement exact et direct sur le disque pour l'enregistrement particulier sans utiliser la structure d'index complexe. Les données en cas de technique de hachage sont stockées sous la forme de blocs de données dont l'adresse est générée en utilisant la fonction généralement appelée fonction de hachage. L'emplacement dans la mémoire où cela réside et où les enregistrements sont stockés est appelé blocs de données ou compartiment de données.
Types de hachage dans le SGBD
Il existe généralement deux types de techniques de hachage dans le SGBD:
1. Hachage statique
2. Hachage dynamique
1) Hachage statique
Dans le cas du hachage statique, l'ensemble de données formé et l'adresse de compartiment sont les mêmes. Cela signifie que si nous essayons de générer l'adresse pour USER_ID = 113 en utilisant le module de fonction de hachage 5, il nous fournit toujours la résultante comme 3 avec la même adresse de bucket. Dans ce cas, il n'y aura aucun changement dans l'adresse du compartiment fourni. Par conséquent, le nombre de godets reste constant tout au long de l'opération.
Fonctionnement du hachage de type statique
une. Recherche d'un enregistrement: s'il est nécessaire de trouver l'enregistrement, la même fonction de hachage exacte est utilisée pour récupérer l'adresse et le chemin du compartiment de données avec les données stockées.
b. Insertion d'un nouvel enregistrement: si un nouvel enregistrement et un nouvel enregistrement sont placés dans une table, une adresse est générée pour un nouvel enregistrement sur la base de la clé de hachage, stockant ainsi l'enregistrement sur cet emplacement.
- Suppression de l'enregistrement: Pour que l'enregistrement soit supprimé, cet enregistrement doit d'abord être récupéré et peut être supprimé. Une fois cette tâche terminée, les enregistrements doivent être supprimés pour cette adresse mémoire.
- Mise à jour d'un enregistrement: Afin de mettre à jour l'enregistrement, nous recherchons d'abord l'enregistrement en utilisant la fonction basée sur le hachage et une fois cela fait, notre enregistrement de données peut être considéré comme étant dans un état mis à jour. Afin que nous puissions insérer un nouvel enregistrement dans le fichier et que l'adresse générée à partir de la fonction basée sur le hachage et du compartiment de données ne soit pas vide ou si les données sont déjà présentes dans l'adresse fournie. Cette situation qui survient particulièrement en cas de hachage statique peut être mieux appelée débordement de godet et, par conséquent, il existe certaines façons de résoudre ce problème, telles que:
(i) Hachage ouvert: si une fonction de hachage génère l'adresse pour laquelle les données peuvent déjà être vues dans l'état stocké, dans ce cas, le niveau suivant du compartiment sera automatiquement alloué. Ce mécanisme peut être qualifié de technique de sondage linéaire.
Par exemple, si R3 est la nouvelle adresse qui doit être mise, la fonction basée sur le hachage générera l'adresse en tant que numéro 102 pour l'adresse R3. L'adresse générée est en état complet et, par conséquent, le système est censé rechercher le nouveau compartiment de données qui est 113 et affecter R3 à ce compartiment de données.
(ii) Hachage fermé: lorsque les compartiments sont complètement pleins, un nouveau compartiment est ensuite alloué pour un résultat de hachage particulier qui est lié juste après celui terminé précédemment et, par conséquent, cette méthode est appelée technique de chaînage à débordement.
Par exemple, R3 est la nouvelle adresse qui doit être placée dans la nouvelle table, la fonction de hachage est utilisée pour générer l'adresse en tant que numéro 110. Ce compartiment, à son tour, est plein et ne peut donc pas recevoir de nouvelles données et, par conséquent, un nouveau compartiment est mis à la fin après 100.
2) Hachage dynamique
Ce type de méthode basée sur le hachage peut être utilisé pour résoudre les problèmes de base du hachage basé sur la statique comme ceux tels que le débordement du seau, car les seaux de données peuvent croître et se réduire avec la taille, c'est une technique plus optimisée pour l'espace et, par conséquent, elle est appelée extensible méthode basée sur le hachage. Dans cette méthode, le hachage est rendu dynamique, ce qui signifie que l'activité d'insertion ou la suppression est autorisée sans entraîner de mauvaises performances.
une. Recherche d'une clé: calculez l'adresse de hachage de la clé requise et vérifiez le nombre de bits utilisés dans le cas d'un répertoire appelé i. Ensuite, ceux qui sont les moins significatifs des bits I sont extraits du répertoire, ce qui donne une idée de l'index du répertoire. En utilisant cette valeur d'index, accédez au répertoire pour trouver l'adresse de compartiment à rechercher pour les enregistrements actuels.
b. Insertion d'un nouvel enregistrement: au début, vous devez suivre exactement la même procédure de récupération qui doit se retrouver quelque part dans le compartiment. Recherchez l'espace dans ce compartiment, puis placez-y les enregistrements. Si ce compartiment créé est complet et plein, le compartiment sera divisé et les enregistrements seront redistribués.
Par exemple, les deux derniers bits des chiffres 2 et 4 sont 00. Ils iront donc dans le seau B0 et ainsi de suite selon la fonction module. La clé 9 a une adresse de 10001 qui doit être présente dans le premier compartiment mais sera divisée et se déplacera vers le nouveau compartiment B1 et cela continue jusqu'à ce que tous les compartiments et les clés soient hachés dynamiquement. La fonction de hachage est utilisée d'une manière où la fonction de hachage est utilisée pour choisir la colonne et sa valeur pour générer l'adresse. Nombre maximal de fois où la fonction de hachage utilise la clé primaire qui à son tour est utilisée pour générer les adresses du bloc de données. Il s'agit d'une fonction mathématique simple où la clé primaire peut également être considérée comme l'adresse du bloc de données, ce qui signifie que chaque ligne avec la même adresse que celle de la clé primaire sera stockée dans le bloc de données.
Articles recommandés
Ceci est un guide de hachage dans le SGBD. Nous discutons ici de l'introduction et des différents types de hachage dans le SGBD qui incluent un hachage statique et un hachage dynamique avec des exemples. Vous pouvez également consulter les articles suivants pour en savoir plus -
- Modèles de données dans le SGBD
- Avantages du SGBD
- Outil d'intégration de données
- Qu'est-ce que le SGBDR?