Skip to content

Commit cb953d8

Browse files
hlinnakahlinnaka
committed
Use the term "radix tree" instead of "suffix tree" for SP-GiST text opclass.
What we have implemented is a radix tree (or a radix trie or a patricia trie), but the docs and code comments incorrectly called it a "suffix tree". Alexander Korotkov
1 parent 20c00ca commit cb953d8

File tree

9 files changed

+201
-201
lines changed

9 files changed

+201
-201
lines changed

‎doc/src/sgml/indices.sgml

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -267,7 +267,7 @@ SELECT * FROM places ORDER BY location <-> point '(101,456)' LIMIT 10;
267267
SP-GiST indexes, like GiST indexes, offer an infrastructure that supports
268268
various kinds of searches. SP-GiST permits implementation of a wide range
269269
of different non-balanced disk-based data structures, such as quadtrees,
270-
k-d trees, and suffix trees (tries). As an example, the standard distribution of
270+
k-d trees, and radix trees (tries). As an example, the standard distribution of
271271
<productname>PostgreSQL</productname> includes SP-GiST operator classes
272272
for two-dimensional points, which support indexed
273273
queries using these operators:

‎doc/src/sgml/spgist.sgml

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@
1515
<acronym>SP-GiST</acronym> is an abbreviation for space-partitioned
1616
<acronym>GiST</acronym>. <acronym>SP-GiST</acronym> supports partitioned
1717
search trees, which facilitate development of a wide range of different
18-
non-balanced data structures, such as quad-trees, k-d trees, and suffix
18+
non-balanced data structures, such as quad-trees, k-d trees, and radix
1919
trees (tries). The common feature of these structures is that they
2020
repeatedly divide the search space into partitions that need not be
2121
of equal size. Searches that are well matched to the partitioning rule
@@ -81,9 +81,9 @@
8181
A node contains a downlink that leads to either another, lower-level inner
8282
tuple, or a short list of leaf tuples that all lie on the same index page.
8383
Each node has a <firstterm>label</> that describes it; for example,
84-
in a suffix tree the node label could be the next character of the string
84+
in a radix tree the node label could be the next character of the string
8585
value. Optionally, an inner tuple can have a <firstterm>prefix</> value
86-
that describes all its members. In a suffix tree this could be the common
86+
that describes all its members. In a radix tree this could be the common
8787
prefix of the represented strings. The prefix value is not necessarily
8888
really a prefix, but can be any data needed by the operator class;
8989
for example, in a quad-tree it can store the central point that the four
@@ -636,7 +636,7 @@ typedef struct spgLeafConsistentOut
636636
<para>
637637
Individual leaf tuples and inner tuples must fit on a single index page
638638
(8KB by default). Therefore, when indexing values of variable-length
639-
data types, long values can only be supported by methods such as suffix
639+
data types, long values can only be supported by methods such as radix
640640
trees, in which each level of the tree includes a prefix that is short
641641
enough to fit on a page, and the final leaf level includes a suffix also
642642
short enough to fit on a page. The operator class should set
@@ -740,7 +740,7 @@ typedef struct spgLeafConsistentOut
740740
<para>
741741
The <productname>PostgreSQL</productname> source distribution includes
742742
several examples of index operator classes for
743-
<acronym>SP-GiST</acronym>. The core system currently provides suffix
743+
<acronym>SP-GiST</acronym>. The core system currently provides radix
744744
trees over text columns and two types of trees over points: quad-tree and
745745
k-d tree. Look into <filename>src/backend/access/spgist/</> to see the
746746
code.

‎src/backend/access/spgist/README

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@ src/backend/access/spgist/README
22

33
SP-GiST is an abbreviation of space-partitioned GiST. It provides a
44
generalized infrastructure for implementing space-partitioned data
5-
structures, such as quadtrees, k-d trees, and suffix trees (tries). When
5+
structures, such as quadtrees, k-d trees, and radix trees (tries). When
66
implemented in main memory, these structures are usually designed as a set of
77
dynamically-allocated nodes linked by pointers. This is not suitable for
88
direct storing on disk, since the chains of pointers can be rather long and
@@ -56,18 +56,18 @@ Inner tuple consists of:
5656

5757
optional prefix value - all successors must be consistent with it.
5858
Example:
59-
suffix tree - prefix value is a common prefix string
59+
radix tree - prefix value is a common prefix string
6060
quad tree - centroid
6161
k-d tree - one coordinate
6262

6363
list of nodes, where node is a (label, pointer) pair.
64-
Example of a label: a single character for suffix tree
64+
Example of a label: a single character for radix tree
6565

