<!-- doc/src/sgml/gist.sgml -->

<sect1 id="gist">
<title>GiST Indexes</title>

   <indexterm>
    <primary>index</primary>
    <secondary>GiST</secondary>
   </indexterm>

<sect2 id="gist-intro">
 <title>Introduction</title>

 <para>
   <acronym>GiST</acronym> stands for Generalized Search Tree.  It is a
   balanced, tree-structured access method, that acts as a base template in
   which to implement arbitrary indexing schemes. B-trees, R-trees and many
   other indexing schemes can be implemented in <acronym>GiST</acronym>.
 </para>

 <para>
  One advantage of <acronym>GiST</acronym> is that it allows the development
  of custom data types with the appropriate access methods, by
  an expert in the domain of the data type, rather than a database expert.
 </para>

  <para>
    Some of the information here is derived from the University of California
    at Berkeley's GiST Indexing Project
    <ulink url="http://gist.cs.berkeley.edu/">web site</ulink> and
    Marcel Kornacker's thesis,
    <ulink url="http://www.sai.msu.su/~megera/postgres/gist/papers/concurrency/access-methods-for-next-generation.pdf.gz">
    Access Methods for Next-Generation Database Systems</ulink>.
    The <acronym>GiST</acronym>
    implementation in <productname>PostgreSQL</productname> is primarily
    maintained by Teodor Sigaev and Oleg Bartunov, and there is more
    information on their
    <ulink url="http://www.sai.msu.su/~megera/postgres/gist/">web site</ulink>.
  </para>

</sect2>

<sect2 id="gist-builtin-opclasses">
 <title>Built-in Operator Classes</title>

 <para>
  The core <productname>PostgreSQL</productname> distribution
  includes the <acronym>GiST</acronym> operator classes shown in
  <xref linkend="gist-builtin-opclasses-table"/>.
  (Some of the optional modules described in <xref linkend="contrib"/>
  provide additional <acronym>GiST</acronym> operator classes.)
 </para>

  <table id="gist-builtin-opclasses-table">
   <title>Built-in <acronym>GiST</acronym> Operator Classes</title>
   <tgroup cols="3">
     <colspec colname="col1" colwidth="2*"/>
     <colspec colname="col2" colwidth="3*"/>
     <colspec colname="col3" colwidth="2*"/>
    <thead>
     <row>
      <entry>Name</entry>
      <entry>Indexable Operators</entry>
      <entry>Ordering Operators</entry>
     </row>
    </thead>
    <tbody>
     <row>
      <entry valign="middle" morerows="11"><literal>box_ops</literal></entry>
      <entry><literal>&lt;&lt; (box, box)</literal></entry>
      <entry valign="middle" morerows="11"><literal>&lt;-&gt; (box, point)</literal></entry>
     </row>
     <row><entry><literal>&amp;&lt; (box, box)</literal></entry></row>
     <row><entry><literal>&amp;&amp; (box, box)</literal></entry></row>
     <row><entry><literal>&amp;&gt; (box, box)</literal></entry></row>
     <row><entry><literal>&gt;&gt; (box, box)</literal></entry></row>
     <row><entry><literal>~= (box, box)</literal></entry></row>
     <row><entry><literal>@&gt; (box, box)</literal></entry></row>
     <row><entry><literal>&lt;@ (box, box)</literal></entry></row>
     <row><entry><literal>&amp;&lt;| (box, box)</literal></entry></row>
     <row><entry><literal>&lt;&lt;| (box, box)</literal></entry></row>
     <row><entry><literal>|&gt;&gt; (box, box)</literal></entry></row>
     <row><entry><literal>|&amp;&gt; (box, box)</literal></entry></row>

     <row>
      <entry valign="middle" morerows="11"><literal>circle_ops</literal></entry>
      <entry><literal>&lt;&lt; (circle, circle)</literal></entry>
      <entry valign="middle" morerows="11"><literal>&lt;-&gt; (circle, point)</literal></entry>
     </row>
     <row><entry><literal>&amp;&lt; (circle, circle)</literal></entry></row>
     <row><entry><literal>&amp;&gt; (circle, circle)</literal></entry></row>
     <row><entry><literal>&gt;&gt; (circle, circle)</literal></entry></row>
     <row><entry><literal>&lt;@ (circle, circle)</literal></entry></row>
     <row><entry><literal>@&gt; (circle, circle)</literal></entry></row>