PostgreSQLLa base de données la plus sophistiquée au monde.
Documentation PostgreSQL 16.4 » Internes » Index Hash » Implémentation

72.2. Implémentation #

Il existe quatre types de blocs dans un index hash : le bloc de méta-données (bloc zéro), qui contient des informations de contrôle allouées statiquement ; les blocs des buckets principaux  les blocs overflow ; et les blocs bitmap qui conservent la trace des blocs overflow libérés et disponibles pour réutilisation. Dans un but d'adressage, les blocs bitmap sont vus comme un sous-ensemble des blocs overflow.

À la fois le parcours de l'index et l'insertion de lignes nécessitent de localiser le bucket où une ligne donnée doit être située. Pour faire cela, nous avons du nombre de buckets, de la valeur haute (highmask) et de la valeur basse (lowmask) partir de le bloc de méta-données ; néanmoins, il n'est pas souhaitable pour des raisons de performance d'avoir à verrouiller le bloc de méta-données à chaque fois qu'il est nécessaire de réaliser cette opération.

Les blocs buckets primaires et les blocs overflow sont alloués indépendamment car n'importe quel index pourrait avoir plus ou moins de blocs overflow suivant son nombre de buckets. Le code des index hash utilise un ensemble intéressant de règles d'adressage pour accepter un nombre variable de blocs overflow sans avoir à déplacer des blocs buckets primaires après leur création.

Chaque ligne dans la table indexé est représentée par un seul enregistrement dans l'index hash. Les enregistrements de l'index hash sont stockés dans des blocs buckets et, s'ils existent, dans des blocs overflow. Nous accélérons les recherches en conservant les entrées d'index de tout bloc d'index triées par son code de hachage, permettant ainsi l'utilisation de recherche binaire dans un bloc d'index. Notez néanmoins qu'il n'y pas de garantie d'un ordre des codes de hachage sur plusieurs blocs d'index d'un bucket.

Les algorithmes de division de bucket pour étendre un index hash sont trop complexes pour être mentionnés ici, mais ils sont décrits dans le fichier src/backend/access/hash/README. L'algorithme de division est garanti contre les crashs et peut être relancé s'il ne s'est pas terminé correctement.