БД. Как хранить древовидные структуры

23.10.2020 Программирование

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

    Бытовая техника (id=1)
        Телевизоры (id=2)
            Плазменные (id=3)
            LCD (id=4)   
        Холодильники (id=5)
            Маленькие (id=6)
            Средние (id=7)
            Большие (id=8)
    Профессиональная техника (id=9)
        ...

Типичные задачи, которые встречаются при работе с такими структурами:

  • выбрать всех детей элемента (например, дети раздела "Бытовая техника" - это "Телевизоры" и "Холодильники")
  • выбрать всех потомков (детей и их детей) элемента
  • проверить, является ли данный элемент потомком другого
  • определить родителя элемента. Например, родитель элемента "Средние" - это элемент "Холодильники"
  • выбрать цепочку предков элемента (родитель, его родитель, и так далее). Для "Средних" путь будет такой: "Бытовая техника" > "Холодильники" > "Средние"
  • переместить элемент (и его потомков) из одной группы в другую
  • удалить элемент из таблицы (со всеми потомками)

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

Добавить колонку parent_id (метод Adjacency List)

Мы добавляем к каждой записи колонку parent_id (и индекс на нее для эффективного поиска), которая хранит id родительской записи (если родителя нет — NULL). Это самый простой, но и самый неэффективный способ. Вот как будет выглядеть вышеприведенное дерево:

Бытовая техника (id=1, parent_id=NULL)
    Телевизоры (id=2, parent_id=1)
        Плазменные (id=3,parent_id=2)
        LCD (id=4,parent_id=2)   
    Холодильники (id=5,parent_id=1)

Выбрать всех детей просто: SELECT WHERE parent_id = ?, но другие операции требуют выполнения нескольких запросов и на больших деревьях не очень эффективны. Например, выбор всех потомков элемента с идентификатором :id

  • выбрать список детей :id (SELECT WHERE parent_id = :id)
  • выбрать список их детей (SELECT WHERE parent_id IN (:children1))
  • выбрать список детей детей (SELECT WHERE parent_id IN (:children2))

И так, пока мы не дойдем до самого младшего ребенка. То есть максимальное число запросов равно глубине дерева + 1 (последним запросом мы проверяем, что больше детей нет). После этого надо еще объединить результаты в дерево и отсортировать в правильном порядке. Часто эта сортировка в итоге требует больше времени, чем выборка.

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

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

Иногда еще добавляют поле depth, указывающее глубину вложенности, но его надо не забыть обновлять при перемещении ветки.

Closure table — усовершенствование предыдущего способа

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

| parent_id | child_id | depth | |---------------:|-----------:|--------:| | 1 | 1 | 0 | | 1 | 2 | 1 | | 1 | 3 | 2 | | 1 | 4 | 2 | | 1 | 5 | 1 | | .... | | | | 2 | 2 | 0 | | 2 | 3 | 1 | | 2 | 4 | 1 |

Число строк в этой таблице примерно равно (число элементов) × (среднее число потомков у элемента), то есть их будет довольно много и для больших таблиц (тысячи и больше элементов) этот подход неэффективен.

Чтобы узнать всех потомков записи, мы (в отличие от предыдущего способа), делаем запрос к дополнительной таблице: SELECT child_id FROM closure_table WHERE parent_id = :id, получаем id потомков и выбираем их их основной таблицы: SELECT WHERE id IN (:children). Если таблицы хранятся в одной БД, запросы можно объединить в один с использованием JOIN.

Данные потом надо будет вручную отсортировать в дерево.

Узнать список предков можно тоже одним запросом к таблице связей: SELECT parent_id FROM closure_table WHERE child_id = :id ORDER BY depth

Минусы метода:

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

Плюсы:

  • относительная простота
  • быстрота выборок (если не учитывать сортировку)

Nested sets

Идея в том, что мы добавляем к каждой записи поля parent_id, depth, left, right и выстраиваем записи хитрым образом. После этого выборка всех потомков (причем уже отсортированных в нужном порядке) делается простым запросом вида SELECT WHERE left >= :a AND right <= :b.

