SpatiaLite Cookbook

	Recette #10: *Le fabuleux index spatial RTree**
Février 2011

Table des matières

Un Index Spatial est plus ou moins identique à un Index normal: i.e. le rôle de tout index est de permettre un accès très rapide à une sélection d'éléments parmi un grand nombre de données.

Prenons l'exemple d'un très gros livre: rechercher une donnée précise en lisant le livre en entier est pénible et très coûteux en temps.
Mais vous pouvez aussi vous référer à l'Index du livre, qui vous guidera vers les pages appropriées.

L'index d'une BDD joue exactement le même rôle.
Cependant, chercher des géométries particulières au sein d'un ensemble plus large diffère grandement d'une recherche de nombre ou de texte: c'est la le but même d'un INDEX SPATIAL

Il existe plusieurs algorithmes d'INDEX SPATIAL.
Dans SQLite, l'index spatial est basé sur l'algorithme R*Tree.

En simplifiant, un R*Tree défini une structure de type arborée, basée sur des rectangles (le R de R*Tree signifie Rectangle).

Toute géométrie peut être représentée comme un rectangle, peut importe sa forme originale: on peut utiliser le MBR (Minimum Bounding Rectangle) ie le rectangle minimum englobant la géométrie.
Peut être le terme BBOX (Bounding Box) vous est-il plus familier: ce sont des synonymes.

Il est facile de comprendre comment R*Tree fonctionne:

La requête spatiale définit un cadre de recherche arbitraire (qui s'avère être un rectangle également)
le R*Tree est rapidement scanné afin d'identifier l'index de tous les rectangles intersectant ce cadre
au final, toute géométrie qui se trouve dans ce cadre de recherche va être identifié.

Appliquons cela au problème de l'aiguille dans la botte de foin: utiliser un R*Tree est une excellente solution permettant de retrouver l'aiguille en un temps record, même si il y a énormément de paille !

Erreurs fréquentes

“j'ai une table avec plusieurs milliers de points disséminés à travers le monde:
dessiner une carte était très pénible et gourmand en temps.
Puis j'ai trouvé une super astuce, et j'ai créé un index spatial pour cette table.
et mes analyses se font bien plus rapidement (ex: "points situés en Italie"), d'une manière générale.
Cependant, je suis très confus, car la carte entière prend autant de temps à être dessinée
Pourquoi est-ce que l'INDEX SPATIAL n'affecte pas l'affichage global de la carte ?”

La réponse est très simple: l'Index spatial peut accélérer les calculs que dans le cas ou le résultat appartient à une petite portion du jeu de donnée.
Quand les résultats incluent une grande partie du jeu de donnée, l'index spatial ne permet pas de gains de performance.
On pourrait même dire que dans ce cas, utiliser l'index Spatial va ralentir les calculs, car scanner le rtree représente une étape supplémentaire.

Conclusion: l'index spatial n'est pas une baguette magique, mais plutôt un filtre.

quand le cadre de sélection couvre une petite région du jeu de donnée, l'utilisation de l'index spatial permet un réel gain de temps.
quand le cadre de sélection couvre une grande région, ce gain est moins important.
quand le cadre de sélection couvre quasiment toute la région, l'index spatial engendre un ralentissement du traitement

SQLite's et R*Tree

SQLite implémente une excellente version de R*Tree: cependant, certains détails pourraient paraître assez exotiques pour les utilisateurs d'autres SGBD spatiaux (comme POSTGIS ou autre).

Un R*Tree sur SQLite nécessite en effet quatre tables corrélées:

rtreebasename_node stocke les noeuds de l'arbre RTree au format binaire.
rtreebasename_parent stocke les relations connectant les noeuds parents et enfants.
rtreebasename_rowid stocke les valeurs de ROWID, connectant chaque nœud du R*Tree à la ligne correspondante dans la table indexée.
- aucune de ces trois tables n'est destinée à être utilisées directement: ne pas y toucher.
rtreebasename est en fait une Table Virtuelle, et permet un aces externe au R*Tree.
- important: ne jamais tenter de modifier ces tables; toute mauvaise manipulation entraînerait une corruption irréversible du R*Tree.
  Vous voila prévenu

SELECT *
FROM rtreebasename;

pkuid	miny	maxx	miny	maxy
1022	313361.000000	331410.531250	4987924.000000	5003326.000000
1175	319169.218750	336074.093750	4983982.000000	4998057.500000
1232	329932.468750	337638.812500	4989399.000000	4997615.500000
...	...	...	...	...

Chaque table R*Tree ressemble à celle-ci:

La colonne pkid contient les valeurs de ROWID .
minx, maxx, miny et maxy définissent les points extrêmes du MBR.

La logique interne de R*Tree est implémenté par la table virtuel, de façon totalement transparente pour l'utilisateur.

SpatiaLite et R*Tree

Tout Indice Spatial SpatiaLite repose entièrement sur le couple SQLite/ R*Tree.
La gestion des R*Tree est entièrement gérée par SpatiaLite:

A chaque requête e type INSERT, UPDATE or DELETE affectant la table indexée, SpatiaLite se charge automatiquement d'effectuer les changements nécessaires dans le R*Tree correspondant.
des triggers vont permettre cette synchronisation.
Ainsi, une fois l'index spatial défini, vous n'avez plus à y penser.

Dans SpatiaLite, les index spatiaux adoptent toujours la même convention de nommage:

prenons la table local_councils contenant une colonne géométrique nommée geometry.
l'Index Spatial correspondant se nommera idx_local_councils_geometry
et idx.local_councils.pkid fera référence à local_councils.ROWID.

Cependant, utiliser les index spatiaux afin d'optimiser les requêtes est un peu plus difficile que dans d'autres SGBD Spatiaux, car il n'y a pas d’intégration serrée entre la table indexée et le R*Tree correspondant: du point de vue de SQLite, ce sont deux tables distinctes.

Ainsi, l'utilisation d'un Index Spatial nécessite une clause JOIN, et la définition d'une sous requête
Vous trouverez de nombreux exemples dans la section Haute Cuisine.

SELECT CreateSpatialIndex('local_councils', 'geometry');

SELECT CreateSpatialIndex('populated_places', 'geometry');

C'est tout ce dont vous avez besoin pour créer un index spatial sur la colonne geometry d'une table.

SELECT DiscardSpatialIndex('local_councils', 'geometry');

Ceci va désactiver l'index spatial:

note: cela ne va pas supprimer physiquement l'index spatial, mais sa synchronisation avec la table.
les TRIGGER seront supprimés et les tables metadata modifiées afin de désactiver l'index spatial.

SpatiaLite supporte un second type d'index spatial, basé sur le MBR-caching. (mise en cache du MBR)
Il s'agit du premier type d'index implémenté, maintenant remplacé par R*Tress, et son utilisation est fortement déconseillée.

Table des matières

	Author: Alessandro Furieri a.furieri@lqt.it Traduced from English by RIVIERE Romain
	This work is licensed under the Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) license.

	Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.