Spatial Indexes - Implémentations

PostGIS, la référence OpenSource en matière de base de données géospatiale implémente un R-Tree pour son index spatial. Pour accéder et modifier à cette index spatiale PostGIS utilise l'API GiST (Generalized Search Tree). Cette API permet de spécifier une structure de données différente suivant les besoins de l'index. Si l'implémentation par défaut reste un R-Tree, il est également possible d'utiliser un B-Tree pour l'index spatial.

SpatiaLite est l'extension spatial de SQLite et dispose également d'un index spatial. De part sa conception et simplicité SQLite permet de connaître plus facilement l'implémentation interne des extensions de SQLite. L'implémentation de référence de leur arbre est un R*Tree. En interne cette index est stocker dans 4 tables distinctes :

  • Noeud
  • Parent
  • RowID
  • View

Ces tables sont mise à jour via un mécanisme de triggers, courant dans une base de données.

Leaflet est une librairie javascript permettant de créer des cartes interactives sur une page web. Une autre librairie javascript permet à Leaflet d'intégrer les index spatiaux. Cette librairie nommé rbush et développée par le créateur de Leaflet implémente un mélange entre un R-Tree et R*Tree. En effet certains aspects, tel que le découpage topologique, du R*Tree ont été implémenté pour améliorer les performances de l'index.