GiST
# GiST

En computación, el GiST o árbol de búsqueda generalizada es una estructura de datos e interfaz de programación de aplicaciones (API) que sirve para construir diferentes árboles de búsqueda en disco. GiST es una generalización del árbol B+, y proporciona una infraestructura de árbol de búsqueda que es concurrente, recuperable y balanceada sin tener que asumir el tipo de dato almacenado o las consultas que se están atendiendo.

Puede usarse para implementar fácilmente una gama de índices como el árbol B+, el árbol R, el árbol hB, el árbol RD. También permite desarrollar índices especiales para nuevos tipos de dato. No puede usarse directamente para implementar árboles sin alto balanceo como árboles quad o árboles de prefijo, aunque como los árboles de prefijo soporta compresión, e incluye compresión con pérdida. Puede usarse para cualquier tipo de dato que se ordene naturalmente en una jerarquía de subconjuntos.

GiST no sólo es extensible como soporte de tipos de dato y diseño de árbol, sino que también deja al escritor de la extensión soportarse en cualquier predicado de consulta que elija. GiST se ha implementado en Informix y en libgist como biblioteca autónoma, aunque la implementación más extendida está en PostgreSQL.

GiST es un ejemplo de extensibilidad de software en los sistemas de base de datos: permite una fácil evolución de un sistema de base de datos para soportar nuevos índices basados en árboles. Esto es posible ya que GiST permite factorizar la infraestructura de su sistema núcleo desde una pequeña API, que permite capturar aspectos concretos de la aplicación de una amplia gama de diseños de índice. El código de infraestructura GiST dirige el diseño de las páginas de índice en disco, los algoritmos para buscar índices y eliminando desde los índices, y detalles transaccionales complejos como bloqueo de nivel de página para una alta concurrencia y registro de escritura anticipada para la recuperación de accidentes. Permite a los autores de nuevos índices basados en árboles enfocarse en implementar las nuevas características del nuevo tipo de índice, sin ser expertos en el interior del sistema de base de datos. Por ejemplo, la manera en qué los subconjuntos de datos tienen que describirse para la búsqueda.

Aunque fue diseñada para responder consultas de selección booleana, GiST también puede soportar búsqueda de vecino cercano, y varias formas de aproximación estadística sobre grandes conjuntos de datos.

La implementación de GiST en PostgreSQL incluye soporte para llaves de longitud variable, llaves compuestas, control de concurrencia y recuperación; estas características están heredadas por todas las extensiones de GiST. Hay varios módulos desarrollados usando GiST y distribuidos con PostgreSQL. Por ejemplo:

* rtree_gist, btree_gist - implementación GiST del árbol R y el árbol B
* intarray - soporte de índice para un arreglo unidimensional de int4
* tsearch2 - un tipo de dato (texto completo) con acceso indexado en el que se puede buscar
* ltree - tipos de datos, métodos de acceso indexado y consultas para datos organizados como estructuras tipo árbol
* hstore - un almacenamiento para datos (llave, valor)
* Cubo - tipo de datos que representan cubos multidimensionales

La implementación de PostgreSQL GiST proporciona el soporte de indexación para el PostGIS (sistema de información geográfica) y el sistema bioinformático BioPostgres.

