Esencia

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:

• rtree_gist, btree_gist: implementación de GiST de R-tree y B-tree
• intarray - soporte de índice para matriz unidimensional de int4
• tsearch2: un tipo de datos que se puede buscar (texto completo) con acceso indexado
• ltree: tipos de datos, métodos de acceso indexados y consultas de datos organizados como estructuras tipo árbol
• hstore - un almacenamiento para datos (clave, valor)
• cubo - tipo de datos que representa cubos multidimensionales

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 .

• Joseph M. Hellerstein , Jeffrey F. Naughton y Avi Pfeffer. Árboles de búsqueda generalizados para sistemas de bases de datos. Proc. 21.ª Conferencia Internacional sobre Bases de Datos de Gran Tamaño, Zúrich, septiembre de 1995, 562–573.
• Marcel Kornacker, C. Mohan y Joseph M. Hellerstein. Concurrencia y recuperación en árboles de búsqueda generalizados. Proc. ACM SIGMOD Conf. on Management of Data, Tucson, AZ, mayo de 1997, 62–72.
• Paul M. Aoki. Generalización de la "búsqueda" en árboles de búsqueda generalizados. Actas de la 14.ª Conferencia Internacional sobre Ingeniería de Datos, Orlando, Florida, febrero de 1998, 380–389.
• Marcel Kornacker. Árboles de búsqueda generalizados de alto rendimiento, Actas de la 24ª Conferencia Internacional sobre Bases de Datos de Gran Tamaño, Edimburgo, Escocia, septiembre de 1999.
• Paul M. Aoki. Cómo evitar la creación de DataBlades que conozcan el valor de todo y el costo de nada, Actas de la 11.ª Conferencia Internacional sobre Gestión de Bases de Datos Científicas y Estadísticas, Cleveland, Ohio, julio de 1999, 122–133.

• Sitio web del proyecto de investigación GiST
• Desarrollo de GiST en PostgreSQL
• Documentación para el soporte de GiST en PostgreSQL
• Desarrollo de una extensión PostgreSQL con GiST (en ruso)
• GiST en la wiki de PostgreSQL
• PostGIS
• BioPostgres