SGBD - Indexation

Nous savons que les données sont stockées sous forme d'enregistrements. Chaque enregistrement a un champ clé, ce qui l'aide à être reconnu de manière unique.

L'indexation est une technique de structure de données permettant d'extraire efficacement des enregistrements à partir des fichiers de base de données en fonction de certains attributs sur lesquels l'indexation a été effectuée. L'indexation dans les systèmes de bases de données est similaire à ce que nous voyons dans les livres.

L'indexation est définie en fonction de ses attributs d'indexation. L'indexation peut être des types suivants -

  • Primary Index- L'index primaire est défini sur un fichier de données ordonné. Le fichier de données est commandé sur unkey field. Le champ clé est généralement la clé primaire de la relation.

  • Secondary Index - L'index secondaire peut être généré à partir d'un champ qui est une clé candidate et a une valeur unique dans chaque enregistrement, ou une non-clé avec des valeurs en double.

  • Clustering Index- L'index de clustering est défini sur un fichier de données ordonné. Le fichier de données est ordonné sur un champ non clé.

L'indexation ordonnée est de deux types -

  • Indice dense
  • Index clairsemé

Indice dense

Dans un index dense, il existe un enregistrement d'index pour chaque valeur de clé de recherche dans la base de données. Cela accélère la recherche mais nécessite plus d'espace pour stocker les enregistrements d'index lui-même. Les enregistrements d'index contiennent une valeur de clé de recherche et un pointeur vers l'enregistrement réel sur le disque.

Index clairsemé

Dans un index fragmenté, les enregistrements d'index ne sont pas créés pour chaque clé de recherche. Un enregistrement d'index contient ici une clé de recherche et un pointeur réel vers les données sur le disque. Pour rechercher un enregistrement, nous procédons d'abord par enregistrement d'index et atteignons l'emplacement réel des données. Si les données que nous recherchons ne sont pas là où nous atteignons directement en suivant l'index, le système lance une recherche séquentielle jusqu'à ce que les données souhaitées soient trouvées.

Index à plusieurs niveaux

Les enregistrements d'index comprennent des valeurs de clé de recherche et des pointeurs de données. L'index à plusieurs niveaux est stocké sur le disque avec les fichiers de base de données réels. Au fur et à mesure que la taille de la base de données augmente, la taille des index augmente également. Il existe un besoin immense de conserver les enregistrements d'index dans la mémoire principale afin d'accélérer les opérations de recherche. Si un index à un seul niveau est utilisé, un index de grande taille ne peut pas être conservé en mémoire, ce qui entraîne plusieurs accès disque.

L'index à plusieurs niveaux aide à décomposer l'index en plusieurs indices plus petits afin de rendre le niveau le plus externe si petit qu'il peut être enregistré dans un seul bloc de disque, qui peut facilement être logé n'importe où dans la mémoire principale.

Arbre B +

L' arbre AB + est un arbre de recherche binaire équilibré qui suit un format d'index à plusieurs niveaux. Les nœuds feuilles d'un arbre B + désignent des pointeurs de données réels. L' arbre B + garantit que tous les nœuds feuilles restent à la même hauteur, donc équilibrés. De plus, les nœuds feuilles sont liés à l'aide d'une liste de liens; par conséquent, un arbre B + peut prendre en charge l'accès aléatoire ainsi que l'accès séquentiel.

Structure de l' arbre B +

Chaque nœud feuille est à égale distance du nœud racine. L' arbre AB + est de l'ordren où nest fixé pour chaque arbre B + .

Internal nodes -

  • Les nœuds internes (non-feuilles) contiennent au moins ⌈n / 2⌉ pointeurs, à l'exception du nœud racine.
  • Tout au plus, un nœud interne peut contenir n pointeurs.

Leaf nodes -

  • Les nœuds feuilles contiennent au moins ⌈n / 2⌉ pointeurs d'enregistrement et des valeurs de clé ⌈n / 2⌉.
  • Tout au plus, un nœud feuille peut contenir n enregistrer des pointeurs et n valeurs clés.
  • Chaque nœud feuille contient un pointeur de bloc P pour pointer vers le nœud feuille suivant et forme une liste chaînée.

Insertion d'arbre B +

  • Les arbres B + sont remplis par le bas et chaque entrée se fait au niveau du nœud feuille.

  • Si un nœud feuille déborde -

    • Divisez le nœud en deux parties.

    • Partition à i = ⌊(m+1)/2⌋.

    • Première i les entrées sont stockées dans un nœud.

    • Le reste des entrées (à partir de i + 1) est déplacé vers un nouveau nœud.

    • ith la clé est dupliquée au niveau du parent de la feuille.

  • Si un nœud non-feuille déborde -

    • Divisez le nœud en deux parties.

    • Partitionner le nœud à i = ⌈(m+1)/2⌉.

    • Entrées jusqu'à i sont conservés dans un nœud.

    • Le reste des entrées est déplacé vers un nouveau nœud.

Suppression d'arbre B +

  • Les entrées de l'arborescence B + sont supprimées aux nœuds feuilles.

  • L'entrée cible est recherchée et supprimée.

    • S'il s'agit d'un nœud interne, supprimez et remplacez par l'entrée de la position gauche.

  • Après suppression, le sous-débit est testé,

    • En cas de sous-dépassement, distribuez les entrées des nœuds qui lui sont laissés.

  • Si la distribution n'est pas possible de gauche, alors

    • Distribuez à partir des nœuds directement.

  • Si la distribution n'est pas possible de gauche ou de droite, alors

    • Fusionner le nœud avec la gauche et la droite.