Технология создания древовидной структуры хранения данных

1. Основные положения

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

• Из чрезвычайно простой формы хранения на диске программным способом получается достаточно сложная разветвлённая структура.
• Смысл каждого слова (термина) определяется его положением в древовидной структуре.
• Каждое слово (термин) записывается в базе данных единожды, но в визуальном представлении повторяется столько раз, сколько нужно для представления других слов.

2. Структура хранения информации

Слова (термины) хранятся в таблице (базе данных), которая имеет следующие поля:

1. Уникальный номер (идентификатор) слова (ID);
2. Само слово (Name);
3. Ссылка на ID верхнего уровня, т.е. на слово, непосредственно определяющее данное (IDUp);
4. Ссылка на ID слова, которое является связанным с текущим (IDLink1);
5. - " - (IDLink2) и т.д.

При описании слова будут использоваться слово верхнего уровня и связанные слова в порядке их расположения от IDLink1 до IDLinkN. Количество связанных слов ограничивается только возможностями компьютера.

По данной таблице уже можно составить описания слов. Исключение составляют только слова первого уровня (с пустым полем IDUp). В данном примере — первые два.

Далее предлагаются эти описания:

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

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

3. Способ визуального представления дерева

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

Суть прямого обхода можно охарактеризовать, как "Родители-Дети". Помимо простой прорисовки связей, в структуру вставляются вспомогательные слова. Таким образом, слова-Дети в поле Родителя сгруппированы по одинаковым вспомогательным словам.

На рисунке ниже прямой обход выделен красным цветом, причём вспомогательные слова подчёркнуты пунктирной линией. Используется также термин основное положение слова. Это положение, которое занимает слово при прямом обходе. На рисунке оно выделено красной рамкой. Количество таких мест совпадает с количеством записей в базе данных.

Обратный обход создаёт дополнительные ветви в дереве. Он реализуется по следующему алгоритму:

1. Выделяются слова, которые присутствуют в связанных полях. В нашем случае это слова с номерами 3, 6 и 10.
2. Определяются основные положения этих слов.
3. В каждое из этих мест вставляются слова, в которых находятся дополнительные ссылки на данное слова. Предварительно эти слова группируются по их определениям (IDUp).

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

4. Заключение

В завершение описания технологии, хотелось бы оговорить некоторые возможности, позволяемые реализовать на основе выше описанного.

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

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