Vue d'ensemble de l'indexation spatiale

SQL Server 2008 et versions ultérieures prennent en charge les données spatiales. Cela inclut la prise en charge d'un type de données spatial planaire, geometry, qui prend en charge des données géométriques (points, lignes et polygones) dans un système de coordonnées Euclidien. Le type de données geography représente des objets géographiques sur une zone sur la surface de la Terre. Un index spatial sur une colonne géographique mappe les données géographiques à un espace non Euclidien en deux dimensions.

Un index spatial est défini sur une colonne de table qui contient des données spatiales (une colonne spatiale). Chaque index spatial fait référence à un espace fini. Par exemple, un index pour une colonne geometry fait référence à une zone rectangulaire spécifiée par l'utilisateur sur un plan.

Décomposition de l'espace indexé en une hiérarchie de grille

Dans SQL Server 2008, les index spatiaux sont construits à l'aide d'arbres B (B-trees), ce qui signifie que les index doivent représenter les données spatiales bidimensionnelles dans l'ordre linéaire d'arbres B. Par conséquent, SQL Server 2008 implémente une décomposition uniforme hiérarchique de l'espace avant de lire des données dans un index spatial. Le processus de création d'index décompose l'espace en une hiérarchie de grille à quatre niveaux. Ces niveaux portent les noms de niveau 1 (le niveau supérieur), niveau 2, niveau 3 et niveau 4.

Chaque niveau consécutif décompose davantage le niveau supérieur ; chaque cellule de niveau supérieur contient donc une grille complète au niveau suivant. Sur un niveau donné, toutes les grilles ont le même nombre de cellules le long des deux axes (par exemple, 4x4 ou 8x8) et les cellules sont toutes d'une seule taille.

L'illustration suivante montre la décomposition pour la cellule supérieure droite à chaque niveau de la hiérarchie de grille en une grille 4x4. En réalité, toutes les cellules sont décomposées de cette manière. Par exemple, la décomposition d'un espace en quatre niveaux de grilles 4x4 produit en fait un total de 65 536 cellules de niveau quatre.

Notes

La décomposition d'espace pour un index spatial est indépendante de l'unité de mesure utilisée par les données de l'application.

Les cellules d'une hiérarchie de grille sont numérotées de façon linéaire en utilisant une variante de la courbe de remplissage d'espace de Hilbert. Toutefois, à des fins d'illustration, cette discussion utilise une numérotation de ligne simple plutôt que la numérotation réellement générée par la courbe Hilbert. Dans l'illustration suivante, plusieurs polygones qui représentent des bâtiments et des lignes qui représentent des rues ont déjà été placés dans une grille 4x4 de niveau 1. Les cellules de niveau 1 sont numérotées de 1 à 16, en commençant par la cellule supérieure gauche.

Densité de grille

Le nombre de cellules le long des axes d'une grille détermine sa densité : plus le nombre est élevé, plus la grille est dense. Par exemple, une grille 8x8 (qui produit 64 cellules) est plus dense qu'une grille 4x4 (qui produit 16 cellules). La densité de grille est définie sur la base de chaque niveau.

L'instruction Transact-SQLCREATE SPATIAL INDEX prend en charge une clause GRIDS qui vous permet de spécifier des densités de grille différentes à des niveaux différents. La densité de grille pour un niveau donné est spécifiée à l'aide de l'un des mots clés suivants :

Mot clé	Configuration de grille	Nombre de cellules
LOW	4X4	16
MEDIUM	8X8	64
HIGH	16X16	256

La valeur par défaut est MEDIUM sur tous les niveaux.

Vous pouvez contrôler le processus de décomposition en spécifiant des densités de grille autres que les densités par défaut. Par exemple, différentes densités de grille sur différents niveaux peuvent être utiles pour le réglage fin d'un index en fonction de la taille de l'espace indexé et des objets contenus dans la colonne spatiale.

Notes

Les densités de grille d'un index spatial sont visibles dans les colonnes level_1_grid, level_2_grid, level_3_grid et level_4_grid de l'affichage catalogue sys.spatial_index_tessellations.

Pavage

Après la décomposition d'un espace indexé en une hiérarchie de grille, l'index spatial lit les données de la colonne spatiale, ligne par ligne. Après avoir lu les données pour un objet spatial (ou une instance), l'index spatial effectue un processus de pavage pour cet objet. Le processus de pavage place l'objet dans la hiérarchie de grille en associant l'objet à un ensemble de cellules de grille qu'il touche (cellules touchées). En partant du niveau 1 de la hiérarchie de grille, le processus de pavage continue dans le sens de la largeur à travers le niveau. Potentiellement, le processus peut se poursuivre à travers les quatre niveaux, un niveau à la fois.

