Méthodes d'indexation et d'accès

Les index et les méthodes d'accès sont les structures de données auxiliaires — principalement les arbres B+ et les index de hachage — qui permettent à une base de données de localiser les tuples correspondants sans balayer une table entière, offrant ainsi les chemins d'accès rapides sur lesquels l'optimiseur s'appuie.

Definition

Un index est une structure de données auxiliaire sur un ou plusieurs attributs d'une relation qui mappe les valeurs de clé aux emplacements des tuples correspondants, permettant une récupération en temps sous-linéaire par rapport à la taille de la table ; une méthode d'accès est le mécanisme qu'une requête utilise pour lire les données, tel qu'un balayage complet ou un balayage d'index.

Scope

Ce sujet couvre les structures et les concepts sous-jacents aux chemins d'accès aux données : la distinction entre les index clusterisés et non clusterisés, primaires et secondaires ; l'arbre B+ en tant qu'index ordonné essentiel supportant la recherche d'égalité et de plage ; les index basés sur le hachage pour la recherche d'égalité ; et le rôle des index dans la sélection, la jointure et l'évitement du tri. Il aborde la manière dont le choix de l'index affecte le coût des requêtes et le surcoût des mises à jour. Il exclut la sélection globale du plan par l'optimiseur basé sur les coûts, qui est un sujet distinct.

Core questions

• Comment un arbre B+ prend-il en charge efficacement les requêtes d'égalité et de plage ?
• Quelle est la différence entre les index clusterisés et non clusterisés, primaires et secondaires ?
• Quand un index de hachage est-il préférable à un index arborescent ?
• Comment les index accélèrent-ils les sélections, les jointures et la récupération ordonnée ?
• Quel est le coût de la maintenance des index lors des insertions, des mises à jour et des suppressions ?

Key concepts

• Index arbre B+
• Index de hachage
• Index clusterisé versus non clusterisé
• Index primaires et secondaires
• Index denses et creux
• Recherche par plage et par égalité
• Hachage extensible et linéaire
• Coût de maintenance des index

Key theories

Index arbre B+

L'arbre B+ est un arbre de recherche équilibré à facteur de branchement élevé qui stocke les clés dans un ordre trié avec toutes les références de données dans les feuilles ; il prend en charge les requêtes d'égalité et de plage ainsi que les balayages ordonnés en E/S logarithmiques et reste équilibré lors des insertions et des suppressions.

Index clusterisés versus non clusterisés

Un index clusterisé maintient les lignes de la table physiquement ordonnées par la clé d'index, rendant les balayages de plage très efficaces, tandis qu'un index non clusterisé (secondaire) pointe vers un fichier non ordonné, de sorte que la récupération de nombreuses lignes correspondantes peut coûter une E/S par ligne.

Index de hachage

Les index basés sur le hachage mappent les clés à des compartiments pour des recherches d'égalité en temps constant attendu, mais ne prennent pas en charge les requêtes de plage ; les schémas dynamiques tels que le hachage extensible et linéaire leur permettent de croître harmonieusement avec les données.

Clinical relevance

L'indexation est le levier pratique le plus courant pour la performance des bases de données : le choix des bons index peut transformer les balayages complets de table en recherches en millisecondes pour les requêtes transactionnelles et analytiques, tandis qu'une sur-indexation ralentit les mises à jour ; la conception des index est donc une décision récurrente dans l'exploitation des systèmes réels.

History

Bayer et McCreight ont introduit l'arbre B en 1972 pour maintenir de grands index ordonnés sur disque ; la variante arbre B+, qui conserve toutes les données dans les feuilles, est devenue l'index de base de données standard, comme l'a examiné Comer dans son ouvrage de 1979 'Ubiquitous B-tree.' Les méthodes d'accès basées sur le hachage et les schémas de hachage dynamique se sont développés en parallèle, et ces deux familles restent au cœur de chaque moteur relationnel.

Key figures

• Rudolf Bayer
• Edward McCreight
• Douglas Comer

Seminal works

• bayer1972
• comer1979
• ramakrishnan2003

Frequently asked questions

Pourquoi les arbres B+ sont-ils utilisés à la place des arbres binaires de recherche dans les bases de données ?

Les bases de données stockent les données sur disque, où le coût est dominé par le nombre de lectures de pages. Les arbres B+ ont un facteur de branchement élevé, de sorte que chaque nœud remplit une page disque et l'arbre est très peu profond, ne nécessitant que quelques opérations d'E/S pour atteindre n'importe quel enregistrement. Un arbre binaire serait beaucoup plus profond et entraînerait beaucoup plus d'accès disque.

Quand devrais-je utiliser un index de hachage plutôt qu'un arbre B+ ?

Utilisez un index de hachage lorsque vous n'avez besoin que de recherches d'égalité (par exemple, trouver la ligne avec un identifiant donné) et que vous souhaitez un accès en temps constant attendu. Utilisez un arbre B+ lorsque vous avez également besoin de requêtes de plage, de balayages ordonnés ou de correspondances de préfixe, car les index de hachage ne préservent pas l'ordre des clés et ne peuvent pas répondre efficacement aux conditions de plage.