computer science

GiST

GiST is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand GiST rather than just read about it. In short: 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.

Key takeaways

GiST belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect GiST to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of GiST from memory before moving on to harder problems.

Reference excerpt

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 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.

Implementations 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.

PostgreSQL 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 (geographic information system) and the BioPostgres bioinformatics system.

References

Joseph M. Hellerstein, Jeffrey F. Naughton and Avi Pfeffer. Generalized Search Trees for Database Systems. Proc. 21st Int'l Conf. on Very Large Data Bases, Zürich, September 1995, 562–573. Marcel Kornacker, C. Mohan and Joseph M. Hellerstein. Concurrency and Recovery in Generalized Search Trees. Proc. ACM SIGMOD Conf. on Management of Data, Tucson, AZ, May 1997, 62–72. Paul M. Aoki. Generalizing "Search" in Generalized Search Trees. Proc. 14th Int'l Conf. on Data Engineering, Orlando, FL, Feb. 1998, 380–389. Marcel Kornacker. High-Performance Generalized Search Trees, Proc. 24th Int'l Conf. on Very Large Data Bases, Edinburgh, Scotland, September 1999. Paul M. Aoki. How to Avoid Building DataBlades That Know the Value of Everything and the Cost of Nothing, Proc. 11th Int'l Conf. on Scientific and Statistical Database Management, Cleveland, OH, July 1999, 122–133.

External links GiST research project website PostgreSQL GiST Development Documentation for the GiST support in PostgreSQL Developing PostgreSQL extension with GiST (in Russian) GiST in PostgreSQL wiki PostGIS BioPostgres

Worked examples

Example 1 — a first encounter with GiST

Start with the simplest possible case. Write down what GiST claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to GiST before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about GiST ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of GiST

In research: GiST appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses GiST in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: GiST is common in secondary-school and first-year university syllabi. It links to neighbouring topics PostgreSQL, Trees (data structures), so understanding it makes those chapters shorter.
In everyday life: Look for GiST outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study GiST in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what GiST means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain GiST out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is GiST in simple terms?

Why does GiST matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study GiST?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on GiST.