Соединение таблиц в запросе по условию "В иерархии" с использованием Nested Sets

Публикация № 642856

Программирование - Практика программирования

Запросы соединение таблиц иерархия в иерархии nested sets

29
Реализация метода хранения деревьев Nested Sets в 1С. Использование деревьев Nested Sets для соединения таблиц в запросах по условию "В иерархии".

В данной статья я расскажу о решении задачи, цель которой в проверке набора записей на сложные (комбинированные) условия вида "в иерархии", с акцентом на производительность решения (т.е. запросы в цикле не используем). Первая часть статьи - это постановка проблемы, вторая - это решение задачи с использованием метода Nested Sets. Если вам не интересны прелюдии, смело переходите ко второй части, там вся суть.

Часть 1. Формулирование проблемы.

Представьте себе задачу: необходимо проверить некоторый набор данных на условие иерархического вхождения его элементов (этого набора) в элементы более высокого уровня (например, группы), вот только групп может быть несколько и выбор той или иной группы также имеет определённые условия.

Чтобы было легче, вот более реальный пример (хотя пример все же выдуман, но для раскрытия темы будет вполне достаточно):

Есть справочник "Номенклатура". Справочник имеет иерархию Групп и элементов, уровень вложенности неограничен (на самом деле не важно, что это будет за иерархия: элементов или групп). Также, для произвольной группировки номенклатуры, имеется справочник "Сегменты номенклатуры". У справочника с сегментами есть табличная часть, где указывается какая номенклатура входит в данный сегмент, причем могут указываться как конкретные позиции номенклатуры, так и группы номенклатуры. Каждому сотруднику предприятия может быть указан один сегмент. Тем самым определяется доступная номенклатура, которую может заказать этот сотрудник. Сотрудники регулярно что-то заказывают, но делают это внесистемно – пишут служебки и относят их ответственному пользователю, который вводит один общий документ, где указывает сотрудников и то, что они заказывают. Документ имеет табличную часть с колонками «Сотрудник», «Номенклатура», «Количество». При проведении документа требуется реализовать проверку, которая убедится, что все заказали только то, что им разрешено.

Если не вдаваться в детали, то на первый взгляд решение задачи проблем не вызывает: взять таблицу из документа, для каждого пользователя определить сегмент и выяснить входит ли заказанная номенклатура в сегмент. Но есть нюанс. Так как в сегментах может быть определена группа, то это означает, что в запросе мы получим соединение таблиц, где проверка условия будет строится по выражению «В иерархии». Вот запрос, который бы решил задачу:

ВЫБРАТЬ

            ВТ_Заказы.Сотрудник КАК Сотрудник,

            ВТ_Заказы.Сегмент КАК Сегмент,

            ВТ_Заказы.Номенклатура КАК Номенклатура,

            СегментыСостав.Номенклатура КАК НоменклатураСегмента

ИЗ

            ВТ_Заказы КАК ВТ_Заказы

                        ЛЕВОЕ СОЕДИНЕНИЕ Справочник.Сегменты.Состав КАК СегментыСостав

                        ПО ВТ_Заказы.Сегмент = СегментыСостав.Ссылка

                                    И (ВЫБОР

                                               КОГДА СегментыСостав.Номенклатура.ЭтоГруппа

                                                           ТОГДА ВТ_Заказы.Номенклатура В ИЕРАРХИИ (СегментыСостав.Номенклатура)

                                               ИНАЧЕ ВТ_Заказы.Номенклатура = СегментыСостав.Номенклатура

                                    КОНЕЦ)

ГДЕ

            СегментыСостав.Ссылка ЕСТЬ NULL

Но 1С так делать не умеет. Выражение в скобках после оператора «В ИЕРАРХИИ» (подчеркнуто и выделено жирным) может быть либо параметром, либо вложенным подзапросом. В обоих случаях нас это не устраивает. Так как еще есть условие на равенство сегмента, соответственно в выборке может быть много сегментов с различными группами.

Можно рассмотреть решение с запросом в цикле: первый запрос вернет требуемые сегменты, затем в цикле для каждого из них получить содержимое и сделать проверку на данных из документа. Но ведь каждый знает, что запрос в цикле — это моветон, кошмар для производительности.

Другой вариант, это реализовать регистр, который будет хранить пономенклатурный состав сегмента. В целом это спасает. Вопрос только как его поддерживать в актуальном состоянии: понятное дело обновлять при записи сегмента, но также нужно следить еще и за изменением структуры в самом справочнике с номенклатурой. Этот вариант тоже отложим в сторону.

Еще есть вариант использовать механизмы СКД (как это делается для сегментов ERP/УТ), но это не чистые запросы 1С и по сути получим тот же неявный запрос в цикле.

Наш вариант другой – научить 1С работать с Nested Sets деревьями!

Часть 2. Nested Sets в 1С.

Немного теории.

Хранить иерархические структуры в базах данных можно по-разному. 1С для этого использует вариант, когда для каждого элемента указывается его родитель. Данный метод называется "Adjacency List" (переводится как "Список смежных вершин"). Такой метод конечно имеет право на жизнь и для большинства задач он вполне достаточен, но, что касается выполнения условий на вхождения в группы, то здесь он просто ужасен (что видно из описанного выше примера). 

Для задач на проверку вхождения в иерархию гораздо лучше подходит метод Nested Sets (можно перевести как "Вложенные множества"). Данный метод подразумевает, что каждый элемент хранит в себе диапазон вложенных в него элементов. Это достигается путем использования пары ключей: lgt - left key и rgt - right key (см. картинку к статье). Соотвенно, left key (левый ключ) определяет начало диапазона, а right key (правый ключ) - его конец. Откуда же берутся ключи? Для того, чтобы получить ключи нужно обойти все дерево против часовой стрелки (слева направо) начиная с его корневого элемента. Это что-то вроде задачек для детей - нарисуй домик не отрывая карандаша, только вместо домика - граф (наше дерево). Так вот, ставим карандаш в корень (получаем первый левый ключ), далее спускаемся до ближаешего крайнего левого узла (получаем левый ключ номер два), далее еще ниже до тех пор пока не дойдем до самого крайнего элемента данной (крайней левой) ветки. От этого элемента начинаем подниматься назад вверх, при этом заполняются уже правые ключи. Поднимаемся до первой развилки и опять спускаемся вниз по тем элементам где еще не были. И так далее пока не будет обрисован весь граф (всё дерево).

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

