Инфраструктура интервальных деревьев

Инфраструктура интервального дерева состоит из трех хранимых процедур, двух триггеров, двух индексов, одного ограничения и одного исключения. Имена этих объектов формируются по определенной схеме. В таблице ниже даны примеры имен для стандартного отношения из эталонной базы данных и для пользовательской таблицы.

Описание объекта	Таблица 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

Триггер на изменение записи

CREATE OR ALTER TRIGGER gd_bu_contact10 FOR gd_contact
active BEFORE UPDATE POSITION 32000
AS
  DECLARE VARIABLE OldDelta  INTEGER;
  DECLARE VARIABLE D         INTEGER;
  DECLARE VARIABLE L         INTEGER;
  DECLARE VARIABLE R         INTEGER;
  DECLARE VARIABLE Prev      INTEGER;
  DECLARE VARIABLE WasUnlock INTEGER;
BEGIN
  IF (NEW.parent IS DISTINCT FROM OLD.parent) THEN
  BEGIN
    /* Делаем проверку на зацикливание */
    IF (EXISTS (SELECT * FROM GD_CONTACT
          WHERE id = NEW.parent AND lb >= OLD.lb AND rb <= OLD.rb)) THEN
      EXCEPTION tree_e_invalid_parent 'Attempt to cycle branch in table GD_CONTACT.';
 
    IF (NEW.parent IS NULL) THEN
    BEGIN
      D = OLD.rb - OLD.lb;
      Prev = 1;
      NEW.lb = NULL;
 
      FOR SELECT lb, rb FROM GD_CONTACT WHERE parent IS NULL ORDER BY lb ASC 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;
 
      /* Определяем величину сдвига */
      OldDelta = NEW.lb - OLD.lb;
      /* Сдвигаем границы детей */
      WasUnlock = RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK');
      IF (:WasUnlock IS NULL) THEN
        RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', 1);
      UPDATE GD_CONTACT SET lb = lb + :OldDelta, rb = rb + :OldDelta
        WHERE lb > OLD.lb AND rb <= OLD.rb;
      IF (:WasUnlock IS NULL) THEN
        RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', NULL);
    END ELSE
      EXECUTE PROCEDURE GD_p_el_CONTACT (NEW.parent, OLD.lb, OLD.rb)
        RETURNING_VALUES NEW.lb, NEW.rb;
  END ELSE
  BEGIN
    IF ((NEW.rb <> OLD.rb) OR (NEW.lb <> OLD.lb)) THEN
    BEGIN
      IF (RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK') IS NULL) THEN
      BEGIN
        NEW.lb = OLD.lb;
        NEW.rb = OLD.rb;
      END
    END
  END
 
  WHEN ANY DO
  BEGIN
    RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', NULL);
    EXCEPTION;
  END
END

См. также

• Деревья в SQL
• Issue 1709
• Issue 2384