La sortie du processus de pavage est un jeu de cellules touchées enregistrées dans l'index spatial pour l'objet. En faisant référence à ces cellules enregistrées, l'index spatial peut localiser l'objet dans l'espace relativement à d'autres objets dans la colonne spatiale qui sont également stockés dans l'index.

Règles de pavage

Pour limiter le nombre de cellules touchées enregistrées pour un objet, le processus de pavage applique plusieurs règles de pavage. Ces règles déterminent la profondeur du processus de pavage et lesquelles des cellules touchées sont enregistrées dans l'index.

Ces règles sont les suivantes :

• La règle de couverture

  Si l'objet couvre complètement une cellule, cette cellule est dite couverte par l'objet. Une cellule couverte est comptée et n'est pas pavée. Cette règle s'applique à tous les niveaux de la hiérarchie de grille. La règle de couverture simplifie le processus de pavage et réduit la quantité de données enregistrées par un index spatial.

• La règle de cellules par objet

  Cette règle applique la limite de cellules par objet, qui détermine le nombre maximal de cellules qui peuvent être comptées pour chaque objet, hormis au niveau 1. Aux niveaux inférieurs, la règle de cellules par objet contrôle la quantité d'informations qui peuvent être enregistrées à propos de l'objet.

• La règle de cellule la plus profonde

  La règle de cellule la plus profonde génère la meilleure approximation d'un objet en enregistrant uniquement les seules cellules les plus profondes qui ont été pavées pour l'objet. Les cellules parentes ne contribuent pas au nombre de cellules par objet et elles ne sont pas enregistrées dans l'index.

Ces règles de pavage sont appliquées de manière récursive sur chaque niveau de grille. Le reste de cette section décrit les règles de pavage en détail.

Règle de couverture

Si un objet couvre complètement une cellule, cette cellule est dite couverte par l'objet. Par exemple, dans l'illustration suivante, l'une des cellules de second niveau, 15.11, est complètement couverte par la partie centrale d'un octogone.

Une cellule couverte est comptée et enregistrée dans l'index, et la cellule n'est pas pavée davantage.

Règle de cellules par objet

L'étendue de pavage de chaque objet dépend principalement de la limite de cellules par objet de l'index spatial. Cette limite définit la quantité maximale de cellules que le pavage peut compter par objet. Notez toutefois que la règle de cellules par objet n'est pas appliquée au niveau 1 ; il est par conséquent possible de dépasser cette limite. Si la quantité de cellules au niveau 1 atteint ou dépasse la limite de cellules par objet, aucun pavage supplémentaire n'a lieu aux niveaux inférieurs.

