Инфраструктура интервальных деревьев
SYSDBA (обсуждение | вклад) |
SYSDBA (обсуждение | вклад) |
||
| Строка 38: | Строка 38: | ||
| | | | ||
|} | |} | ||
| + | |||
| + | === Триггер на вставку записи === | ||
| + | |||
| + | Если вставка идет в корень дерева (PARENT IS NULL), то пытаемся отыскать местечко чтобы втиснуться между существующими корневыми элементами. Если свободного места нет -- добавляем элемент правее самого правого. Поиск "пробела" необходим, чтобы управлять скоростью растягивания дерева вправо при массовых операциях добавления/удаления элементов. | ||
| + | |||
| + | Шириной создаваемого интервала можно управлять с помощью переменной контекста транзакции '''LBRB_DELTA'''. По умолчанию принимается значение 10. | ||
| + | |||
| + | При вставке в существующий элемент -- вызываем процедуру GD_p_el_CONTACT, которая подыщет нам свободное место и, при необходимости, расширит родительский интервал. | ||
| + | |||
| + | <syntaxhighligh lang="SQL"> | ||
| + | CREATE OR ALTER trigger gd_bi_contact10 for gd_contact | ||
| + | active before insert position 32000 | ||
| + | AS | ||
| + | DECLARE VARIABLE D INTEGER; | ||
| + | DECLARE VARIABLE L INTEGER; | ||
| + | DECLARE VARIABLE R INTEGER; | ||
| + | DECLARE VARIABLE Prev INTEGER; | ||
| + | BEGIN | ||
| + | IF (NEW.parent IS NULL) THEN | ||
| + | BEGIN | ||
| + | D = CAST(COALESCE(RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_DELTA'), '10') AS INTEGER); | ||
| + | Prev = 1; | ||
| + | NEW.lb = NULL; | ||
| + | |||
| + | FOR SELECT lb, rb FROM GD_CONTACT WHERE parent IS NULL ORDER BY lb INTO :L, :R | ||
| + | DO BEGIN | ||
| + | IF ((:L - :Prev) > :D) THEN | ||
| + | BEGIN | ||
| + | NEW.lb = :Prev; | ||
| + | LEAVE; | ||
| + | END ELSE | ||
| + | Prev = :R + 1; | ||
| + | END | ||
| + | |||
| + | NEW.lb = COALESCE(NEW.lb, :Prev); | ||
| + | NEW.rb = NEW.lb + :D; | ||
| + | END ELSE | ||
| + | BEGIN | ||
| + | EXECUTE PROCEDURE GD_p_el_CONTACT (NEW.parent, -1, -1) | ||
| + | RETURNING_VALUES NEW.lb, NEW.rb; | ||
| + | END | ||
| + | END | ||
| + | </syntaxhighlight> | ||
==== См. также ==== | ==== См. также ==== | ||
Версия 19:34, 2 апреля 2011
Инфраструктура интервального дерева состоит из трех хранимых процедур, двух триггеров, двух индексов, одного ограничения и одного исключения. Имена этих объектов формируются по определенной схеме. В таблице ниже даны примеры имен для стандартного отношения из эталонной базы данных и для пользовательской таблицы.
| Описание объекта | Таблица GD_CONTACT | Таблица USR$FA_GROUP |
|---|---|---|
| Процедура вычисляет границы интервала для дочернего элемента. При необходимости родительский интервал расширяется. На вход передается родитель и границы существующего интервала элемента. Если это новый элемент, передаются границы -1, -1. | GD_P_EL_CONTACT | |
| Процедура | GD_P_GCHC_CONTACT | |
| Процедура сжимает интервалы всех элементов в дереве. | GD_P_RESTRUCT_CONTACT | |
| Триггер на вставку записи | GD_BI_CONTACT10 | |
| Триггер на изменение записи | GD_BU_CONTACT10 | |
| Индекс | ||
| Индекс | ||
| Исключение |
Триггер на вставку записи
Если вставка идет в корень дерева (PARENT IS NULL), то пытаемся отыскать местечко чтобы втиснуться между существующими корневыми элементами. Если свободного места нет -- добавляем элемент правее самого правого. Поиск "пробела" необходим, чтобы управлять скоростью растягивания дерева вправо при массовых операциях добавления/удаления элементов.
Шириной создаваемого интервала можно управлять с помощью переменной контекста транзакции LBRB_DELTA. По умолчанию принимается значение 10.
При вставке в существующий элемент -- вызываем процедуру GD_p_el_CONTACT, которая подыщет нам свободное место и, при необходимости, расширит родительский интервал.
<syntaxhighligh lang="SQL"> CREATE OR ALTER trigger gd_bi_contact10 for gd_contact active before insert position 32000 AS
DECLARE VARIABLE D INTEGER; DECLARE VARIABLE L INTEGER; DECLARE VARIABLE R INTEGER; DECLARE VARIABLE Prev INTEGER;
BEGIN
IF (NEW.parent IS NULL) THEN
BEGIN
D = CAST(COALESCE(RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_DELTA'), '10') AS INTEGER);
Prev = 1;
NEW.lb = NULL;
FOR SELECT lb, rb FROM GD_CONTACT WHERE parent IS NULL ORDER BY lb INTO :L, :R
DO BEGIN
IF ((:L - :Prev) > :D) THEN
BEGIN
NEW.lb = :Prev;
LEAVE;
END ELSE
Prev = :R + 1;
END
NEW.lb = COALESCE(NEW.lb, :Prev);
NEW.rb = NEW.lb + :D;
END ELSE
BEGIN
EXECUTE PROCEDURE GD_p_el_CONTACT (NEW.parent, -1, -1)
RETURNING_VALUES NEW.lb, NEW.rb;
END
END </syntaxhighlight>
