Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.sai.msu.su/~megera/postgres/gist/tree/README.tree Дата изменения: Wed Feb 27 20:41:01 2002 Дата индексирования: Sat Dec 22 07:19:40 2007 Кодировка: koi8-r Поисковые слова: молодые звезды

ТИПЫ

Под tree понимается два типа: entree (enumerated tree) & bitree (bit tree).
Соответствующие типы entreequery & bitreequery.

tree - тип, представляющий ноду дерева. Представляет собой
путь подереву от корня. Путь указывается номером в каждом узле.
Таким образом, запись '3.4' означает 4-го ребенка 3-его ребенка корня.
Нумерация в каждом уровне начинается с 1.
Максимальное количество детей - 65535 для entree, для
bitree - определяется при компиляции, доступные значения -
8,16,32(по умолчанию),64.
Тип является сортируемым в порядке прямого обхода дерева.
treequery - тип, представляющий маску ноды дерева. Отличается от tree
возможность указания альтернаивы в уровне. Например, запись '1.2|3'
означяет 2-го или 3-го ребенка 1-го ребенка корня, а '1.*.4|5' - 4-го
или 5-го ребенка произвольного ребенка 1-го ребенка корня. Вместе
с тем, приведенные выше примеры соответствуют и нодам, потомкам указанных.
Если это не желательно, можно это указать так: '1.2|3.0' и '1.*.4|5.0'
соответственно.

ОПЕРАЦИИ

Над типом tree определены следующие операции: <,>,<=,>=,= и <>.
Так же возможны операции с масками:
tree <* treequery
treequery >* tree
Последние две операции возвращают TRUE, если нода tree удовлетворяет
маске treequery.
Операция
tree @> tree
возвращает TRUE, левый аргумент является предком правого или равен ему,
соответственно операция
tree <@ tree
возвращает TRUE, правый аргумент является предком левого или равен ему (
другими словами, если левый - потомок правого).

ФУНКЦИИ
entree_level(entree) и bitree_level(bitree) возвращают
уровень ноды.

entree_next(entree), bitree_next(bitree) возвращают следующую
свободную ноду.

Пример использования:
Добавить узел -
select entree_next(tid) from dmoz where tid <* '1.2.3.*.0' order by tid
desc limit 1;

ИНДЕКСЫ
Тип tree поддерживает два типа индексов:
B-Tree - ускоряет операции <,>,<=,>= и =. Поддержка всех
особенностей и свойст штатного Btree - уникальные индексы,
Merge-join и тд
GiST - ускоряет операции <,>,<=,>=,=,*>,<*,@> и <@

МАССИВЫ tree
Над массивами типа tree определены операции:
tree[] => tree
tree <= tree[]
tree[] <* treequery
treequery *> tree[]
Первые две операции возвращают true, если в массиве есть запись,
равная другому операнду операции, оставшиеся возвращают true, если в
массиве есть запись, соответствующая указанной маске.
Эти операции могут быть ускорены путем построения GiST-индекса.

ЗАМЕЧАНИЯ
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';
эквивалентны и возвращают всех потомков узла 1.1.
2 Вставка в GiST в несколько раз медленнее, чем в B-Tree, но по
скорости выборки GiST уступает максимум в 1.5 раза B-Tree.

ПРИМЕРЫ:
create table dmoz (
nodename text, -- название ноды
nodepath text, -- путь к ноде
intid int, -- уникальный идентификатор
id entree
);

Получить всех детей узла
select * from dmoz where id <* '1.2.3.*.0';

Получить всех наследников узла
select * from dmoz where id <* '1.2.3' and id != '1.2.3';

Получить всех детей узла с подсчетом всех их наследников
select *,
(
select count(*)-1 from dmoz as d
where d.id <* entree2query(dmoz.id)
) as descentcount
from dmoz where id <* '1.2.3.*.0';