Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.sai.msu.su/~megera/postgres/gist/tree/README.tree.english Дата изменения: Mon Jul 1 19:44:12 2002 Дата индексирования: Sat Dec 22 07:33:23 2007 Кодировка: Поисковые слова: quasar

TYPES

Trees are represented by two types: entree (enumerated tree) and
bitree (bit tree). The corresponding query types are entreequery and
bitreequery.

tree -
The tree type represents a node of a tree as a path from the root
to the node. A path is generated using each node's number. Thus,
the record by '3.4' indicates the 4th child of the 3rd child of
the root. Numbers at each level begin at 1. For the entree tree
type, the maximum number of children for each node is 65535. For
the bitree tree type, the maximum number of children for each node
is determined during compilation and valid values are 8,16,32
(default) and 64. The type is sorted in order of the direct
traverse of the tree.

treequery -
represents a tree node pattern that is used for queries. It's the
same type as a tree but with the possibility to use some sort of
regular expression. For example, record '1.2|3' indicates the 2nd
or 3rd child of the 1st child of the root, and '1.*.4|5' indicates
the 4th or 5th child of any child of the 1st child of the root.
The examples given above correspond to all descendant nodes. If
this is not desirable, it is possible to limit the depth of the
pattern matching. For instance: '1.2|3.0' and '1.*.4|5.0',
respectively.

OPERATIONS

The following operations are determined for the tree types:
<,>,<=,>=,= and <>.
Also, it's possible to match patterns:
tree <* treequery
treequery >* tree
The last two operations return TRUE if the node matches the
treequery pattern. Operation
tree @> tree
returns TRUE if the left argument is the ancestor of the right or
equal to it. The respective operation
tree <@ tree
returns TRUE if the right argument is the ancestor of the left or
equal to it (the left argument is the descendant of the right).

FUNCTIONS

entree_level(entree) and bitree_level(bitree) return the level of
node.

entree_next(entree) and bitree_next(bitree) return the next free node.

Example of how to add a node:
select entree_next(tid) from dmoz where tid <* '1.2.3.*.0' order
by tid desc limit 1;

INDICES

Type tree supports two types of indices:
B-Tree - accelerates operations:
<,>,<=,>= and =.
Supports all features of regular B-tree - unique indices,
merge-join,...
GiST - accelerates operations:
<,>,<=,>=,=,*>,<*,@> and <@

Arrays of tree

The following operations are determined for arrays of tree:
tree[] => tree
tree <= tree[]
tree[] <* treequery
treequery *> tree[]
The first two operations return true if in the array there is a
record equal to another operand of the operations. The last 2
operations return true if there is a record in the array which
corresponds to the given pattern. These operations can be
accelerated by constructing GiST-indices.

NOTICES

1. The following selects are equivalent and return all descendants
of node 1.1:
select * from treetbl where treefld >= '1.1' and treefld < '1.2';
select * from treetbl where treefld <* '1.1';
select id from dmoz where id <@ '1.1';

2. Insertion into GiST is several times slower than insertion
into B-Tree, while selection performance is at most 1.5 slower.

EXAMPLES:

create table dmoz
(
nodename text, -- the name of node
nodepath text, -- path to node
intid int, -- the unique identifier
id entree
);

To obtain all children of the node:
select * from dmoz where id <* '1.2.3.*.0';

To obtain all decendants of the node:
select * from dmoz where id <* '1.2.3' and id != '1.2.3';

To obtain all children of the node with the calculation of all
their descendants:
select *,
(
select count(*)-1 from dmoz as d
where d.id <* entree2query(dmoz.id)
) as descentcount
from dmoz where id <* '1.2.3.*.0';