Инфраструктура интервальных деревьев
Инфраструктура интервального дерева состоит из трех хранимых процедур, двух триггеров, двух индексов, одного ограничения и одного исключения. Имена этих объектов формируются по определенной схеме. В таблице ниже даны примеры имен для стандартного отношения из эталонной базы данных и для пользовательской таблицы.
| Описание объекта | Таблица 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>
