Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitcb953d8

Browse files
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 patriciatrie), but the docs and code comments incorrectly called it a "suffix tree".Alexander Korotkov
1 parent20c00ca commitcb953d8

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, andsuffix trees (tries). As an example, the standard distribution of
270+
k-d trees, andradix 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, andsuffix
18+
non-balanced data structures, such as quad-trees, k-d trees, andradix
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 asuffix tree the node label could be the next character of the string
84+
in aradix 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 asuffix tree this could be the common
86+
that describes all its members. In aradix 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 assuffix
639+
data types, long values can only be supported by methods such asradix
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 providessuffix
743+
<acronym>SP-GiST</acronym>. The core system currently providesradix
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, andsuffix trees (tries). When
5+
structures, such as quadtrees, k-d trees, andradix 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 forsuffix tree
64+
Example of a label: a single character forradix 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-
onlysuffix trees could add a node to the tuple; quad trees and k-d trees
135+
onlyradix 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 asuffix tree. We use
142+
incoming new value. Consider example of insertion into aradix 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 ofcompressed-suffix tree over text
4+
* implementation ofradix 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 textsuffix tree could have as many
26+
* In the worst case, a inner tuple in a textradix 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_consistentPGNSP PGUID 12 1 0 0 0 f f f f
47004700
DESCR("SP-GiST support for k-d tree over point");
47014701

47024702
DATA(insertOID=4027 (spg_text_configPGNSPPGUID121000fffftfi202278"2281 2281"_null__null__null__null_spg_text_config_null__null__null_ ));
4703-
DESCR("SP-GiST support forsuffix tree over text");
4703+
DESCR("SP-GiST support forradix tree over text");
47044704
DATA(insertOID=4028 (spg_text_choosePGNSPPGUID121000fffftfi202278"2281 2281"_null__null__null__null_spg_text_choose_null__null__null_ ));
4705-
DESCR("SP-GiST support forsuffix tree over text");
4705+
DESCR("SP-GiST support forradix tree over text");
47064706
DATA(insertOID=4029 (spg_text_picksplitPGNSPPGUID121000fffftfi202278"2281 2281"_null__null__null__null_spg_text_picksplit_null__null__null_ ));
4707-
DESCR("SP-GiST support forsuffix tree over text");
4707+
DESCR("SP-GiST support forradix tree over text");
47084708
DATA(insertOID=4030 (spg_text_inner_consistentPGNSPPGUID121000fffftfi202278"2281 2281"_null__null__null__null_spg_text_inner_consistent_null__null__null_ ));
4709-
DESCR("SP-GiST support forsuffix tree over text");
4709+
DESCR("SP-GiST support forradix tree over text");
47104710
DATA(insertOID=4031 (spg_text_leaf_consistentPGNSPPGUID121000fffftfi2016"2281 2281"_null__null__null__null_spg_text_leaf_consistent_null__null__null_ ));
4711-
DESCR("SP-GiST support forsuffix tree over text");
4711+
DESCR("SP-GiST support forradix tree over text");
47124712

47134713
DATA(insertOID=3469 (spg_range_quad_configPGNSPPGUID121000fffftfi202278"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)
[8]ページ先頭
©2009-2025 Movatter.jp