Pull to refresh

Хранение иерархических данных в плоском виде

Reading time 3 min
Views 7.6K
На примере хранения дерева комментариев.

Многие наверняка сталкивались с проблемой хранения комментариев, по крайней мере задумывались об этом. Очевидным решением «в лоб» является ссылка на родительский комментарий и, как следствие, рекурсивные вызовы при необходимости отобразить дерево. Современные СУБД поддерживают иерархические запросы, но мне кажется, что это просто перенос проблемы за пределы области видимости, может быть я не прав. В любом случае я писал для Google Application Engine, там разговора об иерархических запросах не идёт вообще.

Мне очень не нравилась перспектива рекурсии и множество мелких запросов к базе, поэтому я стал изобретать какой-то способ получить все комментарии одним простым запросом. И такой способ я довольно быстро «изобрёл». Опросил нескольких знакомых, оказалось, что мало кто на эту тему задумывался, поэтому возьму на себя смелость описать что именно я реализовал.



Итак, главное требование — получить все комментарии сразу в нужном порядке одним запросом. Соответственно, я должен хранить 1) порядок отображения 2) уровень вложенности.

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

Для решения этих двух задач предлагается ввести некое поле, сортировка по которому и даст желаемый порядок следования комментариев.

Ниже небольшое дерево комментариев с примерами хэша.

  000000   1 первый комментарий
  000100     1.1 ответ на первый комментарий
  000101       1.1.1 ...
  000102       1.1.2 ...
  000103       1.1.3 ...
  000104       1.1.4 ...
  000200     1.2
  000300     1.3
  010000   2 второй комментарий
  010100     2.1 ответ на второй комментарий
  010200     2.2 ...
  020000   3 третий комментарий


Здесь числа типа «1.1.х» это просто часть комментария, а не часть хэша, каким его предлагает классический «материализованный путь».

Предлагаемый хэш стоит в начале каждой строки. В данном случае хэш содержит как бы три двузначных разряда: комментарии нулевого уровня нумеруются в двух первых разрядах, второго в двух вторых и так далее. Мне кажется вычисление этого поля достаточно очевидным из картинки.

Автоматически следуют два ограничения:
    1) ограничено количество комментариев на каждом уровне
    2) ограничено количество уровней.

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

В действительности я решил что на оба эти ограничения можно закрыть глаза. В случае хранения комментариев и их количество и вложенность вполне можно ограничить. Кроме того я пошёл на небольшую хитрость и «разрешаю» добавлять комментарий на 4-й уровень, но фактически оформляю это как комментарий третьего уровня и так же отображаю. Это сделано чтобы не ограничивать обсуждение двух увлёкшихся комментаторов.

Подробности реализации
Развивая эту идею, от цифрового поля я решил отказаться в пользу текстового. В этом случае я немного теряю в эффективности, но зато я вообще не ограничен в длине хэша. Вместо цифр я пользуюсь символами A-Z и a-x, то есть фактически использую числа с основанием 50 (пятидяситеричная система).

В пятидесятиричной системе я одним разрядом нумерую сразу 50 записей, двумя — уже 2500, для моих целей этого достаточно. Уровней вложенности я использую 8. Оба эти параметра легко меняются, но это можно сделать только один раз, перед началом использования.

С целью вычисления хэша для каждой записи кроме её уровня вложенности я храню ещё и количество дочерних записей, чтобы при добавлении очередной записи не приходилось делать лишних запросов (google data storage, фактически, не умеет выполнять select count(*)).

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

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

Выводы
легкий дискомфорт из-за всё-таки наличия ограничений;
некоторые сложности при вычислении этого служебного поля;
моментальная выдача всех результатов одним плоским запросом без лишней нагрузки на сервер.

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

Например здесь можно посмотреть как это всё выглядит и работает.

P.S. Ах да, если кто-то подскажет классические названия или реализации решения этой задачи, будет здорово.
Tags:
Hubs:
+43
Comments 110
Comments Comments 110

Articles