summaryrefslogtreecommitdiffstats
path: root/doc/src/sgml/html/spgist-intro.html
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-04 12:17:33 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-04 12:17:33 +0000
commit5e45211a64149b3c659b90ff2de6fa982a5a93ed (patch)
tree739caf8c461053357daa9f162bef34516c7bf452 /doc/src/sgml/html/spgist-intro.html
parentInitial commit. (diff)
downloadpostgresql-15-5e45211a64149b3c659b90ff2de6fa982a5a93ed.tar.xz
postgresql-15-5e45211a64149b3c659b90ff2de6fa982a5a93ed.zip
Adding upstream version 15.5.upstream/15.5
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'doc/src/sgml/html/spgist-intro.html')
-rw-r--r--doc/src/sgml/html/spgist-intro.html34
1 files changed, 34 insertions, 0 deletions
diff --git a/doc/src/sgml/html/spgist-intro.html b/doc/src/sgml/html/spgist-intro.html
new file mode 100644
index 0000000..b676795
--- /dev/null
+++ b/doc/src/sgml/html/spgist-intro.html
@@ -0,0 +1,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 15.5 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</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 15.5 Documentation">Home</a></td><td width="40%" align="right" valign="top"> 69.2. Built-in Operator Classes</td></tr></table></div></body></html> \ No newline at end of file