6666
Leaf tuple consists of:
6767

6868
a leaf value
6969
Example:
70-
suffix tree - the rest of string (postfix)
70+
radix tree - the rest of string (postfix)
7171
quad and k-d tree - the point itself
7272

7373
ItemPointer to the heap
@@ -122,7 +122,7 @@ space is as good as we can easily make it.
122122
(2) Current implementation allows to do picksplit and insert a new leaf tuple
123123
in one operation, if the new list of leaf tuples fits on one page. It's
124124
always possible for trees with small nodes like quad tree or k-d tree, but
125-
suffix trees may require another picksplit.
125+
radix trees may require another picksplit.
126126

127127
(3) Addition of node must keep size of inner tuple small enough to fit on a
128128
page. After addition, inner tuple could become too large to be stored on
@@ -132,14 +132,14 @@ another page, we can't change the numbers of other tuples on the page, else
132132
we'd make downlink pointers to them invalid. To prevent that, SP-GiST leaves
133133
a "placeholder" tuple, which can be reused later whenever another tuple is
134134
added to the page. See also Concurrency and Vacuum sections below. Right now
135-
only suffix trees could add a node to the tuple; quad trees and k-d trees
135+
only radix trees could add a node to the tuple; quad trees and k-d trees
136136
make all possible nodes at once in PickSplitFn() call.
137137

138138
(4) Prefix value could only partially match a new value, so the SplitTuple
139139
action allows breaking the current tree branch into upper and lower sections.
140140
Another way to say it is that we can split the current inner tuple into
141141
"prefix" and "postfix" parts, where the prefix part is able to match the
142-
incoming new value. Consider example of insertion into a suffix tree. We use
142+
incoming new value. Consider example of insertion into a radix tree. We use
143143
the following notation, where tuple's id is just for discussion (no such id
144144
is actually stored):
145145

‎src/backend/access/spgist/spgtextproc.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
/*-------------------------------------------------------------------------
22
*
33
* spgtextproc.c
4-
* implementation of compressed-suffix tree over text
4+
* implementation of radix tree (compressed trie) over text
55
*
66
*
77
* Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
@@ -23,7 +23,7 @@
2323

2424

2525
/*
26-
* In the worst case, a inner tuple in a text suffix tree could have as many
26+
* In the worst case, a inner tuple in a text radix tree could have as many
2727
* as 256 nodes (one for each possible byte value). Each node can take 16
2828
* bytes on MAXALIGN=8 machines. The inner tuple must fit on an index page
2929
* of size BLCKSZ. Rather than assuming we know the exact amount of overhead

‎src/include/catalog/pg_proc.h

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -4700,15 +4700,15 @@ DATA(insert OID = 4026 ( spg_kd_inner_consistent PGNSP PGUID 12 1 0 0 0 f f f f
47004700
DESCR("SP-GiST support for k-d tree over point");
47014701

47024702
DATA(insert OID = 4027 ( spg_text_config PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_text_config _null_ _null_ _null_ ));
4703-
DESCR("SP-GiST support for suffix tree over text");
4703+
DESCR("SP-GiST support for radix tree over text");
47044704
DATA(insert OID = 4028 ( spg_text_choose PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_text_choose _null_ _null_ _null_ ));
4705-
DESCR("SP-GiST support for suffix tree over text");
4705+
DESCR("SP-GiST support for radix tree over text");
47064706
DATA(insert OID = 4029 ( spg_text_picksplit PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_text_picksplit _null_ _null_ _null_ ));
4707-
DESCR("SP-GiST support for suffix tree over text");
4707+
DESCR("SP-GiST support for radix tree over text");
47084708
DATA(insert OID = 4030 ( spg_text_inner_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_text_inner_consistent _null_ _null_ _null_ ));
4709-
DESCR("SP-GiST support for suffix tree over text");
4709+
DESCR("SP-GiST support for radix tree over text");
47104710
DATA(insert OID = 4031 ( spg_text_leaf_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "2281 2281" _null_ _null_ _null_ _null_ spg_text_leaf_consistent _null_ _null_ _null_ ));
4711-
DESCR("SP-GiST support for suffix tree over text");
4711+
DESCR("SP-GiST support for radix tree over text");
47124712

47134713
DATA(insert OID = 3469 ( spg_range_quad_config PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_range_quad_config _null_ _null_ _null_ ));
47144714
DESCR("SP-GiST support for quad tree over range");

0 commit comments

Comments
 (0)