C'est quoi ?
Un index est une structure de données qui doit être maintenue en permance. Une modification de la donnée sur laquelle se trouve un index doit être répercuter dans la structure de l'index. Ajouter un index demande donc des opérations lors de l'édition de la donnée. Cependant ce coup de maintenance de la structure de donnée devient plus rentable à mesure que le volume total de donnée augmente.
Un index doit être indépendant de la donnée sur laquelle il se trouve. La supression de l'index ne doit pas entraîner la suppression de la donnée. Si un index peut imposer un stockage particulier de la donnée sur le support de stockage (ordonnée ou non), il ne doit pas modifier sa valeur.
A quoi ça sert ?
Un exemple est souvent plus parlant qu'une longue explication. Demandons l'identifiant des bâtiments se trouvant dans le premier arrondissement de Lyon.
Sur un serveur PostgreSQL avec l'extension spatiale PostGIS, 12Go de ram, deux processeurs Intel Xeon et 5 min plus tard la requête tourne encore. La table des bâtiments contient près de 350 000 géométries.
SELECT c.gid FROM cadbatiment c, arrondissement a WHERE ST_Contains(a.geom, c.geom) AND a.__gid = '1'
En créant un index spatial et en executant la même requête, le temps d'attente tombe à 611ms.
La couche des bâtiments contient seulement 350 000 bâtiments et une seule intersection est effectuée. On conçoit facilement que le calcul d'un itinéraire peut s'avérer compliqué sans un index spatial adapté.
CREATE INDEX sidx_arrondissement_geom
ON arrondissement
USING gist(geom);
--------
CREATE INDEX index_cad_geom
ON cadbatiment
USING gist(geom);
C'est tout ?
Les index spatiaux sont utilisés dans de nombreuses applications parmis lesquelles :
- Clustering
- Itinéraires
- Ray casting
- Frustum culling
- Aéronautique
- ...
Certaines de ces applications seraient inexploitables sur un volume de donnée réel sans index spatial. Le clustering voit certains algorithmes passé d'une complexité en O(2^n) à O(logn) en présence d'un index spatial. Il faut cependant pondérer un tel résultat en prenant en compte le temps de construction de l'index qui peux parfois être élevé.