Практика.

Для реализации структуры данных, которая будет хранить дерево в формате Nested Sets подойдет регистр сведений. Если продолжить рассматривать пример из первой части статьи то, для номенклатуры можно реализовать периодический (в пределах секунды) регистр сведений "Номенклатура Nested Sets": измерение "Номенклатура" (тип спр. "Номенклатура"); ресурсы: Левый ключ (Число(10,0)), Правый ключ (Число(10,0)), Уровень(Число(10,0)).

Итоговая конфигурация (выгрузка) приложена к статье.

При добавлении новых позиции номенклатуры и удаления существующих происходит пересчет ключей в Nested Sets. Для этого в обработчики событий "При записи" и "Перед удалением" добалены вызовы соответствующих процедур: "ДобавитьУзелВМножество(Номенклатура, Отказ)" и "УдалитьУзелИзМножества(Номенклатура, Отказ)". Сами процедуры вынесены в модуль менеджера рег. сведений "Номенклатура Nested Sets".

Все действия с пересчетом ключей можно разделить на 3 вида:

  • Добавление нового узла (реализовано в процедуре "ДобавитьУзелВМножество", если условия на проверку существования узла = Ложь);
  • Перемещение узла (изменение родителя) (реализовано в процедуре "ДобавитьУзелВМножество", если условия на проверку существования узла = Истина);
  • Удаление узла (реализовано в процедуре "УдалитьУзелИзМножества")

1. При добавлении нового узла определяется родитель. Если его нет (узел добавляется в корень), то берется максимальное значение правого ключа (по всему дереву) и добавляется "1" - таким образом получается значение левого ключа нового узла. При этом остальные узлы не пересчитываются. Если родитель определен, то берется правый ключ родителя и он становится значением левого ключа нового узла. После этого происходит пересчет ключей всех узлов, стоящих "справа" от нового (что логично, все ключи сдвигаются на 2, узлы "слева" не задействуются). Правый ключ нового узла определяется как Левый ключ + 1 (ведь мы добавили всего один узел без вложенной ветки).

2. Перемещение узла самая сложная часть алгоритма. Следует разделить перемещение на 2 типа: вверх по дереву (с увеличением ключа новой позиции) и вниз по дереву (когда ключ позиции уменьшается). Перемещение всегда происходит  без добавления и удаления узлов. Существующий узел перемещается на новую позицию. Старая и новая позиции узла определяют левую и правую границы. Левая граница - ветка, на которую переместился узел при направлении перемещения "влево", либо ветка, с которой переместился узел при направлении перемещения "вправо". Правая граница - соответственно, ветка, на которую переместился узел при направлении перемещения "вправо", либо ветка, с которой переместился узел при направлении перемещения "влево".  Независимо от направления при перемещении всё множество узлов можно разделить на 5 групп: 

  1. Узлы, ключи которых не изменяются. Ведь если мы перемещаем ветку в пределах двух позиций, то все, что находится за этими позициями, не изменяется. Новые элементы не добавляются, старые не удаляются, количество элементов постоянно, вот и ключи элементов до начала левой границы смещения и после правой границы остаются прежними;
  2. Узлы, у которых изменяются 2 ключа сразу. Это узлы между левой и правой границей. При перемещении влево их индексы увеличиваются на дельту. Где дельта - это разница между правым и левым ключом перемещаемого узла плюс единица (длина ветки исходящей от узла). При перемещении вправо индексы уменьшаются на эту дельту;
  3. Узлы, у которых изменяется  правый ключ. Это узлы, которые проходят по левой границе смещения. Изменение происходит на величину дельты;
  4. Узлы, у которых изменяется левый ключ. Это узлы, которые проходят по правой границе смещения. Изменение происходит на величину дельты;
  5. Узлы, входящие в перемещаемую ветку. Их может и не быть если перемещается один только узел без вложенных элементов. Все такие узлы изменяются на величину смещения. Где смещение - это разница между старым левым ключом и новым левым ключем (длина переноса узла). Старый левый ключ - левый ключ старого положения узла, новый левый ключ - ключ нового положения. Следует учесть, что при перемещении вправо к смещеию добавляется величина дельты. В коде также используется понятие "БлижайшийПравыйКлюч" - под ним следует понимать правый ключ ближайшего элемента. Левый ключ нового узла равен "БлижайшийПравыйКлюч"  + 1.

    Стоит отметить, что в реализованном мною алгоритме не учитывается позиции, в которую перемещается узел в пределах родителя - узел всегда помещается как последний в пределах подчинения родителю. Для решения задач на вложенность элементов этого вполне достаточно.

Ниже приведен листинг процедуры "ДобавитьУзелВМножество":

