Tables organisées en index et index regroupés

Le parcours d'index seul exécute une requête SQL en utilisant seulement les données redondantes enregistrées dans l'index. Les données originales disponibles dans la table (heap) ne sont pas nécessaires. Si nous prenons ce concept au niveau supérieur et plaçons toutes les colonnes dans l'index, nous pourrions nous demander pourquoi nous avons besoin de la table.

De ce fait, certaines bases de données utilisent un index comme principal stockage de la table. La base de données Oracle appelle ce concept table organisée en index (IOT, pour « index-organized table »), d'autres bases de données utilisent le terme index regroupé (« clustered index » en anglais). Dans cette section, les deux termes sont utilisés pour mettre l'accent sur les caractéristiques de la table ou de l'index, suivant le besoin.

Ainsi, une table organisée en index est un index B-tree sans table (heap). Cela a deux avantages : on évite de perdre de l'espace disque et chaque accès à un index regroupé est automatiquement un parcours d'index seul. Ces deux avantages sont très prometteurs mais difficilement atteignables en pratique.

Les inconvénients des tables organisées en index deviennent apparents lors de la création d'un autre index sur la même table. De façon analogue à un index standard, un index secondaire fait référence aux données de la table originale, qui sont stockées dans l'index regroupé. Là, les données ne sont pas enregistrées statiquement comme dans une table mais peuvent être déplacées à tout moment pour maintenir l'ordre de l'index. Du coup, il n'est pas possible d'enregistrer l'emplacement physique des lignes dans la table organisée en index dans l'index secondaire. La base de données doit utiliser une clé logique à la place.

Le graphe suivant montre une recherche via un index pour trouver toutes les ventes du 23 mai 2012. En comparaison, nous allons tout d'abord regarder la Figure 5.2 qui montre le processus lors de l'utilisation d'une table standard. L'exécution implique deux étapes : l'opération INDEX RANGE SCAN et l'opération TABLE ACCESS BY INDEX ROWID.

Bien que l'accès à la table puisse devenir un goulet d'étranglement, cela reste limité à une opération de lecture par ligne car l'index dispose du ROWID comme pointeur direct vers la ligne de la table. La base de données peut immédiatement charger la ligne à partir de la table standard car l'index a sa position exacte. Néanmoins, le graphe change lors de l'utilisation de l'index secondaire sur une table organisée en index. Un index secondaire ne stocke pas de pointeurs physiques (ROWID) mais seulement les valeurs clés de l'index regroupé, fréquemment appelées clé de regroupement. Il s'agit souvent de la clé primaire de la table organisée en index.

Accéder à un index secondaire ne ramène pas un ROWID mais une clé logique pour rechercher la ligne dans l'index regroupé. Néanmoins, un seul accès n'est pas suffisant pour rechercher dans l'index regroupé. Cela nécessite un parcours complet de l'arbre. Autrement dit, un accès à la table via un index secondaire fait une recherche dans deux index : tout d'abord dans l'index secondaire (INDEX RANGE SCAN), puis dans l'index regroupé pour chaque ligne trouvée dans l'index secondaire (INDEX UNIQUE SCAN).

La Figure 5.3 rend évident le fait que le B-tree de l'index regroupé se tient entre l'index secondaire et les données de la table.

Accéder à une table organisée en index via un index secondaire est très inefficace, et cela peut être empêché de la même façon qu'on empêche un accès à la table sur une table standard : en utilisant un parcours d'index seul, qui est mieux décrit dans ce cas comme un « parcours d'index secon­daire seul ». L'avantage au niveau des performances d'un parcours d'index seul est encore plus important car il empêche non seulement un accès seul mais aussi une opération INDEX UNIQUE SCAN entière.

En utilisant cet exemple, nous pouvons aussi voir que les bases de données exploitent toutes les redondances qu'elles ont. Gardez en tête qu'un index secondaire enregistre la clé de regroupement pour chaque entrée d'index. En conséquence, nous pouvons demander la clé de regroupement à partir d'un index secondaire sans accéder à la table organisée en index :

SELECT id_vente
  FROM ventes_iot
 WHERE date_vente = ?;

La table VENTES_IOT est une table organisée en index qui utilise ID_VENTE comme clé de regroupement. Bien que l'index VENTE_IOT_DATE soit seulement sur la colonne DATE_VENTE, il a toujours une copie de la clé de regroupement ID_VENTE pour qu'il puisse répondre à la requête en utilisant seulement l'index secondaire.

Lors de la sélection des autres colonnes, la base de données doit exécuter une opération INDEX UNIQUE SCAN sur l'index regroupé pour chaque ligne :

SELECT valeur_eur
  FROM ventes_iot
 WHERE date_vente = ?;

Les tables organisées en index et les index regroupés ne sont donc pas si utiles. Les améliorations de performance sur l'index regroupé sont facilement perdues lors de l'utilisation d'un index secondaire. La clé de regroupement est généralement plus longue qu'un ROWID, du coup les index secondaires sont plus gros qu'une table standard, ce qui élimine souvent le gain réalisé par l'omission de la table standard. La force des tables organisées en index et des index regroupés est souvent limitée aux tables qui n'ont pas besoin d'index secondaire. Les tables standard ont l'intérêt de fournir des données qui ne sont pas déplacées, ce qui facilite leur référencement.

Le support des bases de données pour les tables organisées en index et pour les index regroupés est très différent. L'aperçu suivant explique les spécificités les plus importantes.