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

<sect1 id="spgist">
<title>SP-GiST Indexes</title>

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

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

 <para>
  <acronym>SP-GiST</acronym> is an abbreviation for space-partitioned
  <acronym>GiST</acronym>.  <acronym>SP-GiST</acronym> supports partitioned
  search trees, which facilitate development of a wide range of different
  non-balanced data structures, such as quad-trees, k-d trees, and radix
  trees (tries).  The common feature of these structures is that they
  repeatedly divide the search space into partitions that need not be
  of equal size.  Searches that are well matched to the partitioning rule
  can be very fast.
 </para>

 <para>
  These popular data structures were originally developed for in-memory
  usage.  In main memory, they are usually designed as a set of dynamically
  allocated nodes linked by pointers.  This is not suitable for direct
  storing on disk, since these chains of pointers can be rather long which
  would require too many disk accesses.  In contrast, disk-based data
  structures should have a high fanout to minimize I/O.  The challenge
  addressed by <acronym>SP-GiST</acronym> is to map search tree nodes to
  disk pages in such a way that a search need access only a few disk pages,
  even if it traverses many nodes.
 </para>

 <para>
  Like <acronym>GiST</acronym>, <acronym>SP-GiST</acronym> is meant to allow
  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 Purdue University's
  SP-GiST Indexing Project
  <ulink url="https://www.cs.purdue.edu/spgist/">web site</ulink>.
  The <acronym>SP-GiST</acronym> implementation in
  <productname>PostgreSQL</productname> is primarily maintained by Teodor
  Sigaev and Oleg Bartunov, and there is more information on their
  <!-- URL will be changed -->
  <ulink url="http://www.sai.msu.su/~megera/wiki/spgist_dev">web site</ulink>.
 </para>

</sect2>

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

 <para>
  The core <productname>PostgreSQL</productname> distribution
  includes the <acronym>SP-GiST</acronym> operator classes shown in
  <xref linkend="spgist-builtin-opclasses-table"/>.
 </para>

  <table id="spgist-builtin-opclasses-table">
   <title>Built-in <acronym>SP-GiST</acronym> Operator Classes</title>
   <tgroup cols="3">
    <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;&gt; (box,box)</literal></entry></row>
     <row><entry><literal>&gt;&gt; (box,box)</literal></entry></row>
     <row><entry><literal>&lt;@ (box,box)</literal></entry></row>
     <row><entry><literal>@&gt; (box,box)</literal></entry></row>
     <row><entry><literal>~= (box,box)</literal></entry></row>
     <row><entry><literal>&amp;&amp; (box,box)</literal></entry></row>
     <row><entry><literal>&lt;&lt;| (box,box)</literal></entry></row>
     <row><entry><literal>&amp;&lt;| (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 valign="middle" morerows="10"><literal>inet_ops</literal></entry>
      <entry><literal>&lt;&lt; (inet,inet)</literal></entry>
      <entry valign="middle" morerows="10"></entry>
     </row>
     <row><entry><literal>&lt;&lt;=