Процедура ДобавитьУзелВМножество(Номенклатура, Отказ) Экспорт
    // Проверка на то, стоит ли дальше продолжать...
	Если Отказ Или Номенклатура.ДополнительныеСвойства.Свойство("НеОбновлятьУзлыВNestedSets")Тогда
		Возврат;
	КонецЕсли;
	
    // Так как на ключи завязан контроль проведения, лучше перестраховаться и выполняться чтение-записи при исключительной блокировке
	Блокировка = Новый БлокировкаДанных;
	ЭлементБлокировки = Блокировка.Добавить("РегистрСведений.НоменклатураNestedSets");
	ЭлементБлокировки.Режим = РежимБлокировкиДанных.Исключительный;
	Блокировка.Заблокировать();
	
	Запрос = Новый Запрос;
	МВТ = Новый МенеджерВременныхТаблиц;
	Запрос.МенеджерВременныхТаблиц = МВТ;
	Запрос.Текст =
    // Первая часть запроса общая: проверка существования записи (если нет, то запись новая), получение ключей родителя и текущий записи
		"ВЫБРАТЬ
		|	НоменклатураNestedSets.Номенклатура КАК Номенклатура,
		|	НоменклатураNestedSets.ЛевыйКлюч КАК ЛевыйКлюч,
		|	НоменклатураNestedSets.ПравыйКлюч КАК ПравыйКлюч,
		|	НоменклатураNestedSets.Уровень КАК Уровень
		|ПОМЕСТИТЬ ВТ_СуществующаяЗапись
		|ИЗ
		|	РегистрСведений.НоменклатураNestedSets.СрезПоследних(, Номенклатура = &Узел) КАК НоменклатураNestedSets
		|;
		|
		|////////////////////////////////////////////////////////////////////////////////
		|ВЫБРАТЬ
		|	НоменклатураNestedSets.Номенклатура КАК Номенклатура,
		|	НоменклатураNestedSets.ЛевыйКлюч КАК ЛевыйКлюч,
		|	НоменклатураNestedSets.ПравыйКлюч КАК ПравыйКлюч,
		|	НоменклатураNestedSets.Уровень КАК Уровень
		|ПОМЕСТИТЬ ВТ_ЗаписьРодителя
		|ИЗ
		|	РегистрСведений.НоменклатураNestedSets.СрезПоследних(
		|			,
		|			&РодительУказан
		|				И Номенклатура = &Родитель) КАК НоменклатураNestedSets
		|;
		|
		|////////////////////////////////////////////////////////////////////////////////
		|ВЫБРАТЬ
		|	МАКСИМУМ(НоменклатураNestedSets.ПравыйКлюч) КАК ПравыйКлюч
		|ПОМЕСТИТЬ ВТ_МаксимальныйПравыйКлюч
		|ИЗ
		|	РегистрСведений.НоменклатураNestedSets.СрезПоследних(, НЕ &РодительУказан) КАК НоменклатураNestedSets
		|;
		|
		|////////////////////////////////////////////////////////////////////////////////
		|ВЫБРАТЬ
		|	ВТ_ЗаписьРодителя.ПравыйКлюч - 1 КАК БлижайшийПравыйКлюч,
		|	ВТ_ЗаписьРодителя.Уровень + 1 КАК Уровень
		|ПОМЕСТИТЬ ВТ_НовоеПоложениеУзла
		|ИЗ
		|	ВТ_ЗаписьРодителя КАК ВТ_ЗаписьРодителя
		|ГДЕ
		|	НЕ ВТ_ЗаписьРодителя.ПравыйКлюч ЕСТЬ NULL
		|
		|ОБЪЕДИНИТЬ ВСЕ
		|
		|ВЫБРАТЬ
		|	ВТ_МаксимальныйПравыйКлюч.ПравыйКлюч,
		|	1
		|ИЗ
		|	ВТ_МаксимальныйПравыйКлюч КАК ВТ_МаксимальныйПравыйКлюч
		|ГДЕ
		|	НЕ ВТ_МаксимальныйПравыйКлюч.ПравыйКлюч ЕСТЬ NULL
		|;
		|
		|////////////////////////////////////////////////////////////////////////////////
		|ВЫБРАТЬ
		|	1 КАК Поле1
		|ИЗ
		|	ВТ_СуществующаяЗапись КАК ВТ_СуществующаяЗапись";
	Запрос.УстановитьПараметр("Узел", Номенклатура.Ссылка);
	Запрос.УстановитьПараметр("Родитель", Номенклатура.Родитель);
	Запрос.УстановитьПараметр("РодительУказан", ЗначениеЗаполнено(Номенклатура.Родитель));		
	
	Если Запрос.Выполнить().Пустой() Тогда
		// Новый узел
		Запрос.Текст =
			"ВЫБРАТЬ
			|	&Период КАК Период,
			|	НоменклатураNestedSets.Номенклатура КАК Номенклатура,
			|	ВЫБОР
			|		КОГДА НоменклатураNestedSets.ЛевыйКлюч > ВТ_ЗаписьРодителя.ПравыйКлюч
			|			ТОГДА НоменклатураNestedSets.ЛевыйКлюч + 2
			|		ИНАЧЕ НоменклатураNestedSets.ЛевыйКлюч
			|	КОНЕЦ КАК ЛевыйКлюч,
			|	НоменклатураNestedSets.ПравыйКлюч + 2 КАК ПравыйКлюч,
			|	НоменклатураNestedSets.Уровень КАК Уровень
			|ИЗ
			|	ВТ_ЗаписьРодителя КАК ВТ_ЗаписьРодителя
			|		ВНУТРЕННЕЕ СОЕДИНЕНИЕ РегистрСведений.НоменклатураNestedSets.СрезПоследних КАК НоменклатураNestedSets
			|		ПО ВТ_ЗаписьРодителя.ПравыйКлюч <= НоменклатураNestedSets.ПравыйКлюч
			|;
			|
			|////////////////////////////////////////////////////////////////////////////////
			|ВЫБРАТЬ
			|	ВТ_НовоеПоложениеУзла.БлижайшийПравыйКлюч + 1 КАК ЛевыйКлючНовогоУзла,
			|	ВТ_НовоеПоложениеУзла.Уровень КАК УровеньНовогоУзла
			|ИЗ
			|	ВТ_НовоеПоложениеУзла КАК ВТ_НовоеПоложениеУзла";
		ПериодЗаписи = ТекущаяДата();
		Запрос.УстановитьПараметр("Период", ПериодЗаписи);
		
		Пакет = Запрос.ВыполнитьПакет();
		ВыгрузкаСмещение = Пакет[0].Выгрузить(); // Данные для записи в регистр с учетом смещения ключей
		ВыборкаНовыйУзел = Пакет[1].Выбрать(); // Данные для вставки нового узла
		
		НаборЗаписей = РегистрыСведений.НоменклатураNestedSets.СоздатьНаборЗаписей();
		НаборЗаписей.Загрузить(ВыгрузкаСмещение);
		
		// Добавим в набор новый узел
		НоваяЗапись 				= НаборЗаписей.Добавить();
		НоваяЗапись.Номенклатура 	= Номенклатура.Ссылка;
		НоваяЗапись.Период 			= ПериодЗаписи;
		Если ВыборкаНовыйУзел.Следующий() Тогда
			НоваяЗапись.Уровень 		= ВыборкаНовыйУзел.УровеньНовогоУзла;
			НоваяЗапись.ЛевыйКлюч 		= ВыборкаНовыйУзел.ЛевыйКлючНовогоУзла;
			НоваяЗапись.ПравыйКлюч 		= НоваяЗапись.ЛевыйКлюч  + 1;
		Иначе
			// Первый (единственный) узел
			НоваяЗапись.Уровень 		= 1;
			НоваяЗапись.ЛевыйКлюч 		= 1;
			НоваяЗапись.ПравыйКлюч 		= 2;
		КонецЕсли;
		
		НаборЗаписей.Записать(Ложь); // Записываем с замещением, лишние записи потрем регл.заданием
	Иначе
		 // Перемещение узла
		 Запрос.Текст =
            /////////////// Определяем Смещение, Дельту, Ближайший правый ключ (см. теорию)
		 	"ВЫБРАТЬ
		 	|	ВТ_НовоеПоложениеУзла.Уровень - ВТ_СуществующаяЗапись.Уровень КАК СмещениеУровня,
		 	|	ВТ_СуществующаяЗапись.ПравыйКлюч - ВТ_СуществующаяЗапись.ЛевыйКлюч + 1 КАК Дельта,
		 	|	ВЫБОР
		 	|		КОГДА ВТ_СуществующаяЗапись.ПравыйКлюч > ВТ_НовоеПоложениеУзла.БлижайшийПравыйКлюч
		 	|			ТОГДА ВТ_НовоеПоложениеУзла.БлижайшийПравыйКлюч - ВТ_СуществующаяЗапись.ЛевыйКлюч + 1
		 	|		ИНАЧЕ ВТ_НовоеПоложениеУзла.БлижайшийПравыйКлюч - ВТ_СуществующаяЗапись.ЛевыйКлюч + 1 - (ВТ_СуществующаяЗапись.ПравыйКлюч - ВТ_СуществующаяЗапись.ЛевыйКлюч + 1)
		 	|	КОНЕЦ КАК Смещение,
		 	|	ВЫБОР
		 	|		КОГДА ВТ_СуществующаяЗапись.ПравыйКлюч > ВТ_НовоеПоложениеУзла.БлижайшийПравыйКлюч
		 	|			ТОГДА -1
		 	|		ИНАЧЕ 1
		 	|	КОНЕЦ КАК Направление,
		 	|	ВТ_НовоеПоложениеУзла.БлижайшийПравыйКлюч КАК БлижайшийПравыйКлюч,
		 	|	ВТ_СуществующаяЗапись.ПравыйКлюч КАК СтарыйПравыйКлюч,
		 	|	ВТ_СуществующаяЗапись.ЛевыйКлюч КАК СтарыйЛевыйКлюч
		 	|ПОМЕСТИТЬ ВТ_ОтборыИСмещение
		 	|ИЗ
		 	|	ВТ_СуществующаяЗапись КАК ВТ_СуществующаяЗапись,
		 	|	ВТ_НовоеПоложениеУзла КАК ВТ_НовоеПоложениеУзла
		 	|;
		 	|
		 	|////////////////////////////////////////////////////////////////////////////////
            |////////// Перемещение влево ////////////////// 
		 	|ВЫБРАТЬ
		 	|	&Период КАК Период,
		 	|	НоменклатураNestedSets.Номенклатура КАК Номенклатура,
		 	|	ВЫБОР
		 	|		КОГДА НоменклатураNestedSets.ЛевыйКлюч >= ВТ_ОтборыИСмещение.СтарыйЛевыйКлюч
		 	|			ТОГДА НоменклатураNestedSets.ЛевыйКлюч + ВТ_ОтборыИСмещение.Смещение
		 	|		КОГДА НоменклатураNestedSets.ЛевыйКлюч > ВТ_ОтборыИСмещение.БлижайшийПравыйКлюч
		 	|			ТОГДА НоменклатураNestedSets.ЛевыйКлюч + ВТ_ОтборыИСмещение.Дельта
		 	|		ИНАЧЕ НоменклатураNestedSets.ЛевыйКлюч
		 	|	КОНЕЦ КАК ЛевыйКлюч,
		 	|	ВЫБОР
		 	|		КОГДА НоменклатураNestedSets.ЛевыйКлюч >= ВТ_ОтборыИСмещение.СтарыйЛевыйКлюч
		 	|			ТОГДА НоменклатураNestedSets.ПравыйКлюч + ВТ_ОтборыИСмещение.Смещение
		 	|		КОГДА НоменклатураNestedSets.ПравыйКлюч < ВТ_ОтборыИСмещение.СтарыйЛевыйКлюч
		 	|			ТОГДА НоменклатураNestedSets.ПравыйКлюч + ВТ_ОтборыИСмещение.Дельта
		 	|		ИНАЧЕ НоменклатураNestedSets.ПравыйКлюч
		 	|	КОНЕЦ КАК ПравыйКлюч,
		 	|	ВЫБОР
		 	|		КОГДА НоменклатураNestedSets.ЛевыйКлюч >= ВТ_ОтборыИСмещение.СтарыйЛевыйКлюч
		 	|			ТОГДА НоменклатураNestedSets.Уровень + ВТ_ОтборыИСмещение.СмещениеУровня
		 	|		ИНАЧЕ НоменклатураNestedSets.Уровень
		 	|	КОНЕЦ КАК Уровень
		 	|ИЗ
		 	|	ВТ_ОтборыИСмещение КАК ВТ_ОтборыИСмещение
		 	|		ВНУТРЕННЕЕ СОЕДИНЕНИЕ РегистрСведений.НоменклатураNestedSets.СрезПоследних(
		 	|				,
		 	|				1 В
		 	|					(ВЫБРАТЬ
		 	|						1
		 	|					ИЗ
		 	|						ВТ_ОтборыИСмещение КАК ВТ_ОтборыИСмещение
		 	|					ГДЕ
		 	|						ВТ_ОтборыИСмещение.Направление = -1)) КАК НоменклатураNestedSets
		 	|		ПО (НоменклатураNestedSets.ПравыйКлюч > ВТ_ОтборыИСмещение.БлижайшийПравыйКлюч)
		 	|			И (НоменклатураNestedSets.ЛевыйКлюч < ВТ_ОтборыИСмещение.СтарыйПравыйКлюч)
		 	|ГДЕ
		 	|	ВТ_ОтборыИСмещение.Направление = -1
		 	|
		 	|ОБЪЕДИНИТЬ ВСЕ
		 	|
            |////////// Перемещение вправо //////////////////
		 	|ВЫБРАТЬ
		 	|	&Период,
		 	|	НоменклатураNestedSets.Номенклатура,
		 	|	ВЫБОР
		 	|		КОГДА НоменклатураNestedSets.ПравыйКлюч <= ВТ_ОтборыИСмещение.СтарыйПравыйКлюч
		 	|			ТОГДА НоменклатураNestedSets.ЛевыйКлюч + ВТ_ОтборыИСмещение.Смещение
		 	|		КОГДА НоменклатураNestedSets.ЛевыйКлюч > ВТ_ОтборыИСмещение.СтарыйПравыйКлюч
		 	|			ТОГДА НоменклатураNestedSets.ЛевыйКлюч - ВТ_ОтборыИСмещение.Дельта
		 	|		ИНАЧЕ НоменклатураNestedSets.ЛевыйКлюч
		 	|	КОНЕЦ,
		 	|	ВЫБОР
		 	|		КОГДА НоменклатураNestedSets.ПравыйКлюч <= ВТ_ОтборыИСмещение.СтарыйПравыйКлюч
		 	|			ТОГДА НоменклатураNestedSets.ПравыйКлюч + ВТ_ОтборыИСмещение.Смещение
		 	|		КОГДА НоменклатураNestedSets.ПравыйКлюч <= ВТ_ОтборыИСмещение.БлижайшийПравыйКлюч
		 	|			ТОГДА НоменклатураNestedSets.ПравыйКлюч - ВТ_ОтборыИСмещение.Дельта
		 	|		ИНАЧЕ НоменклатураNestedSets.ПравыйКлюч
		 	|	КОНЕЦ,
		 	|	ВЫБОР
		 	|		КОГДА НоменклатураNestedSets.ПравыйКлюч <= ВТ_ОтборыИСмещение.СтарыйПравыйКлюч
		 	|			ТОГДА НоменклатураNestedSets.Уровень + ВТ_ОтборыИСмещение.СмещениеУровня
		 	|		ИНАЧЕ НоменклатураNestedSets.Уровень
		 	|	КОНЕЦ
		 	|ИЗ
		 	|	ВТ_ОтборыИСмещение КАК ВТ_ОтборыИСмещение
		 	|		ВНУТРЕННЕЕ СОЕДИНЕНИЕ РегистрСведений.НоменклатураNestedSets.СрезПоследних(
		 	|				,
		 	|				1 В
		 	|					(ВЫБРАТЬ
		 	|						1
		 	|					ИЗ
		 	|						ВТ_ОтборыИСмещение КАК ВТ_ОтборыИСмещение
		 	|					ГДЕ
		 	|						ВТ_ОтборыИСмещение.Направление = 1)) КАК НоменклатураNestedSets
		 	|		ПО (НоменклатураNestedSets.ПравыйКлюч > ВТ_ОтборыИСмещение.СтарыйЛевыйКлюч)
		 	|			И (НоменклатураNestedSets.ЛевыйКлюч <= ВТ_ОтборыИСмещение.БлижайшийПравыйКлюч)
		 	|ГДЕ
		 	|	ВТ_ОтборыИСмещение.Направление = 1";
		ПериодЗаписи = ТекущаяДата();
		Запрос.УстановитьПараметр("Период", ПериодЗаписи);
		
		ВыгрузкаСмещение = Запрос.Выполнить().Выгрузить(); // Данные для записи в регистр с учетом смещения ключей
		
		НаборЗаписей = РегистрыСведений.НоменклатураNestedSets.СоздатьНаборЗаписей();
		НаборЗаписей.Загрузить(ВыгрузкаСмещение);
		НаборЗаписей.Записать(Ложь); // Записываем с замещением, лишние записи потрем регл.заданием
	КонецЕсли;

