logo

Indexation dans le SGBD

  • L'indexation est utilisée pour optimiser les performances d'une base de données en minimisant le nombre d'accès au disque requis lors du traitement d'une requête.
  • L'index est un type de structure de données. Il est utilisé pour localiser et accéder rapidement aux données d’une table de base de données.

Structure de l'indice :

Des index peuvent être créés à l'aide de certaines colonnes de base de données.

Indexation du SGBD dans le SGBD
  • La première colonne de la base de données est la clé de recherche qui contient une copie de la clé primaire ou de la clé candidate de la table. Les valeurs de la clé primaire sont stockées dans un ordre trié afin que les données correspondantes soient facilement accessibles.
  • La deuxième colonne de la base de données est la référence des données. Il contient un ensemble de pointeurs contenant l'adresse du bloc de disque où se trouve la valeur d'une clé particulière.

Méthodes d'indexation

Indexation du SGBD dans le SGBD

Indices ordonnés

Les index sont généralement triés pour accélérer la recherche. Les indices triés sont appelés indices ordonnés.

Exemple : Supposons que nous ayons une table d'employés avec des milliers d'enregistrements et dont chacun mesure 10 octets. Si leurs identifiants commencent par 1, 2, 3... et ainsi de suite et nous devons rechercher l'étudiant avec l'ID-543.

  • Dans le cas d'une base de données sans index, nous devons rechercher le bloc disque depuis le début jusqu'à ce qu'il atteigne 543. Le SGBD lira l'enregistrement après avoir lu 543*10=5430 octets.
  • Dans le cas d'un index, nous rechercherons à l'aide d'index et le SGBD lira l'enregistrement après avoir lu 542*2= 1084 octets, ce qui est très inférieur au cas précédent.

Index primaire

  • Si l'index est créé sur la base de la clé primaire de la table, on parle alors d'indexation primaire. Ces clés primaires sont uniques à chaque enregistrement et contiennent une relation 1:1 entre les enregistrements.
  • Comme les clés primaires sont stockées dans un ordre trié, les performances de l’opération de recherche sont assez efficaces.
  • L'index primaire peut être classé en deux types : l'index dense et l'index clairsemé.

Indice dense

  • L'index dense contient un enregistrement d'index pour chaque valeur de clé de recherche dans le fichier de données. Cela rend la recherche plus rapide.
  • En cela, le nombre d'enregistrements dans la table d'index est le même que le nombre d'enregistrements dans la table principale.
  • Il a besoin de plus d'espace pour stocker l'enregistrement d'index lui-même. Les enregistrements d'index ont la clé de recherche et un pointeur vers l'enregistrement réel sur le disque.
Indexation du SGBD dans le SGBD

Index clairsemé

  • Dans le fichier de données, l'enregistrement d'index apparaît uniquement pour quelques éléments. Chaque élément pointe vers un bloc.
  • En cela, au lieu de pointer vers chaque enregistrement de la table principale, l'index pointe vers les enregistrements de la table principale dans un espace vide.
Indexation du SGBD dans le SGBD

Index de clustering

  • Un index clusterisé peut être défini comme un fichier de données ordonné. Parfois, l'index est créé sur des colonnes de clé non primaire qui peuvent ne pas être uniques pour chaque enregistrement.
  • Dans ce cas, pour identifier l'enregistrement plus rapidement, nous regrouperons deux colonnes ou plus pour obtenir la valeur unique et créerons un index à partir d'elles. Cette méthode est appelée index de clustering.
  • Les enregistrements présentant des caractéristiques similaires sont regroupés et des index sont créés pour ces groupes.

Exemple : supposons qu'une entreprise compte plusieurs employés dans chaque département. Supposons que nous utilisions un index de clustering, dans lequel tous les employés appartenant au même Dept_ID sont considérés au sein d'un seul cluster, et les pointeurs d'index pointent vers le cluster dans son ensemble. Ici, Dept_Id est une clé non unique.

Indexation du SGBD dans le SGBD

Le schéma précédent prête peu à confusion car un bloc de disque est partagé par des enregistrements appartenant à différents clusters. Si nous utilisons un bloc de disque séparé pour des clusters séparés, cela s'appelle une meilleure technique.

Indexation du SGBD dans le SGBD

Indice secondaire

Dans l'indexation éparse, à mesure que la taille de la table augmente, la taille du mappage augmente également. Ces mappages sont généralement conservés dans la mémoire principale afin que la récupération d'adresse soit plus rapide. Ensuite, la mémoire secondaire recherche les données réelles en fonction de l'adresse obtenue grâce au mappage. Si la taille du mappage augmente, la récupération de l'adresse elle-même devient plus lente. Dans ce cas, l’index clairsemé ne sera pas efficace. Pour surmonter ce problème, une indexation secondaire est introduite.

Dans l'indexation secondaire, pour réduire la taille du mappage, un autre niveau d'indexation est introduit. Dans cette méthode, la vaste plage des colonnes est sélectionnée initialement afin que la taille de mappage du premier niveau devienne petite. Ensuite, chaque plage est divisée en plages plus petites. Le mappage du premier niveau est stocké dans la mémoire principale, de sorte que la récupération d'adresse soit plus rapide. Le mappage du deuxième niveau et les données réelles sont stockés dans la mémoire secondaire (disque dur).

Indexation du SGBD dans le SGBD

Par exemple:

  • Si vous souhaitez trouver l'enregistrement du rôle 111 dans le diagramme, il recherchera l'entrée la plus élevée qui est inférieure ou égale à 111 dans l'index de premier niveau. Il obtiendra 100 à ce niveau.
  • Puis au deuxième niveau d'index, encore une fois, il fait max (111)<= 111 and gets 110. now using the address 110, it goes to data block starts searching each record till 111. < li>
  • C'est ainsi qu'une recherche est effectuée dans cette méthode. L'insertion, la mise à jour ou la suppression s'effectue également de la même manière.