blob: 27cfbd7e1fe4fa8d69a667f1869f03a28ebe1702 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
<?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>69.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 69. SP-GiST Indexes" /><link rel="next" href="spgist-builtin-opclasses.html" title="69.2. Built-in Operator Classes" /></head><body id="docContent" class="container-fluid col-10"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">69.1. Introduction</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="spgist.html" title="Chapter 69. SP-GiST Indexes">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="spgist.html" title="Chapter 69. SP-GiST Indexes">Up</a></td><th width="60%" align="center">Chapter 69. SP-GiST Indexes</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 16.2 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="spgist-builtin-opclasses.html" title="69.2. Built-in Operator Classes">Next</a></td></tr></table><hr /></div><div class="sect1" id="SPGIST-INTRO"><div class="titlepage"><div><div><h2 class="title" style="clear: both">69.1. Introduction <a href="#SPGIST-INTRO" class="id_link">#</a></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" title="Chapter 69. SP-GiST Indexes">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="spgist.html" title="Chapter 69. SP-GiST Indexes">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="spgist-builtin-opclasses.html" title="69.2. Built-in Operator Classes">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 69. SP-GiST Indexes </td><td width="20%" align="center"><a accesskey="h" href="index.html" title="PostgreSQL 16.2 Documentation">Home</a></td><td width="40%" align="right" valign="top"> 69.2. Built-in Operator Classes</td></tr></table></div></body></html>
|
