L'organisation en B-tree constitue le fondement des index dans SQL Server, offrant un mécanisme puissant pour accélérer l'accès aux données. Les index structurent les informations de manière spécifique, ce qui est essentiel pour optimiser la réactivité des requêtes. Leur pertinence est particulièrement marquée sur les tables volumineuses, où ils permettent de localiser rapidement les lignes répondant à des critères précis. Au-delà de la simple recherche, les index peuvent également faciliter le tri, les jointures, les regroupements et le filtrage des ensembles de données.

Une structure B-tree est hiérarchique : la racine est le point de départ unique pour toute navigation. Le nombre de niveaux intermédiaires varie en fonction du volume de données de la table et de la taille des entrées d'index. Les nœuds de niveau le plus bas sont désignés comme les nœuds feuilles. Ces nœuds feuilles contiennent une ou plusieurs enregistrements associés aux valeurs de clé définies. Que ce soit pour un index clusterisé ou non-clusterisé, les nœuds feuilles sont ordonnés séquentiellement selon les valeurs de clé, ou selon une combinaison de clés pour les index composites.

1. Index Clusterisé

Dans le cas d'un index clusterisé, les nœuds feuilles englobent non seulement les clés d'index, mais aussi les pages de données complètes. Cela signifie que les données de la table sont intrinsèquement intégrées à l'index clusterisé. Un index clusterisé ordonne logiquement les données de la table en fonction de l'ordre de ses clés. Le choix de la clé clusterisée est donc fondamental, car une fois le niveau feuille atteint, les données réelles sont accessibles directement, et non via un simple pointeur (comme c'est le cas pour un index non-clusterisé non couvrant).

Un index clusterisé est identifié dans sys.partitions par un index_id = 1 pour chaque partition. Par défaut, il réside sur une seule partition. Si un index clusterisé est divisé en plusieurs partitions, chaque partition aura sa propre structure B-tree. Une table ne peut posséder qu'un seul index clusterisé, car les pages de données ne peuvent être triées physiquement que d'une seule manière. L'optimiseur de requêtes favorise souvent les index clusterisés, car ils offrent un accès direct aux données au niveau feuille et sont très efficaces pour les balayages de plages.

2. Index Non-Clusterisé

Un index non-clusterisé présente une structure B-tree similaire à celle d'un index clusterisé, mais il n'impacte pas l'ordre physique des lignes de données dans la table. Au niveau feuille, un index non-clusterisé contient uniquement les valeurs des clés d'index et un "signet" (bookmark). Ce signet indique à SQL Server où retrouver la ligne de données correspondante : il s'agit soit de la clé de l'index clusterisé (si la table en possède un), soit d'un identifiant de ligne (RID) pour une table organisée en tas (heap).

Puisque les nœuds feuilles des index non-clusterisés ne contiennent pas toutes les données, leur présence n'altère pas l'organisation des pages de données de la table. Cela permet de définir jusqu'à 999 index non-clusterisés sur une même table dans les versions récentes de SQL Server. Chaque index non-clusterisé est identifié par un index_id > 1 dans sys.partitions et réside par défaut sur une seule partition.

Impact des Index : Balayage versus Recherche

Pour illustrer l'importance pratique des index, considérons un scénario courant sur une table de grande taille, par exemple dbo.Articles, contenant plusieurs millions d'enregistrements. Nous chercherons à récupérer des informations sur un article en utilisant sa référence unique, CodeArticle. Comparons deux situations : l'absence d'un index pertinent menant à un balayage, et la présence d'un index bien conçu permettant une recherche directe.

1. Scénario avec Balayage d'Index (Absence d'Index pertinent)

Imaginons que nous exécutons la requête suivante pour trouver le nom d'un article, et qu'aucun index efficace n'est défini sur la colonne CodeArticle :

-- Recherche du nom d'un article par son code dans une table volumineuse
-- (supposons qu'aucun index non-clusterisé n'existe sur CodeArticle)
SELECT NomArticle FROM dbo.Articles WHERE CodeArticle = 'REF001XYZ';

Dans ce cas, le plan d'exécution affichera très probablement un "Clustered Index Scan" (balayage de l'index clusterisé) ou, si la table est un tas, un "Table Scan" (balayage de la table). Pour une table de 12 millions de lignes, cette opération impliquera la lecture de dizaines de milliers, voire de centaines de milliers de pages logiques, ce qui se traduit par un temps d'exécution élevé (plusieurs centaines de millisecondes ou même secondes). Un balayage implique que SQL Server doit parcourir l'intégralité des pages de données de la table pour identifier les lignes correspondantes.

Du point de vue de la concurrence, un balayage sur une table volumineuse entraîne l'acquisition de nombreux verrous d'intention partagés (IS locks) sur les pages lues. Bien que ces verrous soient de faible niveau, leur nombre élevé peut accroître le risque de blocage ou d'interblocage (deadlock) si d'autres processus tentent simultanément de modifier des données dans la même table, car les verrous IS sont incompatibles avec les verrous exclusifs (X).

2. Scénario avec Recherche d'Index (Présence d'un Index)

Créons maintenant un index non-clusterisé sur la colonne CodeArticle, puis exécutons la même requête de recherche :

-- Création d'un index non-clusterisé sur CodeArticle
CREATE NONCLUSTERED INDEX IX_Articles_CodeArticle ON dbo.Articles (CodeArticle);

-- Exécution de la même requête après l'ajout de l'index
SELECT CodeArticle FROM dbo.Articles WHERE CodeArticle = 'REF001XYZ';

Avec cet index en place, le plan d'exécution affichera une "Nonclustered Index Seek" (recherche d'index non-clusterisé). Cette opération est nettement plus rapide, se caractérisant par un nombre minime de lectures logiques (par exemple, seulement quelques pages lues) et un temps d'exécution presque instantané. L'index permet à SQL Server de naviguer directement vers les pages contenant la clé recherchée, évitant ainsi un balayage coûteux.

En termes de gestion des verrous, une recherche d'index réduit considérablement le nombre de verrous acquis. Seules les quelques pages spécifiquement pertinentes sont verrouillées, ce qui minimise les risques de contention et améliore significativement la concurrence d'accès à la table pour d'autres opérations, comme les modifications ou les suppressions.

Impact des B-trees sur l'Espace de Stockage

Bien que l'index clusterisé représente les données elles-mêmes, l'ajout de plusieurs index non-clusterisés sur une table implique la duplication des clés d'index et des pointeurs, ce qui consomme de l'espace de stockage additionnel. Il est donc crucial de planifier méticuleusement la création d'index non-clusterisés afin de maîtriser l'utilisation des ressources disque. Prenons l'exemple d'une table en environnement de production dotée d'un index clusterisé et de quatre index non-clusterisés.

Si l'index clusterisé (qui contient les données de base de la table) occupe 1 448 806 pages, les quatre index non-clusterisés combinés pourraient totaliser 2 180 034 pages. Dans ce cas précis, l'espace de stockage requis pour les index non-clusterisés est environ 1,5 fois supérieur à celui des données de base de la table. Cette proportion met en lumière l'importance d'évaluer le compromis entre l'optimisation des performances de requête et la consommation des ressources de stockage lors de la conception des index.