Full Hierarchy — иерархические структуры в базах данных

Веб разработка - Работа с БД

Здравствуйте. В этой статье я хотел бы написать про один очень интересный способ хранения иерархических структур в базах данных, не относящийся при этом к общепринятым и общеизвестным трём (Adjacency List, Nested Set, Materialized Path). Я не встречал в интернете упоминания о нём, о чём очень удивлен, ведь, по моему мнению, — это лучший и единственный способ хранить иерархические структуры. При разработке console-like форума я воспользовался именно этим способом, о чём ни на грамм не жалею. Это авторская статья и ни одно предложение не было вставлено метотодом копипаста.

Вполне возможно, что этот способ известен и называется он иначе. Если так — с удовольствием узнаю, как она называется на самом деле.

Имхо, этот способ больше всего похож на Materialized Path, с незначительным оттенком Adjacency List. По сравнению с Adjacency List он слегка денормализует базу данных, но с теми преимуществами, что он даёт — это не играет значительной роли.

Суть способа

Для каждой иерархической структуры мы создаем две таблицы — таблица с данными и таблица с иерархией. В таблице с данными мы храним то, что нам нужно, единственная ячейка, которая нас здесь интересует — это PRIMARY (`ID`)
В таблице иерархии мы храним список всех элементов и их родителей с уровнем к каждому родителю. То есть, если у элемента есть 5 родителей — мы храним 5 записей формата (ElemID, ParentID, Level). Таким образом, для описания самого глубокого элемента понадобится количество элементов, равное уровню вложенности.

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

Примеры

Итак, какой инструментарий для примера я использую:

Изначально я выложу код, который далее в статье объясню:
Я использую сообственноручно написанный класс для работы с БД (LGPL): pastebin.com/f2642074f. Именно в нём меняем параметры подключения.

Теперь по поводу самого кода:
Определяем, какой элемент мы будем хранить в базе. Это объект класс Elem c свойствами $id, $data, $children, $parent: pastebin.com/f78f943d8

Готовые функции, которыми работаем с базой, и далее они будут описаны: pastebin.com/f314afb10