КонецПроцедуры

3. Удаление узла не сильно отличается от его добавления. Стоит лишь учесть, что при удалении узла удаляется вся ветка (все вложенные узлы). В системе такого не должно быть при нормальных условиях. Но если кто-то удалит группу не удостоверившись, что на нее ссылаются вложенные элементы, то тут как раз и отработает наш алгоритм сполна.

Ниже приведен листинг процедуры "ДобавитьУзелВМножество":

Процедура УдалитьУзелИзМножества(Номенклатура, Отказ) Экспорт
	Если Отказ Тогда
		Возврат;
	КонецЕсли;
	
	Запрос = Новый Запрос;
	Запрос.Текст =
		"ВЫБРАТЬ
		|	НоменклатураNestedSets.Номенклатура КАК Номенклатура,
		|	НоменклатураNestedSets.ЛевыйКлюч КАК ЛевыйКлюч,
		|	НоменклатураNestedSets.ПравыйКлюч КАК ПравыйКлюч,
		|	НоменклатураNestedSets.Уровень КАК Уровень,
		|	НоменклатураNestedSets.ПравыйКлюч - НоменклатураNestedSets.ЛевыйКлюч + 1 КАК Дельта
		|ПОМЕСТИТЬ ВТ_СуществующаяЗапись
		|ИЗ
		|	РегистрСведений.НоменклатураNestedSets.СрезПоследних(, Номенклатура = &Узел) КАК НоменклатураNestedSets
		|;
		|
		|////////////////////////////////////////////////////////////////////////////////
		|ВЫБРАТЬ
		|	НоменклатураNestedSetsСрезПоследних.Номенклатура КАК Номенклатура
		|ИЗ
		|	ВТ_СуществующаяЗапись КАК ВТ_СуществующаяЗапись
		|		ВНУТРЕННЕЕ СОЕДИНЕНИЕ РегистрСведений.НоменклатураNestedSets.СрезПоследних КАК НоменклатураNestedSetsСрезПоследних
		|		ПО ВТ_СуществующаяЗапись.ЛевыйКлюч <= НоменклатураNestedSetsСрезПоследних.ЛевыйКлюч
		|			И ВТ_СуществующаяЗапись.ПравыйКлюч >= НоменклатураNestedSetsСрезПоследних.ПравыйКлюч
		|;
		|
		|////////////////////////////////////////////////////////////////////////////////
		|ВЫБРАТЬ
		|	&Период КАК Период,
		|	НоменклатураNestedSetsСрезПоследних.Номенклатура КАК Номенклатура,
		|	ВЫБОР
		|		КОГДА НоменклатураNestedSetsСрезПоследних.ЛевыйКлюч > ВТ_СуществующаяЗапись.ЛевыйКлюч
		|			ТОГДА НоменклатураNestedSetsСрезПоследних.ЛевыйКлюч - ВТ_СуществующаяЗапись.Дельта
		|		ИНАЧЕ НоменклатураNestedSetsСрезПоследних.ЛевыйКлюч
		|	КОНЕЦ КАК ЛевыйКлюч,
		|	НоменклатураNestedSetsСрезПоследних.ПравыйКлюч - ВТ_СуществующаяЗапись.Дельта КАК ПравыйКлюч,
		|	НоменклатураNestedSetsСрезПоследних.Уровень КАК Уровень
		|ИЗ
		|	ВТ_СуществующаяЗапись КАК ВТ_СуществующаяЗапись
		|		ВНУТРЕННЕЕ СОЕДИНЕНИЕ РегистрСведений.НоменклатураNestedSets.СрезПоследних КАК НоменклатураNestedSetsСрезПоследних
		|		ПО ВТ_СуществующаяЗапись.ПравыйКлюч < НоменклатураNestedSetsСрезПоследних.ПравыйКлюч";
	Запрос.УстановитьПараметр("Узел", Номенклатура.Ссылка);
	ПериодЗаписи = ТекущаяДата();
	Запрос.УстановитьПараметр("Период", ПериодЗаписи);
	
	Пакет = Запрос.ВыполнитьПакет();
	ВыборкаКУдалению = Пакет[1].Выбрать();
	ВыгрузкаСмещение = Пакет[2].Выгрузить(); // Данные для записи в регистр с учетом смещения ключей

    // Здесь можно тоже оптимизнуть и удалить записи не в цикле, а допустим записать их в регистр с некой пометкой "к удалению",
    // но стоит учесть, что тогда придется дописать все остальные запросы и вместо того, чтобы просто брать срез, еще и отсеивать по этому новому признаку
	Пока ВыборкаКУдалению.Следующий() Цикл	
		// Удаляем узел (ветку)
		НаборЗаписей = РегистрыСведений.НоменклатураNestedSets.СоздатьНаборЗаписей();
		НаборЗаписей.Отбор.Номенклатура.Установить(ВыборкаКУдалению.Номенклатура);
		НаборЗаписей.Записать();
	КонецЦикла;
	
	НаборЗаписей = РегистрыСведений.НоменклатураNestedSets.СоздатьНаборЗаписей();
	НаборЗаписей.Загрузить(ВыгрузкаСмещение);
	НаборЗаписей.Записать(Ложь);
