ツリー構造を持つデータの理想的なDB設計について

Question

前提・実現したいこと

FireBaseを使用したRDBによるwebアプリケーションを作成したいと思っています。
デザイン - フロントエンドが専門であり、バックエンドの下地はほぼありません。
JSについては実務レベルの経験（〜8年）があります。

DBの設計について、概念的な質問をしたいです。
イメージとして、「ユーザーが任意で投稿できるwebサービス」を想像してください。

まず、サービス側から1つのpostが行われます。
これは始祖です。（階層レベル0）

それに対し、ユーザーはそれぞれ回答をpostします。
回答は複数行われ、それらは同列として扱われます。
これは始祖に対する子孫です。（階層レベル1）
この時点で、回答は最低限「自分の親が誰か」は書き込みます。

さらに、回答に対してユーザーはそれぞれ回答をpostします。
回答は複数行われ、それらは同列として扱われます。
これは子孫に対するさらなる子孫です。（階層レベル2）
この時点で、回答は最低限「自分の親が誰か」は書き込みます。
※この時点で始祖は誰か、は持つべきなのかどうかも伺いたいです。

これを繰り返していくと、単一の始祖を起点として、
家系図のように展開していくと思います。
親子関係のレベルで1000階層程度は想定したいです。

このとき、

• このツリー構造を効率的に画面に描写したい
• 末端のpostを起点として、始祖まで一気に画面に描写したい。postは自分自身の親が誰か、は把握しているが、それを再帰的に始祖に当たるまで繰り返す事になると、DB負荷なり転送量に大きなデメリットがあり、ベターではないのではないかと、拙い理解で不安に思っている。

どのようなアプローチが最適なのか、広く皆様の見解を伺ってみたいです。

Comments

[退会済みユーザー]

FireBaseを使用したRDB？？？

Answer 1

• 一番負荷がすくないものは経路を列挙する方法

• 検索性に優れているのは入れ子集合でデータを持つ方法

ただし下記のデータは投入時に確定しづらいため親情報だけを
もったデータから任意のタイミングでプロシージャなどで作ることになります。

また親情報だけもっていれば、ネストの深さの上限がきまっているなら
その回数だけleft joinすれば簡易的に管理することは可能です

Answer 2

RDBで木構造のデータを扱う方法はよく話題にあがるのでいくつか手法が提示されています。
https://qiita.com/reflet/items/a454b40b57de81598732
それぞれ負荷や経路途中の挿入などメリット・デメリットがあるので要件と見比べてください。

Answer 3

私が作るとしても、自己参照型のツリー構造にすると思います。

id	parent_id	post
1	親
2	1	子1
3	1	子2
4	1	子3
5	2	孫1-1
6	2	孫1-2
7	3	孫2-1
8	6	ひ孫1-2-1
9	6	ひ孫1-2-2

んで、取得する時は再帰的に参照します。

WITH RECURSIVE tree AS (
SELECT posts.*, array[id] AS id_tree, '/' || post AS path, 1 AS depth FROM posts WHERE parent_id IS NULL
UNION ALL
SELECT posts.*, tree.id_tree || posts.id, tree.path || '/' || posts.post, tree.depth + 1 FROM posts INNER JOIN tree ON posts.parent_id = tree.id
)
SELECT id,post,id_tree,path,depth FROM tree;

| id | post | id_tree | path | depth |
|:--|:--:|--:|
1 | 親 | {1} | /親 | 1
2 | 子1 | {1,2} | /親/子1 | 2
3 | 子2 | {1,3} | /親/子2 | 2
4 | 子3 | {1,4} | /親/子3 | 2
5 | 孫1-1 | {1,2,5} | /親/子1/孫1-1 | 3
6 | 孫1-2 | {1,2,6} | /親/子1/孫1-2 | 3
7 | 孫2-1 | {1,3,7} | /親/子2/孫2-1 | 3
8 | ひ孫1-2-1 | {1,2,6,8} | /親/子1/孫1-2/ひ孫1-2-1 | 4
9 | ひ孫1-2-2 | {1,2,6,9} | /親/子1/孫1-2/ひ孫1-2-2 | 4

※最後のSELECT文にて、 WHERE tree.id = 8 と指定すれば、ひ孫1-2-1だけ抽出したりも当然出来ます。

ただ、負荷的にはぐるぐる回って大変なのに代わりはないので、VIEWを作っておいたりで軽減は出来ます。
個人的にはVIEWは好きではないので、負荷に耐えられるサーバを用意しますが。