SGBD - Hashing

Pour une structure de base de données énorme, il peut être presque impossible de rechercher toutes les valeurs d'index à travers tout son niveau, puis d'atteindre le bloc de données de destination pour récupérer les données souhaitées. Le hachage est une technique efficace pour calculer l'emplacement direct d'un enregistrement de données sur le disque sans utiliser la structure d'index.

Le hachage utilise des fonctions de hachage avec des clés de recherche comme paramètres pour générer l'adresse d'un enregistrement de données.

Organisation de hachage

  • Bucket- Un fichier de hachage stocke les données au format de compartiment. Le seau est considéré comme une unité de stockage. Un compartiment stocke généralement un bloc de disque complet, qui à son tour peut stocker un ou plusieurs enregistrements.

  • Hash Function - Une fonction de hachage, h, est une fonction de mappage qui mappe tout l'ensemble des clés de recherche Kà l'adresse où les enregistrements réels sont placés. Il s'agit d'une fonction allant des clés de recherche aux adresses de compartiment.

Hashing statique

Dans le hachage statique, lorsqu'une valeur de clé de recherche est fournie, la fonction de hachage calcule toujours la même adresse. Par exemple, si la fonction de hachage mod-4 est utilisée, elle ne doit générer que 5 valeurs. L'adresse de sortie doit toujours être la même pour cette fonction. Le nombre de seaux fournis reste inchangé à tout moment.

Opération

  • Insertion - Lorsqu'un enregistrement doit être saisi à l'aide d'un hachage statique, la fonction de hachage h calcule l'adresse du compartiment pour la clé de recherche K, où l'enregistrement sera stocké.

    Adresse du godet = h (K)

  • Search - Lorsqu'un enregistrement doit être récupéré, la même fonction de hachage peut être utilisée pour récupérer l'adresse du compartiment où les données sont stockées.

  • Delete - Il s'agit simplement d'une recherche suivie d'une opération de suppression.

Débordement du godet

La condition de débordement de seau est connue sous le nom de collision. Il s'agit d'un état fatal pour toute fonction de hachage statique. Dans ce cas, le chaînage de débordement peut être utilisé.

  • Overflow Chaining- Lorsque les compartiments sont pleins, un nouveau compartiment est alloué pour le même résultat de hachage et est lié après le précédent. Ce mécanisme s'appelleClosed Hashing.

  • Linear Probing- Lorsqu'une fonction de hachage génère une adresse à laquelle les données sont déjà stockées, le prochain compartiment libre lui est alloué. Ce mécanisme s'appelleOpen Hashing.

Hashing dynamique

Le problème avec le hachage statique est qu'il ne se développe pas ou ne diminue pas de manière dynamique à mesure que la taille de la base de données augmente ou diminue. Le hachage dynamique fournit un mécanisme dans lequel des compartiments de données sont ajoutés et supprimés de manière dynamique et à la demande. Le hachage dynamique est également connu sous le nom deextended hashing.

La fonction de hachage, dans le hachage dynamique, est conçue pour produire un grand nombre de valeurs et seules quelques-unes sont utilisées initialement.

Organisation

Le préfixe d'une valeur de hachage entière est considéré comme un index de hachage. Seule une partie de la valeur de hachage est utilisée pour le calcul des adresses de compartiment. Chaque index de hachage a une valeur de profondeur pour indiquer combien de bits sont utilisés pour calculer une fonction de hachage. Ces bits peuvent adresser 2n buckets. Lorsque tous ces bits sont consommés, c'est-à-dire lorsque tous les compartiments sont pleins, la valeur de profondeur est augmentée linéairement et deux fois les compartiments sont alloués.

Opération

  • Querying - Regardez la valeur de profondeur de l'index de hachage et utilisez ces bits pour calculer l'adresse du compartiment.

  • Update - Effectuez une requête comme ci-dessus et mettez à jour les données.

  • Deletion - Effectuer une requête pour localiser les données souhaitées et les supprimer.

  • Insertion - Calculer l'adresse du bucket

    • Si le seau est déjà plein.
      • Ajoutez plus de seaux.
      • Ajoutez des bits supplémentaires à la valeur de hachage.
      • Recalculez la fonction de hachage.
    • Autre
      • Ajoutez des données au bucket,
    • Si tous les compartiments sont pleins, effectuez les remèdes du hachage statique.

Le hachage n'est pas favorable lorsque les données sont organisées dans un certain ordre et que les requêtes nécessitent une plage de données. Lorsque les données sont discrètes et aléatoires, le hachage est le meilleur.

Les algorithmes de hachage ont une complexité élevée par rapport à l'indexation. Toutes les opérations de hachage sont effectuées en temps constant.