Я знаю и использовал в прошлом два метода для базовых древовидных структур: списки смежности и вложенные множества. Я понимаю несколько плюсов и минусов этих подходов — например, списки смежности быстро обновляются, но медленно запрашиваются, что вложенные наборы противоположны (медленно обновляются, быстро запрашиваются).
Однако мне требуется возможность хранить более сложные древовидные структуры. Лучший способ описать это — использовать человеческие семейные отношения. Моей первой мыслью было, что каждый элемент может иметь как дерево «предков», так и дерево «потомков». Однако в этом подходе будет значительная избыточность, поскольку, используя приведенный ниже пример, и Кэмерон, и Келли будут совместно использовать все дерево предков Боба (и обновления будут занимать еще больше времени, поскольку вставка в дерево фактически должна будет вставляться в дерево предков Боба). несколько деревьев). Моей второй мыслью было включить ссылки на деревья. Например, скажем, что у Алисы есть собственное дерево предков. И элемент (4,5), исходящий из дерева предков Кэмерона, и элемент (2,3), исходящий из дерева предков Келли, будут просто ссылаться на дерево предков Алисы. Этот второй подход требует меньше места для хранения данных, будет производить более быстрые обновления (только обновление одного дерева по сравнению с несколькими деревьями) и сохранит преимущества скорости запросов к большой древовидной структуре (хотя SQL для запроса такого самоссылающегося вложенного набора довольно сложно). Однако недостатком второго подхода является то, что данные становятся «фрагментированными» (во многом подобно индексным дескрипторам на жестком диске).
A = Alice
B = Bob
C = Cameron
J = John
K = Kelly
+------------------------------------------+
+-----------+ +-------------+
|(2) Bob (3)| |(4) Alice (5)|
+-----+-----+ +------+------+
| |
| |
| |
| |
| +---------------+ |
+----+(1) Cameron (6)+----+
+---------------+
+-------------+ +------------+
|(2) Alice (3)| |(4) John (5)|
+-----+-------+ +-------+----+
| |
| |
| |
| |
| +-------------+ |
+------+(1) Kelly (6)+-------+
+-------------+
+------------------------------------------+
+-------------+
|(1) Alice (6)+----------+
+-+-----------+ |
| |
| |
| |
+---------+-----+ +-------+-----+
|(2) Cameron (3)| |(4) Kelly (5)|
+---------------+ +-------------+
Для второго подхода я визуализирую несколько вложенных наборов, сложенных друг перед другом, с определенными узлами, «рисующими линию» вдоль z-индекса к узлу на другой плоскости.
Обратите внимание, что это всего лишь пример: на самом деле я не храню человеческие отношения, а храню сложное дерево, подобное данным. Есть много причин для хранения таких сложных иерархических структур, поэтому я дам вам волю воображению!
Вопрос: Каков наиболее эффективный с точки зрения производительности способ (обновления и выборки) хранения сложных самоссылающихся древовидных структур в базе данных SQL? Я конкретно имею в виду PostgreSQL, но если у вас есть альтернативы (даже к самому SQL), я готов выслушать и это.
