| dbpprop:abstract
|
- 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, hB-trees, RD-trees, and many others; it also allows for easy development of specialized indexes for new data types. It can not 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. The most widely-used GiST implementation is in the PostgreSQL relational database; it was also implemented in the Informix Universal Server, and as a standalone library, libgist. 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. The PostgreSQL GiST implementation includes support for variable length keys, composite keys, concurrency control and recovery; these features are inherited by all GiST extensions. There are several contributed modules developed using GiST and distributed with PostgreSQL. For example: rtree_gist, btree_gist - GiST implementation of R-Tree and B-Tree intarray - index support for one-dimensional array of int4's tsearch2 - a searchable (full text) data type with indexed access ltree - data types, indexed access methods and queries for data organized as a tree-like structures hstore - a storage for (key,value) data cube - data type, representing multidimensional cubes The PostgreSQL GiST implementation provides the indexing support for the PostGIS and the BioPostgres bioinformatics system.
- 汎用検索ツリー はディスク上に木構造の検索機能を実現する データ構造 と API である。 GiSTはB+木を一般化したもので、並列実行性能が高くリカバリが可能な高さがバランスされた検索木のフレームワークを提供する。 また、保存できるデータ型や検索クエリに制限が無い。 GiSTは良く利用されるインデックス（B+木, R木, hB木, RD木 など）の実装に利用できる。 また、新しいデータ型に対して特化したインデックスを開発することも容易である。 ただし、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やBioPostgres に利用されている。
- 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 kd, árvores hB, árvores RD, á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, libgist. 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 write-ahead logging 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 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 full-text e outras. Existem vários módulos que foram desenvolvidos usando GiST e distribuídos com o PostgreSQL. Por exemplo: rtree_gist, btree_gist - implementação GiST das árvores R e B intarray - Suporte a índices para um vetor unidimensional de int4s tsearch2 - um tipo de busca(full text) com acesso indexado ltree - tipos de dados, métodos de acesso indexado e busca para dados organizados como estruturas semelhantes a árvores hstore - Armazenamento para dados do tipo (chave,valor) cube - tipos de dados, representando cubos multidimensionais
|
| 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.
- 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 kd, árvores hB, árvores RD, á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.
|
![[RDF Data]](/statics/sw-cube.png)
