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

Материал из GedeminWiki
Перейти к: навигация, поиск

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

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

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

Триггер отслеживает изменение поля PARENT, т.е. перемещение элемента дерева в другую ветвь или на корневой уровень. Логика действий такая же как и при вставке записи. Дополнительно выполняется проверка на зацикливание, т.е. когда родителя пытаются вставить в один из подуровней потомка. Обратите внимание, как с помощью переменной контекста транзакции LBRB_UNLOCK мы запрещаем несанкционирование редактирование границ элемента. 

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

Процедура определения границ интервала

На вход передается идентификатор родителя и границы существующего интервала вставляемого элемента. Если идет вставка новой записи — передаются границы -1, -1. Задача процедуры — найти свободный промежуток нужной ширины или раздвинуть родительский интервал. Возвращаются значения левой и правой границы интервала. 

CREATE OR ALTER PROCEDURE GD_P_EL_CONTACT (
    PARENT INTEGER,
    LB2 INTEGER,
    RB2 INTEGER)
RETURNS (
    LEFTBORDER INTEGER,
    RIGHTBORDER INTEGER)
AS
DECLARE variable R INTEGER = NULL;
DECLARE variable L INTEGER = NULL;
DECLARE variable PREV INTEGER;
DECLARE variable LCHLD INTEGER = NULL;
DECLARE variable RCHLD INTEGER = NULL;
DECLARE variable DELTA INTEGER;
DECLARE variable DIST INTEGER;
DECLARE variable DIFF INTEGER;
DECLARE variable WASUNLOCK INTEGER;
BEGIN
  IF (:LB2 = -1 AND :RB2 = -1) THEN
    Delta = CAST(COALESCE(RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_DELTA'), '10') AS INTEGER);
  ELSE
    Delta = :RB2 - :LB2;
 
  SELECT lb, rb
  FROM GD_CONTACT
  WHERE id = :Parent
  INTO :L, :R;
 
  IF (:L IS NULL) THEN
    EXCEPTION tree_e_invalid_parent 'Invalid parent specified.';
 
  Prev = :L + 1;
  LeftBorder = NULL;
 
  FOR SELECT lb, rb FROM GD_CONTACT WHERE parent = :Parent ORDER BY lb ASC INTO :LChld, :RChld
  DO BEGIN
    IF ((:LChld - :Prev) > :Delta) THEN 
    BEGIN
      LeftBorder = :Prev;
      LEAVE;
    END ELSE
      Prev = :RChld + 1;
  END
 
  LeftBorder = COALESCE(:LeftBorder, :Prev);
  RightBorder = :LeftBorder + :Delta;
 
  WasUnlock = RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK');
  IF (:WasUnlock IS NULL) THEN
     RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', 1);
 
  IF (:RightBorder >= :R) THEN
  BEGIN
    Diff = :R - :L;
    IF (:RightBorder >= (:R + :Diff)) THEN
      Diff = :RightBorder - :R + 1;
 
    IF (:Delta < 1000) THEN
      Diff = :Diff + :Delta * 10;
    ELSE
      Diff = :Diff + 10000;
 
    /* Сдвигаем все интервалы справа */
    UPDATE GD_CONTACT SET lb = lb + :Diff, rb = rb + :Diff
      WHERE lb > :R;
 
    /* Расширяем родительские интервалы */
    UPDATE GD_CONTACT SET rb = rb + :Diff
      WHERE lb <= :L AND rb >= :R;
 
    IF (:LB2 <> -1 AND :RB2 <> -1) THEN
    BEGIN
      IF (:LB2 > :R) THEN
      BEGIN
        LB2 = :LB2 + :Diff;
        RB2 = :RB2 + :Diff;
      END
      Dist = :LeftBorder - :LB2;
      UPDATE GD_CONTACT SET lb = lb + :Dist, rb = rb + :Dist 
        WHERE lb > :LB2 AND rb <= :RB2;
    END
  END ELSE
  BEGIN
    IF (:LB2 <> -1 AND :RB2 <> -1) THEN
    BEGIN
      Dist = :LeftBorder - :LB2;
      UPDATE GD_CONTACT SET lb = lb + :Dist, rb = rb + :Dist 
        WHERE lb > :LB2 AND rb <= :RB2;
    END
  END
 
  IF (:WasUnlock IS NULL) THEN
    RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', NULL);
END

Процедура перестроения дерева

В процессе перестроения интервалы изменяются следующим образом:

  • Все листья получают ширину из переменной контекста транзации LBRB_DELTA. Если последняя не задана, то принимается ширина 10.
  • Ширина остальных узлов определяется как сумма интервалов непосредственных потомков. 
CREATE OR ALTER PROCEDURE GD_P_RESTRUCT_CONTACT
AS
DECLARE variable CURRENTINDEX INTEGER;
DECLARE variable CHILDKEY INTEGER;
DECLARE variable WASUNLOCK INTEGER;
BEGIN
  CurrentIndex = 1;
 
  WasUnlock = RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK');
  IF (:WasUnlock IS NULL) THEN
    RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', 1);
 
  /* Для всех корневых элементов ... */
  FOR
    SELECT id
    FROM GD_CONTACT
    WHERE parent IS NULL
    INTO :ChildKey
  DO
  BEGIN
    /* ... меняем границы детей */
    EXECUTE PROCEDURE GD_p_gchc_CONTACT (:ChildKey, :CurrentIndex)
      RETURNING_VALUES :CurrentIndex;
  END
 
  IF (:WasUnlock IS NULL) THEN
    RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', NULL);
END

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

Процедура рекурсивного перестроения указанного элемента дерева

Данная процедура вызывается из процедуры перестроения дерева (см. выше) и не предназначена для самостоятельного использования. На вход передается идентификатор элемента и новое значение левой границы. Процедура действует для поддерева следующим образом:

  • Все листья получают ширину из переменной контекста транзации LBRB_DELTA. Если последняя не задана, то принимается ширина 10.
  • Ширина остальных узлов определяется как сумма интервалов непосредственных потомков. 
CREATE OR ALTER PROCEDURE GD_P_GCHC_CONTACT (
    PARENT INTEGER,
    FIRSTINDEX INTEGER)
RETURNS (
    LASTINDEX INTEGER)
AS
DECLARE variable CHILDKEY INTEGER;
BEGIN
  LastIndex = :FirstIndex + 1;
 
  /* Изменяем границы детей */
  FOR
    SELECT id
    FROM GD_CONTACT
    WHERE parent = :Parent
    INTO :ChildKey
  DO
  BEGIN
    EXECUTE PROCEDURE GD_p_gchc_CONTACT (:ChildKey, :LastIndex)
      RETURNING_VALUES :LastIndex;
  END
 
  LastIndex = :LastIndex + CAST(COALESCE(RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_DELTA'), '10') AS INTEGER) - 1;
 
  /* Изменяем границы родителя */
  UPDATE GD_CONTACT SET lb = :FirstIndex + 1, rb = :LastIndex
    WHERE id = :Parent;
END

См. также

Источник — «https://gsbelarus.com/gs/wiki/index.php?title=%D0%98%D0%BD%D1%84%D1%80%D0%B0%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D0%B2%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D0%B5%D0%B2&oldid=4439»
Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты