Как максимально быстро и экономно построить дерево из плоской таблицы в 1С

← На главную

При разработке на платформе 1С:Предприятие часто возникает классическая задача: имеется плоская таблица значений (например, загруженная из внешнего источника, файла или полученная из SQL-запроса), строки которой связаны отношением «родитель — потомок» через колонки Ид и ИдРодителя. Нам необходимо преобразовать эту плоскую таблицу в полноценное иерархическое ДеревоЗначений для последующего вывода на форму или программной обработки.

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

Способ 1. Оптимизированный двухпроходный обход через Соответствие (сложность O(N))

Давайте выясним, почему традиционный рекурсивный поиск работает медленно. Если на каждом уровне иерархии мы выполняем метод таблицы значений НайтиСтроки, платформа вынуждена каждый раз сканировать всю таблицу. При большом объеме данных сложность такого алгоритма стремится к O(N²), что вызывает лавинообразный рост времени выполнения.

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

Рассмотрим детально, как выглядит этот алгоритм на практике:


// Предположим, что ПлоскаяТаблица - это наша исходная ТаблицаЗначений
// с колонками: Ид, ИдРодителя, Наименование и другими данными.

// Шаг 1. Создаем индекс родителей в памяти
ИндексРодителей = Новый Соответствие;

Для Каждого СтрокаТЗ Из ПлоскаяТаблица Цикл
    Родитель = СтрокаТЗ.ИдРодителя;
    
    // Получаем массив детей для текущего родителя
    СписокДетей = ИндексРодителей[Родитель];
    Если СписокДетей = Неопределено Тогда
        СписокДетей = Новый Массив;
        ИндексРодителей.Вставить(Родитель, СписокДетей);
    КонецЕсли;
    
    // Добавляем саму строку в массив подчиненных элементов
    СписокДетей.Добавить(СтрокаТЗ);
КонецЦикла;

// Шаг 2. Инициализируем результирующее ДеревоЗначений
ДеревоРезультат = Новый ДеревоЗначений;
ДеревоРезультат.Колонки.Добавить("Ид");
ДеревоРезультат.Колонки.Добавить("ИдРодителя");
ДеревоРезультат.Колонки.Добавить("Наименование");

// Шаг 3. Запускаем рекурсивную сборку дерева, начиная с корня (где Родитель равен Неопределено или пустому ИД)
ЗаполнитьУровеньДерева(ДеревоРезультат.Строки, Неопределено, ИндексРодителей);

Теперь рассмотрим саму рекурсивную процедуру ЗаполнитьУровеньДерева, которая благодаря предварительной индексации работает мгновенно:


Процедура ЗаполнитьУровеньДерева(КоллекцияСтрокДерева, ТекущийИдРодителя, ИндексРодителей)
    
    // Быстро получаем массив подчиненных элементов по ключу из соответствия (сложность O(1))
    Дети = ИндексРодителей[ТекущийИдРодителя];
    Если Дети = Неопределено Тогда
        Возврат; // У этого элемента нет подчиненных
    КонецЕсли;
    
    Для Каждого СтрокаИсточник Из Дети Цикл
        НоваяСтрокаДерева = КоллекцияСтрокДерева.Добавить();
        ЗаполнитьЗначенияСвойств(НоваяСтрокаДерева, СтрокаИсточник);
        
        // Рекурсивно уходим на следующий уровень иерархии
        ЗаполнитьУровеньДерева(НоваяСтрокаДерева.Строки, СтрокаИсточник.Ид, ИндексРодителей);
    КонецЦикла;
    
КонецПроцедуры

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

Способ 2. Использование Системы компоновки данных (СКД)

Платформа 1С:Предприятие содержит мощный и глубоко оптимизированный на уровне ядра C++ механизм для построения иерархических структур — Систему компоновки данных (СКД). Мы можем использовать СКД программно, чтобы переложить всю тяжелую работу по расчету иерархических связей на платформу.

Разберем по шагам, как настроить и выполнить такое построение:

Создаем программную схему компоновки данных СхемаКомпоновкиДанных.
Добавляем в нее НаборДанныхОбъект, куда мы передадим нашу плоскую таблицу значений.
Описываем вкладку «Связи наборов данных», связывая наш набор данных сам на себя по ключевым полям.
Настраиваем структуру вывода в детальные записи с иерархией и выгружаем результат напрямую в ДеревоЗначений.

Посмотрим на пример программной реализации этого метода:


// Инициализируем схему компоновки
Схема = Новый СхемаКомпоновкиДанных;

// Добавляем набор данных - объект
НаборДанных = Схема.НаборыДанных.Добавить(Тип("НаборДанныхОбъектСхемыКомпоновкиДанных"));
НаборДанных.Имя = "ИсходныеДанные";
НаборДанных.ИмяОбъекта = "ПлоскаяТаблица";

// Описываем поля набора данных
ДобавитьПолеВНаборДанных(НаборДанных, "Ид", "Ид");
ДобавитьПолеВНаборДанных(НаборДанных, "ИдРодителя", "ИдРодителя");
ДобавитьПолеВНаборДанных(НаборДанных, "Наименование", "Наименование");

// Описываем связь набора сам на себя для построения иерархии
Связь = Схема.СвязиНаборовДанных.Добавить();
Связь.НаборДанныхИсточник = "ИсходныеДанные";
Связь.НаборДанныхПриемник = "ИсходныеДанные";
Связь.ВыражениеИсточника  = "Ид";
Связь.ВыражениеПриемника  = "ИдРодителя";
Связь.ПараметрНачалаСвязи = Неопределено;
Связь.СвязьПоИерархии     = Истина; // Это ключевой момент!

