Comment l'index combiné est-il implémenté dans SQL Server

Question

Je comprends comment fonctionne une colonne indexée unique dans SQL Server et comment elle est implémentée à l'aide d'arborescences équilibrées.Il y a beaucoup de vidéos intéressantes sur YouTube sur ce sujet.Cependant je ne comprends pas comment cela fonctionne si l'index est basé sur plusieurs colonnes.Par exemple:

CREATE NONCLUSTERED INDEX idxItemsCatState
ON Items (Category,OfferState)
INCLUDE ([Id],[Ranking])

Et comment cela peut accélérer les requêtes comme

SELECT ID, Ranking FROM Items where Category = 1 AND OfferState < 3

Il est toujours implémenté sous le nom de B-Tree ?Comment peut-il évaluer la combinaison de valeurs ?Quelles sont les restrictions pour une telle fonctionnalité ?

Answer 1

Pour stocker des lignes dans un arbre B et effectuer une recherche, il suffit d'un ordre dans lequel les lignes doivent être triées.Tout comme tu peux faire le tri (Category), vous pouvez également trier sur le tuple (Category, OfferState).Dans ce dernier cas, les lignes sont d'abord triées par Category puis toutes les égalités sont rompues en triant par OfferState.

L'index résultant utilisera la même structure b-tree, mais la valeur de chaque entrée dans le b-tree sera un (Category, OfferState) tuple.

Et comment cela peut accélérer les requêtes comme...

Pour votre requête, SQL Server peut effectuer une recherche de la manière suivante :

• Rechercher la première ligne qui correspond Category = 1.Cela peut être fait en utilisant la même recherche d'arbre b que celle que vous connaissez, SQL Server n'ayant besoin que d'utiliser le Category partie de chacun (Category, OfferState) tuple.
• Commencez à lire les lignes et continuez jusqu'à une ligne avec OfferState >= 3 est trouvé

De cette manière, SQL Server pourra rechercher directement le début de la plage de lignes nécessaires, lire ces lignes et s'arrêter à la fin de la plage de lignes.Notez que vous pouvez voir comment fonctionne cette recherche en regardant le Seek Predicate propriété du Index Seek opérateur dans votre plan de requête.

Plus généralement, un index multi-colonnes sur plusieurs colonnes (a, b, c, d, ...) peut prendre en charge une recherche sur n'importe quel sous-ensemble principal de colonnes, tel que (a) ou (a, b, c), lorsque vous recherchez l'égalité (en utilisant =).

Si vous recherchez une plage (par exemple, b < 3), SQL Server ne peut plus rechercher les colonnes qui se trouvent plus tard dans l'index.Dans un tel cas, il faudrait effectuer une recherche distincte pour chaque valeur distincte de b, ce qui n'est pas pris en charge (sauf dans un cas plus spécifique dont vous n'aurez probablement pas à vous soucier :sur les partitions d’une table partitionnée).

Answer 2

Les index traditionnels sont implémentés sous forme d'arbres B, qu'il s'agisse d'une clé unique ou multicoline.

et comment il peut accélérer la requête comme

SELECT ID, Ranking FROM Items where Category = 1 AND OfferState < 3

L'ordre des clés d'index composites est significatif pour l'optimisation de la requête.Spécifiez la ou les colonnes utilisées dans les prédicats d'égalité d'abord (par ordre de sélectivité), suivie de la colonne (s) utilisée (s) utilisée (s) avec des prédicats d'inégalité.Cela facilitera que toucher uniquement ces lignes correspondant à la condition égale, puis accédez aux lignes dans la plage spécifiée.Donc, pour cette requête, l'ordre de colonne dans l'index devrait être une catégorie et des acomptes de biens-au-temps plutôt que vice-versa.

Answer 3

Logiquement, les colonnes individuelles sont regroupées dans un tuple (Category, OfferState).Ces tuples sont les clés d'index et l'algorithme b-tree fonctionne sans modification.

Les arbres B n'ont besoin d'aucune sorte de "condition".Ils fonctionnent sur n'importe quel domaine de valeur pour lequel un ordre total est défini.La seule opération jamais effectuée au niveau de la structure des données consiste à comparer deux clés.SQL Server utilise en outre deux opérations supplémentaires :sérialisation en octets et désérialisation à partir d'octets.