| dbo:abstract
|
- En computación, GiST o Árbol de búsqueda Generalizada, es una estructura de datos y API que puede ser usada para construir diferentes árboles de búsqueda en disco . GiST Es una generalización del árbol B+, proporcionando una infraestructura de árbol de búsqueda que sea concurrente, recuperable y balanceada sin tener que asumir el tipo de dato almacenado, o las consultas se están atendiendo. GiST puede usarse para implementar fácilmente una gama de índices bien conocidos, incluyendo el árbol B+, árbol R, árbol hB, árbol RD; GiST también permite desarrollar índices especiales para nuevos tipos de dato. No puede ser usarse directamente para implementar árboles sin alto balanceo como árboles quad o árboles de prefijo, aunque como los árboles de prefijo soporta compresión, incluyendo compresión con pérdida. GiST Puede ser utilizado para cualquier tipo de dato que puede ser naturalmente ordenado a una jerarquía de supersets. No sólo es extensible en cuanto soporte de tipos de dato y diseño de árbol, deja al escritor de la extensión soportar cualquier predicados de consulta que escojan. La implementación GiST más extendida está en PostgreSQL, también se implementó en Informix y como biblioteca autónoma, libgist. 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. Lo logra al factorizar la infraestructura de su sistema núcleo desde un pequeño API, suficiente para 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. Permitiendo 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 conjuntos de datos grandes. 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 - GiST implementación 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, representando 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. (es)
- In computing, GiST or Generalized Search Tree, is a data structure and API that can be used to build a variety of disk-based search trees. GiST is a generalization of the B+ tree, providing a concurrent and recoverable height-balanced search tree infrastructure without making any assumptions about the type of data being stored, or the queries being serviced. GiST can be used to easily implement a range of well-known indexes, including B+ trees, R-trees, , , and many others; it also allows for easy development of specialized indexes for new data types. It cannot be used directly to implement non-height-balanced trees such as quad trees or prefix trees (tries), though like prefix trees it does support compression, including lossy compression. GiST can be used for any data type that can be naturally ordered into a hierarchy of supersets. Not only is it extensible in terms of data type support and tree layout, it allows the extension writer to support any query predicates that they choose. GiST is an example of software extensibility in the context of database systems: it allows the easy evolution of a database system to support new tree-based indexes. It achieves this by factoring out its core system infrastructure from a narrow API that is sufficient to capture the application-specific aspects of a wide variety of index designs. The GiST infrastructure code manages the layout of the index pages on disk, the algorithms for searching indexes and deleting from indexes, and complex transactional details such as page-level locking for high concurrency and write-ahead logging for crash recovery. This allows authors of new tree-based indexes to focus on implementing the novel features of the new index type — for example, the way in which subsets of the data should be described for search — without becoming experts in database system internals. Although originally designed for answering Boolean selection queries, GiST can also support nearest-neighbor search, and various forms of statistical approximation over large data sets. (en)
- 汎用検索ツリー (GiST: Generalized Search Tree) はディスク上に木構造の検索機能を実現する データ構造 と API である。GiSTはB+木を一般化したもので、並列実行性能が高くリカバリが可能な高さがバランスされた検索木のフレームワークを提供する。また、保存できるデータ型や検索クエリに制限が無い。 GiSTは良く利用されるインデックス（B+木, R木, , など）の実装に利用できる。また、新しいデータ型に対して特化したインデックスを開発することも容易である。ただし、GiST を使っても直接的には高さバランスではないツリー構造 (八分木やトライ木) を実装することはできない。また、GiST は可逆および非可逆の圧縮をサポートしているが、各ノードのデータ型は同一でなければならない。リーフにはノードとは異なる型を用いることもできる。 データ型と木の配置だけではなく、クエリの検索条件（演算子）も拡張することができる。 最も広く利用されているGiSTは、PostgreSQL 関係データベースにおける実装である。また、Informix Universal Server でも外部ライブラリ libgist によってGiSTが利用できる。 データベースの観点では、GiSTはソフトウェアの拡張性の一例である。データベースに対して新しい木構造のインデックスを追加することが容易になる。アプリケーションごとの様々なインデックスの設計に対応できるよう、コアシステムから数個の API が外部に公開されている。GiST のフレームワークはディスク上のインデックス・ページのレイアウトを管理する。検索、削除、ページ単位ロック、高い並列実行性能、クラッシュ・リカバリのためのログ先行書き込み (WAL) のアルゴリズムなどの機能もフレームワークにより提供される。そのため、新しい木構造インデックスの製作者はデータベース・システムの内部構造に関する知識が無くても新機能の実装（例えば、データからどのように特徴量を抽出するか）に注力することができる。 GiSTは、当初は厳密な検索だけを目的として設計されたが、近傍検索もできるよう拡張された。また、巨大なデータセットから様々な形式で統計情報を取得することもできる。 PostgreSQL の GIST の実装は、可変長キー、複合キー、並行性制御、リカバリをサポートしている。これらの機能は GiST をベースとするインデックスにも継承される。GiST を利用して開発されたいくつかの貢献モジュールが PostgreSQL に添付され、提供されている。以下に例を挙げる：
* rtree_gist, btree_gist - R木やB木をGiSTで再実装したもの。
* intarray - 1次元のint4の配列に対するインデックス。
* tsearch2 - 全文検索インデックス。
* ltree - 木に似た構造を内包するデータ型の検索。
* hstore - キーと値の組を保存するデータ型。
* cube - 多次元の立方体。 PostgreSQLのGiSTの実装はPostGIS (地理空間情報システム)や (バイオインフォマティクス) に利用されている。 (ja)
- In informatica, GiST (Generalized Search Tree) o Albero di ricerca generalizzato, è una struttura dati e API che può essere usato per costruire una varietà alberi di ricerca basati sul disco. GiST è una generalizzazione degli alberi B+, che fornisce una infrastruttura ad albero di ricerca concorrente e altamente bilanciata per il recupero senza compiere alcuna assunzione sul tipo di dato archiviato o la tipologia di interrogazioni. Può essere implementato facilmente in una serie di indici ben conosciuti, inclusi alberi B+, alberi R, , e molti altri; permette anche lo sviluppo di indici specializzati per nuovi tipi di dato. Non può essere usato direttamente per implementare alberi non altamente bilanciati come Quadtree alberi a prefisso, sebbene come gli alberi a prefisso supporti la compressione, compresa quella con perdita. GiST può essere usato con tutti i tipi di dato che sono ordinati naturalmente in una gerarchia di superset (superinsiemi). La più utilizzata implementazione di GiST è nel gestore di basi di dati relazionali PostgreSQL, ma anche nell'Informix Universal Server, e come libreria libgist. (it)
- GiST (англ. Generalized Search Tree, Обобщенное поисковое дерево) — структура индекса, которая является обобщенной разновидностью R-tree и предоставляет стандартные методы навигации по дереву и его обновления (расщепление и удаление узлов). GiST представляет собой сбалансированное (по высоте) дерево, концевые узлы (листья) которого содержат пары (key, rid), где key — ключ, а rid — указатель на соответствующую запись на странице данных. Внутренние узлы содержат пары (p, ptr), где p — это некий предикат (используется как поисковый ключ), выполняющийся для *всех* наследных узлов, а ptr — указатель на другой узел в дереве. Для этого дерева определены базовые методы SEARCH, INSERT, DELETE, и интерфейс для написания пользовательских методов, которыми можно управлять работой этих (базовых) методов. Метод SEARCH управляется функцией Consistent, возвращающая 'true', если узел удовлетворяет предикату, метод INSERT — функциями penalty, picksplit и union, которые позволяют оценить сложность операции вставки в узел, разделить узел при переполнении и перестроить дерево при необходимости, метод DELETE находит лист дерева, содержащий ключ, удаляет пару (key, rid) и, если нужно, с помощью функции union перестраивает родительские узлы. GiST является прямым индексом, используемым полнотекстовым поиском СУБД PostgreSQL. Это означает, что для каждого вектора tsvector, описывающего все лексемы документа, создаётся сигнатура, описывающая, какие из лексем входят в данный tsvector. Принцип работы схож с битовыми индексами, однако есть и различия. Продемонстрируем на примере: пусть лексеме w1 сопоставлена сигнатура 001000, лексеме w2 — 000010. Тогда документу, содержащему только лексемы w1 и w2, будет сопоставлена сигнатура 001010 (001000 | 000010). В отличие от битовых индексов, отображение лексем в сигнатуры не однозначно, то есть возможно существование лексемы w3 с сигнатурой 001000. Это позволяет значительно экономить на размере индекса, но требует вторичной проверки на полное совпадение лексем запроса и документа. Стоит также обратить внимание, что в случае, если лексема запроса имеет сигнатуру, к примеру, 000001, то документ с сигнатурой 001010 однозначно её не содержит, несмотря на неоднозначность отображения лексем. Преимущество GiST в его скорости создания и размере индекса в сравнении с GiN (в 3 раза), потому он предпочтительнее для динамически постоянно обновляемых данных. Для статических данных или которые редко обновляются предпочтительнее GiN индекс (он в 3 раза быстрее производит поиск). (ru)
- Na computação, GiST or Generalized Search Tree ou Árvore de busca genérica, é uma estrutura de dados e API que pode ser usada para construir quase todo tipo de árvore de busca sob quase todo tipo de dado. Com GiST é possível construir árvores B+, , , , árvores R e muitas mais. Contudo, ela não pode ser usada para construir uma árvore de prefixos, apesar de poder dar suporte a outras formas de compressão, incluindo compressão lossy. GiST pode ser usada eficientemente para qualquer tipo de dados que possa ser naturalmente ordenado em uma hierarquia de conjuntos. Não é apenas extensível em termos de tipos de dados e layout de árvore, mas ela também permite árvores de busca pré-definidas personalizadas. GiST é implementado no banco de dados relacional PostgreSQL e também foi implementada como uma biblioteca, . GiST é bastante útil pois ela permite que novos índices, baseados em árvores, sejam criados facilmente. No PostgreSQL, o código da infra estrutura GiST gerencia o layout das próprias páginas de índice, os algoritmos para busca em índices e para remoção dos índices, e outros detalhes de implementação complexos, como trancamento para alta concorrência em nível de páginas de memória e para recuperação de dados.Isto permite que os autores de novos índices baseados em árvores se foquem em implementar as novas características do novo tipo de índice. Os desenvolvedores atuais( e ) do GiST em PostgreSQL adicionaram o suporte para chaves de tamanho variáveis, chaves compostas e suporte para recuperação e concorrência, os quais foram automaticamente herdados por todas as extensões do GiST, como o PostGIS, busca e outras. Existem vários módulos que foram desenvolvidos usando GiST e distribuídos com o PostgreSQL. Por exemplo:
* , - implementação GiST das árvores R e B
* - Suporte a índices para um vetor unidimensional de int4s
* - um tipo de busca(full text) com acesso indexado
* - tipos de dados, métodos de acesso indexado e busca para dados organizados como estruturas semelhantes a árvores
* - Armazenamento para dados do tipo (chave,valor)
* cube - tipos de dados, representando cubos multidimensionais (pt)
|
| rdfs:comment
|
- In computing, GiST or Generalized Search Tree, is a data structure and API that can be used to build a variety of disk-based search trees. GiST is a generalization of the B+ tree, providing a concurrent and recoverable height-balanced search tree infrastructure without making any assumptions about the type of data being stored, or the queries being serviced. GiST can be used to easily implement a range of well-known indexes, including B+ trees, R-trees, , , and many others; it also allows for easy development of specialized indexes for new data types. It cannot be used directly to implement non-height-balanced trees such as quad trees or prefix trees (tries), though like prefix trees it does support compression, including lossy compression. GiST can be used for any data type that can be na (en)
- En computación, GiST o Árbol de búsqueda Generalizada, es una estructura de datos y API que puede ser usada para construir diferentes árboles de búsqueda en disco . GiST Es una generalización del árbol B+, proporcionando una infraestructura de árbol de búsqueda que sea concurrente, recuperable y balanceada sin tener que asumir el tipo de dato almacenado, o las consultas se están atendiendo. GiST puede usarse para implementar fácilmente una gama de índices bien conocidos, incluyendo el árbol B+, árbol R, árbol hB, árbol RD; GiST también permite desarrollar índices especiales para nuevos tipos de dato. No puede ser usarse directamente para implementar árboles sin alto balanceo como árboles quad o árboles de prefijo, aunque como los árboles de prefijo soporta compresión, incluyendo compresión (es)
- In informatica, GiST (Generalized Search Tree) o Albero di ricerca generalizzato, è una struttura dati e API che può essere usato per costruire una varietà alberi di ricerca basati sul disco. GiST è una generalizzazione degli alberi B+, che fornisce una infrastruttura ad albero di ricerca concorrente e altamente bilanciata per il recupero senza compiere alcuna assunzione sul tipo di dato archiviato o la tipologia di interrogazioni. Può essere implementato facilmente in una serie di indici ben conosciuti, inclusi alberi B+, alberi R, , e molti altri; permette anche lo sviluppo di indici specializzati per nuovi tipi di dato. (it)
- 汎用検索ツリー (GiST: Generalized Search Tree) はディスク上に木構造の検索機能を実現する データ構造 と API である。GiSTはB+木を一般化したもので、並列実行性能が高くリカバリが可能な高さがバランスされた検索木のフレームワークを提供する。また、保存できるデータ型や検索クエリに制限が無い。 GiSTは良く利用されるインデックス（B+木, R木, , など）の実装に利用できる。また、新しいデータ型に対して特化したインデックスを開発することも容易である。ただし、GiST を使っても直接的には高さバランスではないツリー構造 (八分木やトライ木) を実装することはできない。また、GiST は可逆および非可逆の圧縮をサポートしているが、各ノードのデータ型は同一でなければならない。リーフにはノードとは異なる型を用いることもできる。 データ型と木の配置だけではなく、クエリの検索条件（演算子）も拡張することができる。 最も広く利用されているGiSTは、PostgreSQL 関係データベースにおける実装である。また、Informix Universal Server でも外部ライブラリ libgist によってGiSTが利用できる。 PostgreSQLのGiSTの実装はPostGIS (地理空間情報システム)や (バイオインフォマティクス) に利用されている。 (ja)
- Na computação, GiST or Generalized Search Tree ou Árvore de busca genérica, é uma estrutura de dados e API que pode ser usada para construir quase todo tipo de árvore de busca sob quase todo tipo de dado. Com GiST é possível construir árvores B+, , , , árvores R e muitas mais. Contudo, ela não pode ser usada para construir uma árvore de prefixos, apesar de poder dar suporte a outras formas de compressão, incluindo compressão lossy. GiST pode ser usada eficientemente para qualquer tipo de dados que possa ser naturalmente ordenado em uma hierarquia de conjuntos. Não é apenas extensível em termos de tipos de dados e layout de árvore, mas ela também permite árvores de busca pré-definidas personalizadas. GiST é implementado no banco de dados relacional PostgreSQL e também foi implementada como (pt)
- GiST (англ. Generalized Search Tree, Обобщенное поисковое дерево) — структура индекса, которая является обобщенной разновидностью R-tree и предоставляет стандартные методы навигации по дереву и его обновления (расщепление и удаление узлов). GiST представляет собой сбалансированное (по высоте) дерево, концевые узлы (листья) которого содержат пары (key, rid), где key — ключ, а rid — указатель на соответствующую запись на странице данных. Внутренние узлы содержат пары (p, ptr), где p — это некий предикат (используется как поисковый ключ), выполняющийся для *всех* наследных узлов, а ptr — указатель на другой узел в дереве. Для этого дерева определены базовые методы SEARCH, INSERT, DELETE, и интерфейс для написания пользовательских методов, которыми можно управлять работой этих (базовых) методо (ru)
|
