General Search Tree

General Search Tree

In computing,GiST( 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 BST, 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 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.

General trees are those in which the number of sub trees for any node is not required to be 0, 1, or 2. The tree may be highly structured and therefore have 3 sub trees per node in which case it is called a ternary tree. However, it is often the case that the number of sub trees for any node may be variable. Some nodes may have 1 or no sub trees , others may have 3, some 4, or any other combination. The ternary tree is just a special case of a general tree (as is true of the binary tree).

Application: Disk Directories

References

1.https://en.wikipedia.org/wiki/GiST

2.db.cs.berkeley.edu/papers/icde98-search.pdf

3.www.cs.kau.se/cs/education/courses/dvgb03/lectures/NTrees_1.pdf