// Настраиваем вывод структуры данных
КомпоновщикНастроек = Новый КомпоновщикНастроекКомпоновкиДанных;
КомпоновщикНастроек.Инициализировать(Новый ИсточникДоступныхНастроекКомпоновкиДанных(Схема));

Группировка = КомпоновщикНастроек.Настройки.Структура.Добавить(Тип("ГруппировкаКомпоновкиДанных"));
Группировка.Использование = Истина;

// Добавляем автополе в выбранные поля группировки
ВыбранноеПоле = Группировка.Выбор.Элементы.Добавить(Тип("АвтоВыбранноеПолеКомпоновкиДанных"));
ВыбранноеПоле.Использование = Истина;

// Выполняем компоновку
КомпоновщикМакета = Новый КомпоновщикМакетаКомпоновкиДанных;
МакетКомпоновки = КомпоновщикМакета.Выполнить(Схема, КомпоновщикНастроек.Настройки);

ВнешниеНаборыДанных = Новый Структура;
ВнешниеНаборыДанных.Вставить("ПлоскаяТаблица", ПлоскаяТаблица);

ПроцессорКомпоновки = Новый ПроцессорКомпоновкиДанных;
ПроцессорКомпоновки.Инициализировать(МакетКомпоновки, ВнешниеНаборыДанных);

// Выводим результат в ДеревоЗначений
ПроцессорВывода = Новый ПроцессорВыводаРезультатаКомпоновкиДанныхВДеревоЗначений;
ДеревоРезультат = Новый ДеревоЗначений;
ПроцессорВывода.УстановитьОбъект(ДеревоРезультат);
ПроцессорВывода.Вывести(ПроцессорКомпоновки);

Для удобства приведем вспомогательную функцию описания полей схемы:


Процедура ДобавитьПолеВНаборДанных(НаборДанных, ИмяПоля, ПутьКДанным)
    Поле = НаборДанных.Поля.Добавить(Тип("ПолеСхемыКомпоновкиДанных"));
    Поле.Имя = ИмяПоля;
    Поле.ПутьКДанным = ПутьКДанным;
    Поле.Заголовок = ИмяПоля;
КонецПроцедуры

Этот метод через СКД хорош тем, что вся логика рекурсивного связывания и сборки дерева выполняется внутренними оптимизированными алгоритмами платформы, что сводит к минимуму затраты памяти и времени выполнения на стороне сервера приложений 1С.

Способ 3. Ленивая (динамическая) загрузка — решение для сверхбольших таблиц

Если плоская таблица действительно огромна (содержит сотни тысяч строк), то построение полного дерева в памяти сервера, передача его по сети на тонкий клиент и попытка отобразить его на управляемой форме неизбежно приведут к зависанию интерфейса пользователя. Браузер или тонкий клиент просто не справятся с отрисовкой такого количества DOM-элементов или строк управления.

В этом случае применяется паттерн «ленивой загрузки» (подгрузки данных «на лету»):

На сервере мы формируем и выводим на форму только первый (корневой) уровень дерева.
Для тех корневых строк, у которых гарантированно есть подчиненные элементы, мы добавляем одну пустую строку-заглушку. Это нужно для того, чтобы платформа отобразила символ раскрытия ветки («плюсик») рядом с элементом.
На форме для элемента управления Таблица (связанного с деревом) переопределяем событие ПередРазворачиванием.
Когда пользователь нажимает на «плюсик», мы отправляем быстрый контекстный запрос на сервер, удаляем строку-заглушку и динамически подгружаем только подчиненные строки для этой конкретной ветки.

Посмотрим, как выглядит обработчик события на управляемой форме:


&НаКлиенте
Процедура СписокДеревоПередРазворачиванием(Элемент, СтрокаИдентификатор, Отказ)
    
    СтрокаДерева = Элемент.ДанныеФормы.НайтиПоИдентификатору(СтрокаИдентификатор);
    
    // Проверяем, загружены ли данные для этой ветки ранее
    Если ТребуетсяЗагрузкаПодчиненных(СтрокаДерева) Тогда
        ПодгрузитьПодчиненныеСтрокиНаСервере(СтрокаДерева.Ид, СтрокаИдентификатор);
    КонецЕсли;
    
КонецПроцедуры

И серверная процедура динамической подгрузки данных:


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

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

Важные нюансы и типичные ошибки

При решении задач построения иерархии разработчики часто сталкиваются с неочевидным поведением платформы 1С. Проанализируем ключевые моменты:

Запросы с конструкцией ИТОГИ ПО... ИЕРАРХИЯ: В обсуждениях часто предлагают использовать обычные запросы 1С с предложением ИТОГИ ПО. Помните, что конструкция ТОЛЬКО ИЕРАРХИЯ работает исключительно для иерархических справочников, заведенных в метаданных конфигурации. Если вы поместите произвольную плоскую таблицу значений во временную таблицу запроса, построить по ней иерархию через ИТОГИ не получится — платформа выдаст ошибку времени выполнения.
Ограничения ПостроителяЗапроса: Еще один популярный инструмент — ПостроительЗапроса. Он умеет группировать плоские таблицы и выгружать их в дерево, но предназначен только для линейных группировок (например, Организация — Склад — Номенклатура). Разрешить рекурсивную связь «родитель-потомок» по колонкам Ид / ИдРодителя он самостоятельно не способен.
Передача дерева между клиентом и сервером: Тип данных ДеревоЗначений существует только на стороне сервера или в толстом клиенте. На управляемой форме для отображения дерева используется специальный объект-декоратор ДанныеФормыДерево. Для преобразования одного в другой всегда применяйте быстрые системные методы ЗначениеВРеквизитФормы() и РеквизитФормыВЗначение().

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