Сбалансированная иерархия – это такая иерархия, в которой все ветви структуры имеют заранее определенное количество уровней.
Пример. Сбалансированная 3-уровневая иерархия:
Элемент 1
Элемент 1.1
Элемент 1.1.1
Элемент 1.2
Элемент 1.2.1
Элемент 1.2.2
Элемент 1.2.3
Элемент 1.3
Элемент 1.3.1
Элемент 1.3.2
Элемент 2
Элемент 2.1
Элемент 2.1.1
Элемент 3
Элемент 3.1
Элемент 3.1.1
Элемент 3.1.2

Классический механизм организации сбалансированной иерархии в таблице БД.
Несбалансированная иерархия – это такая иерархия, которая имеет неоднородную структуру и не имеет ограничений по количеству уровней в ее ветках.
Пример. Несбалансированная иерархия:
Элемент 1
Элемент 1.1
Элемент 1.2
Элемент 1.2.1
Элемент 1.2.1.1
Элемент 1.2.1.2
Элемент 1.2.2
Элемент 1.2.3
Элемент 1.3
Элемент 1.3.1
Элемент 1.3.2
Элемент 2
Элемент 3
Элемент 3.1

Классический механизм организации несбалансированной иерархии в таблице БД.
В случае если возникла ситуация, что очень нужно подключить к источнику данных некоторую очень важную программу, а она не умеет обрабатывать несбалансированные иерархии, то одним из лучших решений будет преобразовать несбалансированную иерархию в сбалансированную. Основное неудобство заключается в том, что несбалансированная иерархия не имеет физических ограничений по количеству уровней, а сбалансированная иерархия обязательно должна иметь четкое количество уровней. Поэтому, как правило, разработчик, перед написанием механизма преобразования, определяет максимальный уровень глубины для иерархии (либо по факту, либо по теоретическому максимуму), а потом пишет механизм преобразования. Для преобразования в сбалансированную иерархию я применяю в основном 2 подхода: SQL запрос на выборку со сложной структурой и рекурсивную процедуру (stored procedure в СУБД, либо алгоритм анализа в клиентском приложении) формирующую отдельную таблицу.
Первый подход хорош тем, что можно выполнить преобразование с помощью только одного запроса и нет необходимости увеличивать количество объектов СУБД. Недостатком же является сложность самого запроса (и соответственно, низкая его производительность), причем его сложность растет в арифметической прогрессии, в зависимости от максимального количества уровней иерархии.
Второй подход хорош тем, что работа со сформированной статической таблицей значительно быстрее чем работа со сложным запросом. Недостаток такого подходя – это то что при каждом изменении таблицы с несбалансированной иерархией необходимо полностью перестраивать таблицу со сбалансированной иерархией (что неприемлемо в системах где структура несбалансированной иерархии постоянно меняется).

Часто возникает задача выбрать из таблицы не все элементы иерархии, а только конкретный уровень. И если с 1-м уровнем все просто (выбрать все элементы у которого "Родитель is null"), то с остальными уровнями все не так просто. Лучшее решение, я считаю, это добавление атрибута с номером уровня. Обновлять поле с номером уровня лучше все триггером (средствами БД). Если задействовать механизм триггеров невозможно, то обновлять номер уровня элемента/ов можно рекурсивной процедурой, либо рекурсивным алгоритмом на клиентском приложении.

Одной из регулярных задач является удаление элементов иерархии, и тут самая большая проблема – это не допустить появления т. н. "разрывов" (когда в таблице появляются элементы иерархии, которые содержат ссылки на несуществующие элементы). Лучшим решением при удалении элементов иерархии, по моему мнению, является сканирование и удаление всех вложенных элементов иерархии рекурсивным алгоритмом. По опыту, в сложных системах, иногда (крайне редко, но случаи были), из-за особенностей работы некоторых СУБД, разрывы иногда могут появляться. Поэтому, я бы рекомендовал, в механизмы обслуживания (maintenance) систем хранения, включать алгоритмы сканирования иерархий на наличие разрывов.

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

1. определил все возможные комбинации сортировок для конкретной иерархии (по имени, по дате, по рейтингу и т. д.)
2. для каждой комбинации сортировки добавил сортирующий атрибут в таблицу с иерархией
3. сформировал рекурсивный алгоритм обновления сортирующих индексов

Но, при использовании описанного подхода, возникает серьезная проблема производительности при добавлении новых элементов иерархии (в простейшем случае, возникает необходимость перерасчета всех сортирующих атрибутов, что даже при относительно небольших размерах иерархии происходит весьма медленно). И тут, чтобы избежать сильных проседаний производительности, я использую небольшую хитрость. Если при базовом заполнении сортирующих атрибутов их заполнять не плотной последовательностью (1, 2, 3, 4 и т. д.), а разреженной (100, 200, 300, 400 и т. д.), то новым элементам можно будет рассчитывать их сортирующий атрибут на основе сортирующего атрибута родителя и рядом стоящих элементов, без необходимости перерасчета сортирующих атрибутов всей иерархии. Конечно же такой механизм не избавляет от необходимости периодически пересчитывать сортирующие атрибуты всей иерархии, но позволяет сильно оптимизировать алгоритм.

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