structure that
  may offer better performance in some applications.
 </para>
 <para>
  The <literal>quad_point_ops</literal>, <literal>kd_point_ops</literal> and
  <literal>poly_ops</literal> operator classes support the <literal>&lt;-&gt;</literal>
  ordering operator, which enables the k-nearest neighbor (<literal>k-NN</literal>)
  search over indexed point or polygon data sets.
 </para>

</sect2>

<sect2 id="spgist-extensibility">
 <title>Extensibility</title>

 <para>
  <acronym>SP-GiST</acronym> offers an interface with a high level of
  abstraction, requiring the access method developer to implement only
  methods specific to a given data type. The <acronym>SP-GiST</acronym> core
  is responsible for efficient disk mapping and searching the tree structure.
  It also takes care of concurrency and logging considerations.
 </para>

 <para>
  Leaf tuples of an <acronym>SP-GiST</acronym> tree usually contain values
  of the same data type as the indexed column, although it is also possible
  for them to contain lossy representations of the indexed column.
  Leaf tuples stored at the root level will directly represent
  the original indexed data value, but leaf tuples at lower
  levels might contain only a partial value, such as a suffix.
  In that case the operator class support functions must be able to
  reconstruct the original value using information accumulated from the
  inner tuples that are passed through to reach the leaf level.
 </para>

 <para>
  When an <acronym>SP-GiST</acronym> index is created with
  <literal>INCLUDE</literal> columns, the values of those columns are also
  stored in leaf tuples.  The <literal>INCLUDE</literal> columns are of no
  concern to the <acronym>SP-GiST</acronym> operator class, so they are
  not discussed further here.
 </para>

 <para>
  Inner tuples are more complex, since they are branching points in the
  search tree.  Each inner tuple contains a set of one or more
  <firstterm>nodes</firstterm>, which represent groups of similar leaf values.
  A node contains a downlink that leads either to another, lower-level inner
  tuple, or to a short list of leaf tuples that all lie on the same index page.
  Each node normally has a <firstterm>label</firstterm> that describes it; for example,
  in a radix tree the node label could be the next character of the string
  value.  (Alternatively, an operator class can omit the node labels, if it
  works with a fixed set of nodes for all inner tuples;
  see <xref linkend="spgist-null-labels"/>.)
  Optionally, an inner tuple can have a <firstterm>prefix</firstterm> value
  that describes all its members.  In a radix tree this could be the common
  prefix of the represented strings.  The prefix value is not necessarily
  really a prefix, but can be any data needed by the operator class;
  for example, in a quad-tree it can store the central point that the four
  quadrants are measured with respect to.  A quad-tree inner tuple would
  then also contain four nodes corresponding to the quadrants around this
  central point.
 </para>

 <para>
  Some tree algorithms require knowledge of level (or depth) of the current
  tuple, so the <acronym>SP-GiST</acronym> core provides the possibility for
  operator classes to manage level counting while descending the tree.
  There is also support for incrementally reconstructing the represented
  value when that is needed, and for passing down additional data (called
  <firstterm>traverse values</firstterm>) during a tree descent.
 </para>

 <note>
  <para>
   The <acronym>SP-GiST</acronym> core code takes care of null entries.
   Although <acronym>SP-GiST</acronym> indexes do store entries for nulls
   in indexed columns, this is hidden from the index operator class code:
   no null index entries or search conditions will ever be passed to the
   operator class methods.  (It is assumed that <acronym>SP-GiST</acronym>
   operators are strict and so cannot succeed for null values.)  Null values
   are therefore not