Поля left и right хранят идущие по возрастанию числа, подобранные, чтобы соблюдались правила:

  • значения left/right уникальны и не повторяются
  • у любого элемента right > left
  • у детей leftchild и rightchild всегда находятся в промежутке между leftparent и rightparent родителя, то есть leftparent < leftchild < rightchild < rightparent
  • элементы на одном уровне (с общим родителем) выстраиваются по возрастанию left

Вот пример расстановки left/right для дерева выше:

[ 1(left)           Бытовая техника                                  (right) 16 ][ 17 Профессиональная ... ]
[ 2 Телевизоры            7 ][ 8 Холодильники                                15 ] ....
[ 3 Плазменные 4 ][ 5 LCD 6 ][ 9 Маленькие 10 ][ 11 Средние 12 ][ 13 Большие 14 ] ....

Такое распределение чисел позволяет при выборке с условием ORDER BY left получать отсортированные в правильном порядке записи (попробуй проверить это вручную), и отсеивать потомков записи по условию WHERE left > :leftParent AND right < :rightParent или (что равносильно предыдущему варианту, но использует индекс по left) WHERE left > :leftParent AND left < :rightParent. Индекс по left оптимизирует как сортировку, так и отбор потомков.

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

Минусы:

  • необходимость пересчитывать left/right почти во всей таблице при вставке записей в середину или удалении
  • сложное перемещение веток
  • сложность в понимании.

Плюсы:

  • скорость выборки
  • записи выбираются уже отсортированными

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

При использовании этого метода рекомендуется также найти или написать код для проверки правильности расстановки значений left/right/depth и их исправления.

Materialized Path

Идея в том, что записи в пределах одной ветки нумеруются по порядку и в каждую запись добавляется поле path, содержащее полный список родителей. Напоминает способ нумерации глав в книгах. Пример:

    Бытовая техника (id=1, number=1, path=001)
        Телевизоры (id=2, number=1, path=001.001)
            Плазменные (id=3, number=1, path=001.001.001)
            LCD (id=4, number=2, path=001.001.002)   
        Холодильники (id=5, number=2, path=001.002)

При этом способе path хранится в поле вроде VARCHAR, по нему делается индекс (так как path может быть длинный, индексировать можно только первые N символов, где N выбирается так, чтобы с одной стороны индекс получился меньшего размера, с другой стороны, значения в нем не повторялись бы). Выбрать всех потомков можно запросом SELECT WHERE path LIKE '001.001.%' ORDER BY path, который использует индекс.

Определение предков делается получением их путей (001.001.002 -> 001.001, 001) и поиском записей c условием path IN (...).

Нули добавляются для корректной сортировки: с нулями порядок будет 001, 002, 010, а без нулей 1, 10, 2. Разумеется, из-за того что длина числа ограничена, в этом примере у нас может быть не более 999 детей у каждого узла.

Точки поставлены для наглядности, так как длина чисел фиксирована, то их можно не ставить (и писать просто 001001002). Также, если хочется еще более плотного хранения, можно хранить числа в бинарном виде, например, выделив 1, 1,5 или 2 байта на каждое (1 байт дает нам закодировать 256 возможных значений, 1,5 - 4096, а 2 байта - 65536 значений).

Хотя этот способ и не требует хранения id родителя parent_id (оно избыточно, так как его можно получить из path), но удобнее иметь это поле. Оно позволит восстановить структуру дерева при ошибках в path, а также делать оптимизированные выборки (например, подсчет числа детей записи) с использованием индекса по условию WHERE parent_id = ?.

Плюс:

  • записи выбираются уже отсортированными в нужном порядке.
  • простота решения
  • скорость выборок высокая (1 запрос)
  • быстрая вставка

Минусы:

  • при вставке записи в середину надо пересчитывать номера и пути всех следующих за ней элементов и их потомков
  • при удалении ветки - возможно, тоже
  • при перемещении ветки надо делать сложные расчеты
  • максимальная глубина дерева и число детей у родителя ограничены выделенным для них местом и длиной path

Этот способ отлично подходит для древовидных комментариев, которые редко переносятся. Удаление комментария не с конца ветки может потребовать обновления большого числа path, потому вместо удаления часто просто заводят поле вроде isDeleted и ставят в него 1, а при выборке отсеивают такие записи.