RDB에서 계층 구조를 나타내기에 가장 일반적이고 자연스러운 방법
Foreign Key로 자식 노드, 부모 노드를 가르킨다.
FK가 가르키고 있는 부모, 자식 노드를 찾기 위해 Recursive한 메소드가 필요하다.
간단한 계층 구조에서 적합한 방법이지만 복잡한 계층 구조에서는 쿼리 작성 난이도 상승, Join으로 인한 DB 성능 저하가 발생할 수 있다.
class Node(models.Model):
parent = models.ForeignKey(
"self",
on_delete=models.CASCADE,
related_name='child'
)
...
from itertools import chain
from typing import Iterable
def get_descendants(node: Node) -> Iterable[Node]:
queryset = Node.objects.filter(parent=node)
results = chain(queryset)
for child in queryset:
results = chain(results, get_descendants(child))
return results
descendants_of_node_7 = list(get_descendants(Node.objects.get(pk=7)))
# [4, 10, 6, 5, 11]
def get_ascendants(node: Node) -> Iterable[Node]:
if node.parent:
return chain([node.parent], get_ancestors(node.parent))
return chain()
ascendants_of_node_11 = get_ascendants(Node.objects.get(pk=11))
# [6, 7, 2]
# descendants_of_node_7 = list(get_descendants(Node.objects.get(pk=7)))
SELECT t1.id, t2.id, t3.id, t4.id
FROM Node as t1
LEFT JOIN Node as t2 ON t2.parent_id=t1.id
LEFT JOIN Node as t3 ON t3.parent_id=t2.id
LEFT JOIN Node as t4 ON t4.parent_id=t3.id
WHERE t1.id = 7
WITH RECURSIVE descendants
(id, name, depth, parent_id)
AS (
SELECT
id,
name,
0,
parent_id,
FROM Node
WHERE parent_id is NULL
UNION ALL
SELECT
N1.id,
N1.name,
T1.depth + 1,
T1.id,
FROM Node N1, descendants T1
WHERE N1.parent_id = T1.id
)
SELECT * FROM descendants
WHERE depth > 0
ORDER BY depth, parent_id;
postgresql
의 경우 WITH
clause를 이용한 recursive cte는 parent query로부터 fetch하며 쿼리를 반복한다.postgresql
docs에서는 production level에서 사용하지 않기를 권하고, 분석용으로 사용하기를 권한다. (DB 엔진마다 작동방식이 달라 결과가 달라질 수 있기 때문에)itertools.chain()을 이용한 쿼리셋 합치기
Recursive SQL Queries with PostgreSQLRecursive SQL Queries with PostgreSQL
Do it in sql recursive tree traversal
Joe Celko's Trees and Hierarchies in SQL for Smarties