Как хранить иерархические структуры данных в SQL?
Когда нужно хранить пути (URL-адреса) в базе данных, то возникает очень много отдельных вопросов. По началу не понятен сам процесс.
Предлагаю поглядеть на приблизительный набор URL-адресов:
- https://example.com
- https://example.com/a
- https://example.com/a/aa
- https://example.com/a/bb
- https://example.com/b
- https://example.com/b/aa
- https://example.com/b/bb
- https://example.com/b/cc
- https://example.com/b/cc/sss
- https://example.com/b/cc/ttt
- https://example.com/b/cc/ttt/zzz
- https://example.com/b/cc/ooo
- https://example.com/c
Что мы видим? Мы видим повторяющиеся символьные последовательности на всём наборе строк (URL-адресов). Также мы видим, что строки между собой имеют незначительные (менее весомые) различия. Большая часть информации в каждой строке повторяется из адреса в адрес.
Очевидно, что хранение строк в таком виде будет занимать много места в таблице базы данных, потому что есть повторения.
Давайте посмотрим на статистику.
Все эти 13 строк посимвольно занимают 330 байт. Для примера я закину их в одну строку JavaScript.
Мы понимаем, что эту строку можно сократить. Если мы найдём «самую короткую начальную последовательность» символов, которая встречается во всех 13 строках, то мы можем вынести её в отдельное место. Такой «короткой начальной последовательностью» является «https://example.com«.
Её длина составляет 19 байт. Она повторяется 13 раз, что суммарно равно 247 байт.
Что получается? Из всех 330 байт «самая короткая начальная последовательность» символов занимает 247 байт. Это 74%. Это очень много!!!
Например
Если бы у нас база данных занимала 1 терабайт, то при таком раскладе мы могли бы теоретически сэкономить 740 гигабайт. В результате улучшения, данные могли бы занимать 260 гигабайт. Не кажется ли вам, что это очень хорошо? Экономия пространства существенная.
На «кухонном языке» нам всё понятно, но как это реализовать на практике в PostgreSQL? Как это называется в математическом сообществе?
Давайте нарисуем иерархическую модель наших 13 строк:
Иерархическая модель даёт наглядное представление о том, что любой URL-адрес можно разложить на составные элементы.
Видно сколько всего уровней вложенности может быть из нашего массива уникальных URL-адресов. Мы видим 4 уровня вложенности (глубины).
Также мы можем видеть какой элемент является родительским для остальных элементов — это самый верхний элемент (строка-домен «https://example.com«)
Мы можем найти самый глубокий элемент — это «/zzz«.
Мы знаем кто у кого является братом/сестрой, а кто ребёнком.
В общем это всё очень напоминает «Объектную Модель Документа» — DOM.
Остаётся только понять КАК ЗАПИСЫВАТЬ такие структуры в таблицу, а также КАК ИЗВЛЕКАТЬ из такой таблицы нужные данные?
Статья в разработке
…
Информационные ссылки
Вы можете поискать ответ в теме официального справочника по PostgreSQL — «Глава 64. Индексы B-деревья» — https://postgrespro.ru/docs/postgresql/14/btree
или
«Иерархические данные (SQL Server)» — https://docs.microsoft.com/ru-Ru/sql/relational-databases/hierarchical-data-sql-server?view=sql-server-2017
