<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <HTML ><HEAD ><TITLE >Introduction</TITLE ><META NAME="GENERATOR" CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK REV="MADE" HREF="mailto:pgsql-docs@postgresql.org"><LINK REL="HOME" TITLE="PostgreSQL 9.3.9 Documentation" HREF="index.html"><LINK REL="UP" TITLE="SP-GiST Indexes" HREF="spgist.html"><LINK REL="PREVIOUS" TITLE="SP-GiST Indexes" HREF="spgist.html"><LINK REL="NEXT" TITLE="Extensibility" HREF="spgist-extensibility.html"><LINK REL="STYLESHEET" TYPE="text/css" HREF="stylesheet.css"><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1"><META NAME="creation" CONTENT="2015-06-13T20:07:22"></HEAD ><BODY CLASS="SECT1" ><DIV CLASS="NAVHEADER" ><TABLE SUMMARY="Header navigation table" WIDTH="100%" BORDER="0" CELLPADDING="0" CELLSPACING="0" ><TR ><TH COLSPAN="5" ALIGN="center" VALIGN="bottom" ><A HREF="index.html" >PostgreSQL 9.3.9 Documentation</A ></TH ></TR ><TR ><TD WIDTH="10%" ALIGN="left" VALIGN="top" ><A TITLE="SP-GiST Indexes" HREF="spgist.html" ACCESSKEY="P" >Prev</A ></TD ><TD WIDTH="10%" ALIGN="left" VALIGN="top" ><A HREF="spgist.html" ACCESSKEY="U" >Up</A ></TD ><TD WIDTH="60%" ALIGN="center" VALIGN="bottom" >Chapter 56. SP-GiST Indexes</TD ><TD WIDTH="20%" ALIGN="right" VALIGN="top" ><A TITLE="Extensibility" HREF="spgist-extensibility.html" ACCESSKEY="N" >Next</A ></TD ></TR ></TABLE ><HR ALIGN="LEFT" WIDTH="100%"></DIV ><DIV CLASS="SECT1" ><H1 CLASS="SECT1" ><A NAME="SPGIST-INTRO" >56.1. Introduction</A ></H1 ><P > <ACRONYM CLASS="ACRONYM" >SP-GiST</ACRONYM > is an abbreviation for space-partitioned <ACRONYM CLASS="ACRONYM" >GiST</ACRONYM >. <ACRONYM CLASS="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. </P ><P > 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 CLASS="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. </P ><P > Like <ACRONYM CLASS="ACRONYM" >GiST</ACRONYM >, <ACRONYM CLASS="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. </P ><P > Some of the information here is derived from Purdue University's SP-GiST Indexing Project <A HREF="http://www.cs.purdue.edu/spgist/" TARGET="_top" >web site</A >. The <ACRONYM CLASS="ACRONYM" >SP-GiST</ACRONYM > implementation in <SPAN CLASS="PRODUCTNAME" >PostgreSQL</SPAN > is primarily maintained by Teodor Sigaev and Oleg Bartunov, and there is more information on their <A HREF="http://www.sai.msu.su/~megera/wiki/spgist_dev" TARGET="_top" >web site</A >. </P ></DIV ><DIV CLASS="NAVFOOTER" ><HR ALIGN="LEFT" WIDTH="100%"><TABLE SUMMARY="Footer navigation table" WIDTH="100%" BORDER="0" CELLPADDING="0" CELLSPACING="0" ><TR ><TD WIDTH="33%" ALIGN="left" VALIGN="top" ><A HREF="spgist.html" ACCESSKEY="P" >Prev</A ></TD ><TD WIDTH="34%" ALIGN="center" VALIGN="top" ><A HREF="index.html" ACCESSKEY="H" >Home</A ></TD ><TD WIDTH="33%" ALIGN="right" VALIGN="top" ><A HREF="spgist-extensibility.html" ACCESSKEY="N" >Next</A ></TD ></TR ><TR ><TD WIDTH="33%" ALIGN="left" VALIGN="top" >SP-GiST Indexes</TD ><TD WIDTH="34%" ALIGN="center" VALIGN="top" ><A HREF="spgist.html" ACCESSKEY="U" >Up</A ></TD ><TD WIDTH="33%" ALIGN="right" VALIGN="top" >Extensibility</TD ></TR ></TABLE ></DIV ></BODY ></HTML >