Tant que la quantité est inférieure à la limite de cellules par objet, le processus de pavage continue. En commençant par la cellule touchée la plus basse (par exemple, la cellule 15.6 dans l'illustration précédente), le processus teste chaque cellule afin d'évaluer s'il faut la compter ou la paver. Si le pavage d'une cellule entraîne un dépassement de la limite de cellules par objet, la cellule est comptée et non pavée. Autrement, la cellule est pavée et les cellules de niveau inférieur touchées par l'objet sont comptées. Le processus de pavage se poursuit de cette manière, dans le sens de la largeur, à travers le niveau. Ce processus est répété de façon récursive pour les grilles de niveau inférieur des cellules pavées jusqu'à ce que la limite soit atteinte ou qu'il n'y ait plus de cellules à compter.

Par exemple, considérez l'illustration précédente, qui montre un octogone qui s'adapte parfaitement à la cellule 15 de la grille de niveau 1. Dans l'illustration, la cellule 15 a été pavée, l'octogone ayant été disséqué en neuf cellules de niveau 2. Cette illustration suppose que la limite de cellules par objet est supérieure ou égale à 9. Si la limite de cellules par objet était inférieure ou égale à 8, la cellule 15 ne serait pas pavée et seule cette cellule 15 serait comptée pour l'objet.

Par défaut, la limite de cellules par objet est de 16, ce qui constitue un compromis satisfaisant entre l'espace et la précision pour la plupart des index spatiaux. Toutefois, l'instruction Transact-SQLCREATE SPATIAL INDEX prend en charge une clause CELLS_PER_OBJECT**=**n qui vous permet de spécifier une limite de cellules par objet comprise entre 1 et 8192 compris.

Notes

Le paramètre cells_per_object d'un index spatial est visible dans l'affichage catalogue sys.spatial_index_tessellations.

Règle de cellule la plus profonde

La règle de cellule la plus profonde exploite le fait que chaque cellule de niveau inférieur appartient à la cellule située au-dessus d'elle : une cellule de niveau 4 appartient à une cellule de niveau 3, une cellule de niveau 3 appartient à une cellule de niveau 2 et une cellule de niveau 2 appartient à une cellule de niveau 1. Par exemple, un objet qui appartient à la cellule 1.1.1.1 appartient également à la cellule 1.1.1, à la cellule 1.1 et à la cellule 1. La connaissance de telles relations de hiérarchie de cellule est intégrée au processeur de requêtes. Par conséquent, seules les cellules les plus profondes doivent être enregistrées dans l'index, ce qui réduit la quantité d'informations que l'index doit stocker.

Dans l'illustration suivante, un polygone en losange relativement petit est pavé. L'index utilise la limite de cellules par objet par défaut de 16, qui n'est pas atteinte pour ce petit objet. Par conséquent, le pavage continue jusqu'au niveau 4. Le polygone réside dans les cellules suivantes du niveau 1 au niveau 3 : 4, 4.4, 4.4.10 et 4.4.14. 4.4.10.13-15 et 4.4.14.1-3, 4.4.14.5-7 et 4.4.14.9-11.

Schémas de pavage

Le comportement d'un index spatial dépend en partie de son schéma de pavage. Le schéma de pavage est spécifique au type de données. Dans SQL Server 2008, les index spatiaux prennent en charge deux schémas de pavage :

• Le pavage de grille géométrique, qui est le schéma pour le type de données geometry.

• Le pavage de grille géographique, qui s'applique aux colonnes du type de données geography.

Notes

Le paramètre tessellation_scheme d'un index spatial est visible dans l'affichage catalogue sys.spatial_index_tessellations.

Schéma de pavage de grille géométrique

Le pavage de grille géométrique est le schéma de pavage par défaut pour le type de données geometry, et dans SQL Server 2008 il s'agit du seul schéma de pavage de ce genre. Cette section traite des aspects du pavage de grille géométrique qui sont pertinents à l'utilisation d'index spatiaux : méthodes prises en charge et zones englobantes.

Notes

Vous pouvez spécifier explicitement ce schéma de pavage en utilisant la clause USING GEOMETRY_GRID de l'instruction Transact-SQLCREATE SPATIAL INDEX.

Méthodes de géométrie prises en charge

Un index spatial a pour fonction de réduire le coût de l'application de méthodes basées sur des ensembles à une colonne spatiale en agissant comme un filtre sur les objets. Le type de données geometry fournit des méthodes intégrées pour construire des instances géométriques qui décrivent des objets géométriques et pour utiliser ces instances. Sous certaines conditions, les index spatiaux prennent en charge plusieurs méthodes de géométrie basées sur les ensembles, telles que STIntersects() et STTouches().

Pour plus d'informations sur la prise en charge fournie par les index spatiaux pour les méthodes de géométrie, consultez Méthodes géométriques prises en charge par les index spatiaux.

La zone englobante

Les données géométriques occupent un plan qui peut être infini. Dans SQL Server 2008, toutefois, un index spatial requiert un espace fini. Pour établir un espace fini pour la décomposition, le schéma de pavage de grille géométrique requiert une zone englobante rectangulaire. La zone englobante est définie par quatre coordonnées, (x-min,y-min) et (x-max,y-max), qui sont stockées comme propriétés de l'index spatial. Ces coordonnées représentent les éléments suivants :

• x-min est la coordonnée x de l'angle inférieur gauche du cadre englobant.

• y-min est la coordonnée y de l'angle inférieur gauche.

• x-max est la coordonnée x de l'angle supérieur droit.

• y-max est la coordonnée y de l'angle supérieur droit.

Notes

Ces coordonnées sont spécifiées par la clause BOUNDING_BOX de l'instruction Transact-SQLCREATE SPATIAL INDEX.

Les coordonnées (x-min,y-min) et (x-max,y-max) déterminent la position et les dimensions de la zone englobante. L'espace en dehors de la zone englobante est traité comme une cellule unique affectée du numéro 0.

L'index spatial décompose l'espace à l'intérieur de la zone englobante. La grille de niveau 1 de la hiérarchie de grille remplit la zone englobante. Pour placer un objet géométrique dans la hiérarchie de grille, l'index spatial compare les coordonnées de l'objet à celles de la zone englobante.

L'illustration suivante montre les points définis par les coordonnées (x-min,y-min) et (x-max,y-max) de la zone englobante. Le niveau supérieur de la hiérarchie de grille est illustré comme une grille 4x4. À des fins d'illustration, les niveaux inférieurs sont omis. L'espace en dehors de la zone englobante est indiqué par un zéro (0). Notez que l'objet 'A' s'étend en partie au-delà de la zone et que l'objet 'B' se trouve complètement à l'extérieur de la zone dans la cellule 0.

Une zone englobante correspond à une partie des données spatiales d'une application. Le fait que la zone englobante de l'index contienne toutes les données stockées dans la colonne spatiale ou uniquement une partie d'entre elles dépend de l'application. Seules les opérations calculées sur des objets qui sont entièrement à l'intérieur de la zone englobante tirent parti de l'index spatial. Par conséquent, pour profiter au plus d'un index spatial sur une colonne geometry, vous devez spécifier une zone englobante qui contient tous les objets ou la plupart d'entre eux.

Notes

Les densités de grille d'un index spatial sont visibles dans les colonnes bounding_box_xmin, bounding_box_ymin, bounding_box_xmax et bounding_box_ymax de l'affichage catalogue sys.spatial_index_tessellations.

Le schéma de pavage de grille géographique

Ce schéma de pavage s'applique uniquement à une colonne geography. Cette section résume les méthodes qui sont prises en charge par le pavage de grille géographique et discute de la manière dont l'espace géodésique est projeté sur un plan, qui est ensuite décomposé en une hiérarchie de grille.

Notes

Vous pouvez spécifier explicitement ce schéma de pavage en utilisant la clause USING GEOGRAPHY_GRID de l'instruction Transact-SQLCREATE SPATIAL INDEX.

Méthodes de géographie prises en charge

Le type de données geography fournit des méthodes intégrées pour construire et manipuler des instances de geography qui décrivent des objets géographiques. Sous certaines conditions, les index spatiaux prennent en charge les méthodes de géographie basées sur les ensembles suivantes : STIntersects()STEquals() et STDistance(). Un index spatial sur une colonne de type de données geography filtre les objets et réduit le coût, en termes de performances et de requêtes, de l'application de ces méthodes aux données spatiales.

Pour plus d'informations sur la prise en charge fournie par les index spatiaux pour les méthodes de géographie, consultez Méthodes géographiques prises en charge par les index spatiaux.

Projection de l'espace géodésique sur un plan

Les calculs sur les instances (objets) geography traitent l'espace qui contient les objets comme une ellipsoïde géodésique. Pour décomposer cet espace, le schéma de pavage de grille géographique divise la surface de l'ellipsoïde en ses hémisphères supérieur et inférieur puis effectue les étapes suivantes :

1. Projection de chaque hémisphère sur les facettes d'une pyramide quadrilatère.

2. Aplatissement des deux pyramides.

3. Jointure des pyramides aplaties pour former un plan non Euclidien.

L'illustration suivante montre une vue schématique du processus de décomposition en trois étapes. Dans les pyramides, les traits pointillés représentent les limites des quatre facettes de chaque pyramide. Les étapes 1 et 2 illustrent l'ellipsoïde géodésique, avec une ligne horizontale verte pour représenter la ligne de longitude équatoriale et une série de lignes verticales vertes pour représenter plusieurs lignes de latitude. L'étape 1 illustre la projection des pyramides sur les deux hémisphères. L'étape 2 illustre l'aplatissement des pyramides. L'étape 3 illustre les pyramides aplaties, après qu'elles ont été combinées de façon à former un plan, avec plusieurs lignes de longitude projetées. Remarquez que ces lignes projetées sont tendues et que leur longueur varie en fonction de l'emplacement où elles sont sur les pyramides.

Une fois l'espace projeté sur le plan, celui-ci est décomposé en une hiérarchie de grille à quatre niveaux. Différents niveaux peuvent utiliser différentes densités de grille. L'illustration suivante montre le plan après qu'il a été décomposé en une grille 4x4 de niveau 1. À des fins d'illustration, les niveaux inférieurs de la hiérarchie de grille sont omis. En réalité, le plan est décomposé entièrement en une hiérarchie de grille à quatre niveaux. Une fois le processus de décomposition terminé, les données géographiques sont lues, ligne par ligne, à partir de la colonne géographique et le processus de pavage est effectué pour chaque objet l'un après l'autre.

Prise en charge d'index spatial

Un index spatial peut être créé uniquement sur une colonne spatiale. Vous pouvez créer des index spatiaux sur toute colonne spatiale dans une table qui prend en charge les index spatiaux et vous pouvez créer plusieurs index spatiaux sur une colonne spatiale donnée. Pour plus d'informations sur les restrictions applicables aux index spatiaux, consultez Restrictions sur les index spatiaux.

Voir aussi

Concepts

Création, modification et suppression d'index spatiaux

Types de données spatiales

Autres ressources

Utilisation d'index spatiaux (moteur de base de données)