<?xml version="1.0" encoding="UTF-8" standalone="no"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>65.1. Introduction</title><link rel="stylesheet" type="text/css" href="stylesheet.css" /><link rev="made" href="pgsql-docs@lists.postgresql.org" /><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><link rel="prev" href="spgist.html" title="Chapter 65. SP-GiST Indexes" /><link rel="next" href="spgist-builtin-opclasses.html" title="65.2. Built-in Operator Classes" /></head><body><div xmlns="http://www.w3.org/TR/xhtml1/transitional" class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">65.1. Introduction</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="spgist.html" title="Chapter 65. SP-GiST Indexes">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="spgist.html" title="Chapter 65. SP-GiST Indexes">Up</a></td><th width="60%" align="center">Chapter 65. SP-GiST Indexes</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 11.5 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="spgist-builtin-opclasses.html" title="65.2. Built-in Operator Classes">Next</a></td></tr></table><hr></hr></div><div class="sect1" id="SPGIST-INTRO"><div class="titlepage"><div><div><h2 class="title" style="clear: both">65.1. Introduction</h2></div></div></div><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 class="ulink" href="https://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 class="ulink" href="http://www.sai.msu.su/~megera/wiki/spgist_dev" target="_top">web site</a>. </p></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="spgist.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="spgist.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="spgist-builtin-opclasses.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 65. SP-GiST Indexes </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> 65.2. Built-in Operator Classes</td></tr></table></div></body></html>
