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