КонецПроцедуры

В моей реализации я сделал регистр сведений "НоменклатураNestedSets" периодическим с целью увеличения производительности. Объясню: в примерах по использованию Nested Sets в интернетах используется команда UPDATE SQL сервера, такого 1С не может. Либо записывай набор записей целиком на весь регистр, либо пиши по одной записи. Если рассматривать спр. Номенклатура, то он спокойно может перевалить за 100 000, и каждый раз писать весь набор (с предшествующим удалением) это будет накладно. Писать по одной записи, тоже плохо (обращение к СУБД в цикле). Остается вариант использование периодического регистра: записывать только измененные позиции на текущую секунду, везде в запросах брать срез последних по регистру, а регламентным заданием чистить регистр. Собственно, такой вариант я и выбрал. Конечно он не идеален (2 записи в одну секунду не осилит), но для того чтобы показать алгоритм работы с Nested Sets подойдет.

Ну и на конец сам проверка на вхождение в иерархию, сделал ее в обработке проведения документа. Листинг ниже:

Процедура ОбработкаПроведения(Отказ, РежимПроведения)
	Запрос = Новый Запрос;
	Запрос.Текст =
		"ВЫБРАТЬ
		|	ВЫРАЗИТЬ(ЗаявкиСотрудниковЗаказы.Сотрудник КАК Справочник.Сотрудники) КАК Сотрудник,
		|	ВЫРАЗИТЬ(ЗаявкиСотрудниковЗаказы.Номенклатура КАК Справочник.Номенклатура) КАК Номенклатура
		|ПОМЕСТИТЬ ВТ_Заказы
		|ИЗ
		|	&ТЗ КАК ЗаявкиСотрудниковЗаказы
		|;
		|
		|////////////////////////////////////////////////////////////////////////////////
		|ВЫБРАТЬ РАЗЛИЧНЫЕ
		|	ВТ_Заказы.Сотрудник КАК Сотрудник,
		|	ВТ_Заказы.Сотрудник.Сегмент КАК Сегмент,
		|	СегментыСостав.Номенклатура КАК НоменклатураСегмента
		|ПОМЕСТИТЬ ВТ_ДанныеПоСегментам
		|ИЗ
		|	ВТ_Заказы КАК ВТ_Заказы
		|		ЛЕВОЕ СОЕДИНЕНИЕ Справочник.Сегменты.Состав КАК СегментыСостав
		|		ПО ВТ_Заказы.Сотрудник.Сегмент = СегментыСостав.Ссылка
		|;
		|
		|////////////////////////////////////////////////////////////////////////////////
		|ВЫБРАТЬ
		|	ВТ_ДанныеПоСегментам.Сотрудник КАК Сотрудник,
		|	ВТ_ДанныеПоСегментам.НоменклатураСегмента КАК НоменклатураСегмента,
		|	КлючиНоменклатурыСегмента.ЛевыйКлюч КАК ЛевыйКлюч,
		|	КлючиНоменклатурыСегмента.ПравыйКлюч КАК ПравыйКлюч
		|ПОМЕСТИТЬ ВТ_ДанныеПоСегментамСКлючами
		|ИЗ
		|	ВТ_ДанныеПоСегментам КАК ВТ_ДанныеПоСегментам
		|		ЛЕВОЕ СОЕДИНЕНИЕ РегистрСведений.НоменклатураNestedSets.СрезПоследних(
		|				,
		|				Номенклатура В
		|					(ВЫБРАТЬ
		|						ВТ_ДанныеПоСегментам.НоменклатураСегмента
		|					ИЗ
		|						ВТ_ДанныеПоСегментам КАК ВТ_ДанныеПоСегментам)) КАК КлючиНоменклатурыСегмента
		|		ПО ВТ_ДанныеПоСегментам.НоменклатураСегмента = КлючиНоменклатурыСегмента.Номенклатура
		|;
		|
		|////////////////////////////////////////////////////////////////////////////////
		|ВЫБРАТЬ
		|	ВТ_Заказы.Сотрудник КАК Сотрудник,
		|	ВТ_Заказы.Номенклатура КАК Номенклатура,
		|	ВТ_ДанныеПоСегментамСКлючами.НоменклатураСегмента КАК НоменклатураСегмента
		|ИЗ
		|	ВТ_Заказы КАК ВТ_Заказы
		|		ЛЕВОЕ СОЕДИНЕНИЕ РегистрСведений.НоменклатураNestedSets.СрезПоследних(
		|				,
		|				Номенклатура В
		|					(ВЫБРАТЬ
		|						ВТ_Заказы.Номенклатура
		|					ИЗ
		|						ВТ_Заказы КАК ВТ_Заказы)) КАК КлючиНоменклатурыЗаказа
		|		ПО ВТ_Заказы.Номенклатура = КлючиНоменклатурыЗаказа.Номенклатура
		|		ЛЕВОЕ СОЕДИНЕНИЕ ВТ_ДанныеПоСегментамСКлючами КАК ВТ_ДанныеПоСегментамСКлючами
		|		ПО ВТ_Заказы.Сотрудник = ВТ_ДанныеПоСегментамСКлючами.Сотрудник
		|			И (КлючиНоменклатурыЗаказа.ЛевыйКлюч >= ВТ_ДанныеПоСегментамСКлючами.ЛевыйКлюч)
		|			И (КлючиНоменклатурыЗаказа.ПравыйКлюч <= ВТ_ДанныеПоСегментамСКлючами.ПравыйКлюч)
		|ГДЕ
		|	ВТ_ДанныеПоСегментамСКлючами.Сотрудник ЕСТЬ NULL";
	Запрос.УстановитьПараметр("ТЗ", Заказы.Выгрузить(,"Сотрудник, Номенклатура"));
	
	Результат = Запрос.Выполнить();
	
	Если Не Результат.Пустой() Тогда
		Отказ = Истина;
		Сообщение = Новый СообщениеПользователю;
		Сообщение.Текст = "Кто-то заказал что-то не то";		
		Сообщение.Сообщить();
	КонецЕсли;
