GiST

En informatique, GiST ou Generalized Search Tree, est une structure de données et une API qui peuvent être utilisées pour créer une variété d'arbres de recherche sur disque. GiST est une généralisation de l'arbre B+, offrant une infrastructure d'arbre de recherche équilibré en hauteur, simultanée et récupérable, sans présumer du type de données stockées ni des requêtes effectuées. GiST peut être utilisé pour implémenter facilement une gamme d'index bien connus, notamment les arbres B+, R, hB, RD et bien d'autres ; il permet également de développer facilement des index spécialisés pour de nouveaux types de données. Il ne peut pas être utilisé directement pour implémenter des arbres non équilibrés en hauteur comme les arbres quadruples (quadtrees) ou les arbres préfixes, mais, à l’instar des tries, il prend en charge la compression, y compris la compression avec perte. GiST peut être utilisé avec tout type de données pouvant être naturellement ordonnées en une hiérarchie de sur-ensembles. Il est non seulement extensible en termes de prise en charge des types de données et de structure de l’arborescence, mais il permet aussi aux développeurs d’extensions de prendre en charge n’importe quel prédicat de requête.

Extensibilité dans les bases de données

GiST est un exemple d'extensibilité logicielle dans le contexte des systèmes de base de données (SGBD) : il permet une évolution facile d'un système pour prendre en charge de nouveaux index basés sur des arbres. Il y parvient en dissociant son infrastructure système de base via une API minimaliste qui suffit à représenter les aspects spécifiques à l’application d’une large gamme de conceptions d’index. L’infrastructure GiST gère l’organisation des pages d’index sur le disque, les algorithmes de recherche et de suppression des index, ainsi que des aspects transactionnels complexes tels que le verrouillage au niveau de la page pour un haut degré de concurrence élevée et la journalisation en écriture anticipée pour la récupération après incident.

Grâce à cette approche, les développeurs peuvent se concentrer sur la mise en œuvre de nouvelles fonctionnalités pour de nouveaux types d’index (ex. la manière dont les sous-ensembles de données doivent être décrits pour la recherche) sans devoir maîtriser en profondeur les mécanismes internes des SGBD.

Bien qu'initialement conçu pour répondre aux requêtes de sélection booléennes, GiST peut également prendre en charge la recherche du plus proche voisin et diverses formes d'approximation statistique sur de grands ensembles de données.

Implémentations

L'implémentation de GiST la plus largement utilisée se trouve dans la base de données relationnelle PostgreSQL ; elle a également été implémentée dans Informix Universal Server, ainsi que sous forme de bibliothèque autonome, libgist.

PostgreSQL

L'implémentation de GiST dans PostgreSQL comprend la prise en charge des clés de longueur variable, des clés composées, du contrôle de concurrence et de la récupération ; ces fonctionnalités sont héritées par toutes les extensions GiST. Il existe plusieurs modules contribué développés en utilisant GiST et distribués avec PostgreSQL. Par exemple :

• rtree_gist, btree_gist - Implémentation GiST de R-tree et B-tree
• intarray - Prise en charge des index pour les tableaux unidimensionnels d'entiers de type int4
• tsearch2 - Un type de données consultable (texte intégral) avec un accès indexé
• ltree - Types de données, méthodes d'accès indexées et requêtes pour des données organisées sous forme de structures arborescentes
• hstore - Un stockage pour des données (clé, valeur)
• cube - Type de données représentant des cubes multidimensionnels

L'implémentation de GiST dans PostgreSQL fournit également le support des index pour PostGIS (système d'information géographique) et le système bio-informatique BioPostgres.