En informática, GiST o árbol de búsqueda generalizado, es una estructura de datos y una API que se puede utilizar para construir 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 gama de índices bien conocidos, incluyendo + árboles B , R-árboles , HB-árboles , RD-árboles, 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 con altura no equilibrada, como árboles cuádruples o árboles de prefijos (intentos), aunque, al igual que los árboles de prefijos, admite la compresión, incluida la compresión con pérdida . GiST se puede utilizar para cualquier tipo de datos que se pueda ordenar naturalmente en una jerarquía de superconjuntos . No solo es extensible en términos de soporte de tipo de datos y diseño de árbol, 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 admitir nuevos índices basados en árboles. Lo logra al factorizar su infraestructura de sistema central a partir de 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 GiST administra el diseño de las páginas de índice en el disco, los algoritmos para buscar índices y eliminar de índices, y detalles transaccionales complejos como el bloqueo a nivel de página para alta concurrencia y registro de escritura anticipada para recuperación de fallas. Esto permite a los autores de nuevos índices basados en árboles centrarse en implementar las características novedosas del nuevo tipo de índice, por ejemplo, la forma en que se deben describir los subconjuntos de datos para la búsqueda, sin convertirse en expertos en los componentes internos del sistema de bases de datos.
Aunque originalmente diseñado para responder consultas de selección booleana, GiST también puede admitir la búsqueda del vecino más cercano y varias formas de aproximación estadística sobre grandes conjuntos de datos.
Implementaciones
La implementación GiST más utilizada se encuentra en la base de datos relacional PostgreSQL ; también se implementó en Informix Universal Server y, como biblioteca independiente, libgist.
PostgreSQL
La implementación de PostgreSQL GiST incluye soporte para claves de longitud variable, claves compuestas, control de concurrencia y recuperación; estas características son heredadas por todas las extensiones GiST. Hay varios módulos contribuidos desarrollados usando GiST y distribuidos con PostgreSQL. Por ejemplo:
- rtree_gist, btree_gist - Implementación GiST de R-tree y B-tree
- intarray: soporte de índice para una matriz unidimensional de int4
- tsearch2: un tipo de datos con capacidad de búsqueda (texto completo) con acceso indexado
- ltree: tipos de datos, métodos de acceso indexados y consultas de datos organizados como estructuras en forma de árbol
- hstore: un almacenamiento para datos (clave, valor)
- cubo: tipo de datos, que representa cubos multidimensionales
La implementación de PostgreSQL GiST proporciona el soporte de indexación para PostGIS ( sistema de información geográfica ) y el sistema bioinformático BioPostgres .
Referencias
- Joseph M. Hellerstein , Jeffrey F. Naughton y Avi Pfeffer. Árboles de búsqueda generalizados para sistemas de bases de datos . Proc. 21ª Conf. Internacional on Very Large Data Bases, Zürich, septiembre de 1995, 562–573.
- Marcel Kornacker, C. Mohan y Joseph M. Hellerstein. Simultaneidad 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 "Búsqueda" en árboles de búsqueda generalizados . Proc. 14ª Conf. Internacional on Data Engineering, Orlando, FL, febrero de 1998, 380–389.
- Marcel Kornacker. Árboles de búsqueda generalizados de alto rendimiento , Proc. 24.a Conf. Internacional on Very Large Data Bases, Edimburgo, Escocia, septiembre de 1999.
- Paul M. Aoki. Cómo evitar la construcción de DataBlades que conocen el valor de todo y el costo de nada , Proc. XI Conf. Internacional sobre Gestión de bases de datos científicas y estadísticas, Cleveland, OH, julio de 1999, 122-133.
enlaces externos
- Sitio web del proyecto de investigación GiST
- Desarrollo de PostgreSQL GiST
- Documentación para el soporte GiST en PostgreSQL
- Desarrollando la extensión PostgreSQL con GiST (en ruso)
- GiST en PostgreSQL wiki
- PostGIS
- BioPostgres