КонецПроцедуры

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

Спасибо за внимание, надеюсь для кого-то эта статья будет полезна.

29

Скачать файлы

Наименование Файл Версия Размер
Соединение таблиц в запросе по условию "В иерархии" с использованием Nested Sets:
.dt 53,67Kb
05.07.17
1
.dt 53,67Kb 1 Скачать

См. также

Специальные предложения

Комментарии
Избранное Подписка Сортировка: Древо
1. Dmitri93 4 03.07.17 10:10 Сейчас в теме
Очень интересно было читать, описано доступным и понятным языком. Спасибо автору) честно говоря, я для себя пока не вижу конкретного практического применения этой технологи, но то что она кому-то может пригодиться это точно.
2. azhilichev 04.07.17 03:45 Сейчас в теме
ЛЕВОЕ СОЕДИНЕНИЕ РегистрСведений.НоменклатураNestedSets.СрезПоследних(


Лучше это вынести во временную таблицу. Соединять основной запрос с виртуальными таблицами - плохая практика.

| Номенклатура В
| (ВЫБРАТЬ
| ВТ_Заказы.Номенклатура
| ИЗ
| ВТ_Заказы КАК ВТ_Заказы)


Тут нужны индексы (подзапрос в параметрах виртуальной таблицы - это тоже плохо, тем более из неиндексированной таблицы).

Ну и в целом по коду похожее наблюдается. Я понимаю, что это придирки, но вот это

Блокировка = Новый БлокировкаДанных;
ЭлементБлокировки = Блокировка.Добавить("РегистрСведений.НоменклатураNestedSets");
ЭлементБлокировки.Режим = РежимБлокировкиДанных.Исключительный;
Блокировка.Заблокировать();


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

Но в целом довольно интересная статья, поэтому плюс вам.
4. kron.isant 44 04.07.17 14:19 Сейчас в теме
(2) Спасибо за комментарии.
3. bulpi 150 04.07.17 12:35 Сейчас в теме
Интересно, но на самом деле для решения исходной задачи поддерживать такой регистр - это стрелять из пушки по воробьям.
5. alon 171 05.07.17 13:54 Сейчас в теме
Начал читать, и не понял вот это
И (ВЫБОР

КОГДА ВТ_Заказы.Номенклатура.ЭтоГруппа

ТОГДА ВТ_Заказы.Номенклатура В ИЕРАРХИИ (СегментыСостав.Номенклатура)

ИНАЧЕ ВТ_Заказы.Номенклатура = СегментыСостав.Номенклатура

КОНЕЦ)
По идее проверка должна идти на СегментыСостав.Номенклатура.ЭтоГруппа
6. kron.isant 44 05.07.17 15:41 Сейчас в теме
Вы правы, спасибо, что заметили.
Запрос писал для примера в статью, разумеется проверить его не удалось:)
7. eugeniezheludkov 34 06.07.17 07:57 Сейчас в теме
Ваша статья хороша тем, что в подобной задаче я сделал запрос в цикле, а на код ревью обосновал это ссылкой на вашу статью, мол во что превратится код если уберу запрос из цикла ) ....
8. German_Tagil 6 07.07.17 17:04 Сейчас в теме
Пытаемся написать на базе КА 1.1 систему управления заявками - большая часть написана - тестируется.
Но возник такой интересный вопрос - в заказе поставщику одной позиции номенклатуры может соответствовать две - три четыре N количества заявок
Как реализовать список заявок,количество которое было заказано в табличном поле заказа поставщику ?
Я понимаю что это вопрос обсуждался и не раз и не два - но к сожалению ничего внятного не нашел
можно организовать регистр сведений и пихать туда всю инфу связанную с данной номенклатурой
но может есть другие варианты
надо поразмышлять - что-то очень близкое к тому что мне надо
10. starik-2005 1853 27.07.17 15:31 Сейчас в теме
(8)
Но возник такой интересный вопрос - в заказе поставщику одной позиции номенклатуры может соответствовать две - три четыре N количества заявок
Кто ясно мыслит - тот ясно излагает. Я вот, честно, ничего не понял.
9. starik-2005 1853 27.07.17 15:30 Сейчас в теме
Слишком сложная реализация достаточно простого механизма.
11. kron.isant 44 28.07.17 15:21 Сейчас в теме
(9) Механизм в понимании может быть и прост, но реализация его в среде 1С, на мой взгляд, выглядит именно так (как описано в статье).
Предложите более простой вариант реализации. Ну или хотя бы намекните, что здесь можно упростить, а то уж больно голословным получился Ваш комментарий.
16. German_Tagil 6 02.08.17 12:58 Сейчас в теме
(9) Sergey Andree - попробую изложить еще раз
есть спецификация покупных вразличных спецификациях могут повторяться
одноименная номенклатура - как отследить что пришло по той или иной заявке(спецификации)
перепахивать таблицы товара в заказах поставщик приходный ордер
в данном случае это вопрос - может кто-то подобное делал?
17. starik-2005 1853 02.08.17 13:26 Сейчас в теме
(16) Я, конечно, не филолог, но все-равно не могу понять, что это:
(16)
есть спецификация покупных
"Покупных" чего?
вразличных спецификациях могут повторяться одноименная номенклатура
"Могут" - это они. Они - это "покупные"? Или "они" - это "одноименная номенклатура" (тогда с какого хрена в единственном числе)?
(16)
как отследить что пришло по той или иной заявке(спецификации)
Заявка - это что? Спецификация? Или просто номенклатура? Пришло - это как? Документом каким-то? ПТУ? Или просто пришло и встало там в углу?

