En informática, GiST o Generalized Search Tree (árbol de búsqueda generalizado) es una estructura de datos y una API que se puede utilizar para crear una variedad de árboles de búsqueda basados en disco . GiST es una generalización del árbol B+ , que proporciona una infraestructura de árbol de búsqueda con equilibrio de altura concurrente y recuperable sin hacer suposiciones sobre el tipo de datos que se almacenan o las consultas que se atienden. GiST se puede utilizar para implementar fácilmente una variedad de índices conocidos, incluidos árboles B+ , árboles R , árboles hB, árboles RD y muchos otros; también permite el desarrollo sencillo de índices especializados para nuevos tipos de datos. No se puede utilizar directamente para implementar árboles sin equilibrio de altura, como árboles cuádruples o árboles de prefijo (intentos), aunque, al igual que los árboles de prefijo, admite la compresión, incluida la compresión con pérdida . GiST se puede utilizar para cualquier tipo de datos que se pueda ordenar de forma natural en una jerarquía de superconjuntos . No solo es extensible en términos de compatibilidad con tipos de datos y diseño de árboles, sino que permite al escritor de extensiones admitir cualquier predicado de consulta que elija.
GiST es un ejemplo de extensibilidad de software en el contexto de los sistemas de bases de datos: permite la fácil evolución de un sistema de bases de datos para soportar nuevos índices basados en árboles. Esto se logra al extraer de su infraestructura de sistema central una API estrecha que es suficiente para capturar los aspectos específicos de la aplicación de una amplia variedad de diseños de índices. El código de infraestructura de GiST administra el diseño de las páginas de índice en el disco, los algoritmos para buscar índices y eliminarlos de los índices, y detalles transaccionales complejos como el bloqueo a nivel de página para alta concurrencia y el registro de escritura anticipada para la recuperación de fallas. Esto permite a los autores de nuevos índices basados en árboles enfocarse en implementar las características novedosas del nuevo tipo de índice (por ejemplo, la forma en que se deben describir los subconjuntos de los datos para la búsqueda) sin convertirse en expertos en los aspectos internos del sistema de bases de datos.
Aunque originalmente fue diseñado para responder consultas de selección booleana, GiST también puede soportar la búsqueda del vecino más cercano y varias formas de aproximación estadística sobre grandes conjuntos de datos.
La implementación de GiST más utilizada está en la base de datos relacional PostgreSQL ; también se implementó en Informix Universal Server y como una biblioteca independiente, libgist.
La implementación de GiST para PostgreSQL incluye compatibilidad con claves de longitud variable, claves compuestas, control de concurrencia y recuperación; todas las extensiones de GiST heredan estas características. Existen varios módulos contribuidos desarrollados con GiST y distribuidos con PostgreSQL. Por ejemplo:
La implementación de PostgreSQL GiST proporciona soporte de indexación para PostGIS ( sistema de información geográfica ) y el sistema de bioinformática BioPostgres .