Пока Вы не научитесь излагать мысли, мне Вам сложно будет что-то ответить (и, полагаю, не только мне).
Патриот; +1 Ответить
12. zels 170 29.07.17 12:12 Сейчас в теме
Можно первоначально назначить ключи с шагом 100, чтобы потом было, куда вставлять новые и тем самым ускорить модификацию дерева?
13. kron.isant 44 31.07.17 11:14 Сейчас в теме
(12) Ваш первый комментарий был о том, что реализация слишком сложна, при этом предложенный вами вариант (с шагом в 100) не упрощает, а, наоборот, усложняет реализацию.
Да, он выглядит более оптимальным с точки зрения производительности, но реализация уж точно усложняется:
1. остается старый подход в случае, когда мы вываливаемся за буфер (добавляется больше 100 элементов);
2. и добавляется новый "оптимизированный" код для включения в добавленный буфер (1..99).
14. zels 170 31.07.17 16:37 Сейчас в теме
(13) А где мой первый комментарий?
15. kron.isant 44 01.08.17 17:33 Сейчас в теме
(14) Прошу прощения, думал что Вы написали предыдущие комментарии :)
18. German_Tagil 6 02.08.17 13:33 Сейчас в теме
есть спецификация покупных материалов
в различных спецификациях может повторяться одноименная номенклатура
Заявка - это что - Документ в который заносится спецификация
19. starik-2005 1853 02.08.17 13:41 Сейчас в теме
(18) Ну так это азы!
Азы - это стандартные методы FIFO/LIFO и по-среднему. Был вот случай у меня: автозапчасти, много заявок с предоплатой или по-договоренности, одинаковые запчасти в заявках. Когда приход происходил, то сначала лучшему клиенту, потом хорошему, потом остальным (если осталось). Ну и срок учитывался (в пределах недели). Задача в принципе на спеца по платформе - можно в заказе партии с учетом спецификации создавать и по приходу распределять.
Оставьте свое сообщение