RDB에서 계층형 데이터를 관리하는 방법

모놀리식으로 개발했던 시스템들을 MSA로 전환하면서 실수를 보완하고 변경된 요구사항에 맞춰서 많은 것들을 바꾸고 있습니다. 특히 부동산 프로젝트 관리 도메인을 마이크로 서비스로 만들때는 다양한 프로젝트 관련 메타데이터들을 RDB에서 어떻게 관리할지 고민이 되었습니다. 어떤 문제를 인지했는지, 어떻게 해결했는지 공유하겠습니다.

---

문제인지

프로젝트 관리를 위해서는 프로젝트에 적절히 메타데이터를 부여해야했습니다. 이러한 메타데이터는 N 개로 늘어날수도 있으며, 심지어 하나의 메타데이터 카테고리 안에서 위계가 생겨나는 중이었죠.

 

처음에는 가볍게 생각했습니다. "000 이라는 카테고리에 하위 개념이 생기면 테이블 하나 더 만들지 뭐!" 하지만 얼마 지나지않아 그렇게 풀면 안되는 문제라는 것을 깨달았습니다.

• 매번 위계가 생길때마가 테이블을 만드는 것은 비효율적이며
• FrontEnd 개발자와 약속했던 API Interface가 바뀌어야 했습니다.

쿠팡 등 커머스 서비스를 보면 다양한 카테고리가 있는데 그들이 이렇게 비효율적으로 일할것같지 않을것 같다는 생각을 쭉 해오고 해결법을 찾았다가 MSA로 변경하는 김에 같이 바꿨습니다.

---

해결방법들

당연하게도 이러한 문제 의식을 가진건 제가 처음이 아니었고, 2010년대 초반을 기점으로 다양한 레퍼런스를 찾을 수 있었습니다. RDB는 데이터 자체를 Flat하게 다루는데 최적화 되어 있기 때문에 위계가 있는 데이터를 어떻게 Flat하게 다룰지가 포인트였습니다. 그리고 선배 개발자분들이 고안한 해결책은 다음과 같습니다

Adjacency List Model

각 행이 자신의 부모 노드 식별자(parent id)를 저장하는 구조입니다. 예를 들어, 아래와 같이 간단한 테이블을 구성할 수 있습니다.

+-------------+----------------------+--------+
| category_id | name                 | parent |
+-------------+----------------------+--------+
|           1 | ELECTRONICS          |   NULL |
|           2 | TELEVISIONS          |      1 |
|           3 | TUBE                 |      2 |
|           4 | LCD                  |      2 |
|           5 | PLASMA               |      2 |
|           6 | PORTABLE ELECTRONICS |      1 |
|           7 | MP3 PLAYERS          |      6 |
|           8 | FLASH                |      7 |
|           9 | CD PLAYERS           |      6 |
|          10 | 2 WAY RADIOS         |      6 |
+-------------+----------------------+--------+

상당히 직관적이고 구현도 쉬울것 같습니다. 하지만 다음의 기준으로 살펴볼 필요가 있습니다.

 

전체 Hierarchy 조회:

각 노드가 단일 부모를 가리키므로, 전체 트리를 조회하기 위해 재귀적 탐색(예: WITH RECURSIVE 쿼리)을 사용해야 합니다, 시간복잡도: 최악 O(n)

단일 Hierarchy Path 조회:

 단일 경로는 부모를 재귀적으로 따라가므로 데이터 양이 적으면 문제가 없음, 시간복잡도: O(depth)

종말 Node(Leaf) 조회:

설명: LEFT JOIN이나 서브쿼리로 자식이 없는 노드를 찾을 수 있으나, 전체 데이터 스캔 필요, 시간복잡도: O(n) 

Hierarchy Node 추가/삭제:

단일 INSERT 또는 DELETE 쿼리로 노드 추가/삭제 가능 (부모 ID만 처리하면 됨), 시간복잡도: O(1)

---

Nested Set Model

이 해법은 테이블로 보면 다소 난해해집니다. 그래서 아래의 그림을 보는게 가장 직관적입니다:

https://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

 

ELECTRONICS 라는 대분류 안에 TELEVISIONS, PORTABLE ELECTROFICS 가 나뉘고 그 이하에 다른 카테고리들이 있습니다.

 

이제 이 그림을 X 좌표계에 올리고 좌우 양끝점을 통해 범주를 계산한다고 생각해보겠습니다. 그렇다면 ELECTRONICS의 시작 x 값이 가장 작고 종료 x 값이 제일 커야겠죠? 반대로 TELEVISIONS, PORTABLE ELECTROFICS 의 범위 값은 ELECTRONICS 보다 작아야하고 서로 겹치지 않아야합니다. 이렇한 개념을 RDB 테이블에서 표현하면 다음과 같습니다:

+-------------+----------------------+-----+-----+
| category_id | name                 | lft | rgt |
+-------------+----------------------+-----+-----+
|           1 | ELECTRONICS          |   1 |  20 |
|           2 | TELEVISIONS          |   2 |   9 |
|           3 | TUBE                 |   3 |   4 |
|           4 | LCD                  |   5 |   6 |
|           5 | PLASMA               |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |  10 |  19 |
|           7 | MP3 PLAYERS          |  11 |  14 |
|           8 | FLASH                |  12 |  13 |
|           9 | CD PLAYERS           |  15 |  16 |
|          10 | 2 WAY RADIOS         |  17 |  18 |
+-------------+----------------------+-----+-----+

 

다시 공통 기준에서 살펴보겠습니다.

 

전체 Hierarchy 조회:

각 노드에 미리 계산된 lft와 rgt 값을 이용하여, 단일 범위(BETWEEN) 쿼리로 전체 서브트리를 빠르게 조회할 수 있습니다, 시간복잡도: O(1) ~ O(log n)

단일 Hierarchy Path 조회:

특정 노드에 대한 전체 경로는 해당 노드의 lft/rgt 값 범위를 활용하여 즉시 조회할 수 있습니다, 시간복잡도: O(1) ~ O(log n)

종말 Node(Leaf) 조회:

설명: Leaf 노드는 일반적으로 rgt = lft + 1 조건을 만족하므로, 이를 통해 빠르게 조회할 수 있습니다, 시간복잡도: O(1)

Hierarchy Node 추가/삭제:

노드 삽입이나 삭제 시, 전체 트리에서 영향을 받는 left/right 값들을 재계산하고 업데이트해야 하므로, 작업 비용이 많이 듭니다, 시간복잡도: O(n)

---

Closure Table

개인적으로 RDB에서 계층형 데이터를 다룰때 가장 RDB스럽게 풀어낸 방법이라고 생각합니다. 바로 데이터 테이블과 계층정보를 다루는 테이블을 분리하는 것입니다. 위의 해법들과는 다르게 테이블이 2개 생긴다는(따라서 공간복잡도가 커지는) 특징이 있습니다.

https://kntmr.hatenablog.com/entry/2020/08/14/080000

다시 공통기준에서 살펴보자면

 

전체 Hierarchy 조회:

모든 조상–자손 관계가 별도의 테이블에 저장되어 있으므로, 단일 JOIN으로 전체 서브트리를 빠르게 조회할 수 있습니다, 시간복잡도: O(1) ~ O(log n)

단일 Hierarchy Path 조회:

Closure Table에 미리 계산된 경로 정보를 통해 특정 노드의 전체 경로를 단순 JOIN이나 WHERE 조건으로 조회할 수 있습니다, 시간복잡도: O(1) ~ O(log n) 

종말 Node(Leaf) 조회:

자식이 없는 노드의 경우, Closure Table에서 관련 조상–자손 관계가 없음을 조건으로 빠르게 필터링할 수 있습니다, 시간복잡도: O(1) ~ O(log n) 

Hierarchy Node 추가/삭제:

노드 추가 시, 부모의 모든 조상 관계를 새로운 노드와 연결하는 다수의 INSERT가 필요하며, 삭제 시에도 관련된 모든 관계를 제거해야 합니다, 시간복잡도: O(a) 또는 O(r) (여기서 a는 추가할 조상 수, r은 삭제할 관련 관계 수; 일반적으로 트리 깊이에 비례)

---

postgresql의 ltree

ltree는 PostgreSQL의 확장(extension) 기능 중 하나로, 계층적(트리형) 데이터 구조를 문자열(경로)의 형태로 저장하고, 이 경로를 기준으로 효율적으로 검색할 수 있는 데이터 타입을 제공합니다. 각 노드의 위치는 루트에서 해당 노드까지의 “경로”를 나타내는 문자열로 저장됩니다. 예를 들어, 파일 시스템의 경로처럼 'Top.Middle.Bottom'으로 표현할 수 있습니다. ltree 만을 위한 @> 연산자, <@ 연산자와 기타 함수(예: nlevel(), subpath()) 들이 제공됩니다.

https://dba.stackexchange.com/questions/90797/how-to-update-the-parent-child-of-all-rows-in-the-tree-ltree

 

전체 Hierarchy 조회:

ltree 전용 인덱스와 <@ 연산자 등으로 경로 기반 조회를 수행할 수 있어, 전체 서브트리를 매우 빠르게 조회할 수 있습니다, 시간복잡도: O(1) ~ O(log n)

단일 Hierarchy Path 조회:

경로 문자열을 기반으로 접두사 매칭 연산을 사용하여, 특정 노드까지의 경로를 즉시 추출할 수 있습니다, 시간복잡도: O(1) ~ O(log n)

종말 Node(Leaf) 조회:

ltree는 기본적으로 경로 정보만 저장하므로, Leaf 여부 판별을 위해 경로 길이 등의 추가 계산이 필요할 수 있지만, 적절히 최적화하면 빠르게 조회할 수 있습니다, 시간복잡도: 보통 (약간의 추가 계산 필요)

Hierarchy Node 추가/삭제:

노드 추가나 이동 시, 해당 노드의 경로 문자열을 계산하여 업데이트해야 합니다. 인덱스 재구성이 필요하므로 비용이 들 수 있으나, 데이터 규모가 작다면 큰 부담은 없습니다, 시간복잡도: O(1) ~ O(log n) (경로 재계산 비용 포함)

효율성 종합 

모델	노드 추가	노드 삭제	전체 조회	단일 Path 조회	종말 Node(Leaf) 조회
Adjacency List	시간복잡도: O(1)	시간복잡도: O(1)	시간복잡도: 최악 O(n)	시간복잡도: O(depth) (depth는 보통 작음)	시간복잡도: O(n)
Nested Set	시간복잡도: O(n)	시간복잡도: O(n)	시간복잡도: O(1) ~ O(log n)	시간복잡도: O(1) ~ O(log n)	시간복잡도: O(1)
Closure Table	시간복잡도: O(a), a는 조상 수 (최악 O(n))	시간복잡도: O(r), r은 관련 관계 수 (최악 O(n))	시간복잡도: O(1) ~ O(log n)	시간복잡도: O(1) ~ O(log n)	시간복잡도: O(1) ~ O(log n)
PostgreSQL ltree	시간복잡도: O(1) ~ O(log n) (데이터량이 작으면 거의 O(1))	시간복잡도: O(1) ~ O(log n)	시간복잡도: O(1) ~ O(log n)	시간복잡도: O(1) ~ O(log n)	시간복잡도: O(1) ~ O(log n)

---

해결방법 선택

데이터의 전체 건수(N)가 많을수록, 그리고 위계 깊이가 깊을수록 각각의 알고리즘이 가진 시간복잡도와 공간 복잡도가 중요한 고려 대상이 됩니다. 또한 읽기(READ) 연산이 압도적으로 많은 경우, Insert/Update 비용보다는 조회 성능이 우선되기 때문에 전체 Hierarchy 조회 및 특정 경로 조회의 효율성이 결정적인 요소가 됩니다. 이러한 기준에서 주관적으로 평가를 해보자면:

Adjacency List Model

구조가 간단하여 구현이 쉽고, 단일 노드의 추가/삭제는 매우 빠르지만, 읽기 성능이 좋지 않기 때문에 소규모 프로젝트에 적합하다고 판단됩니다.

Nested Set Model

lft/rgt 값을 이용한 범위 쿼리로 전체 서브트리 조회 및 특정 경로 조회가 매우 빠르며, 인덱스가 잘 구성되면 조회 성능이 뛰어납니다. 다만  노드 추가/삭제시 전체 트리의 lft/rgt 를 계산해야하므로 업데이트 비용이 매우 높아집니다.

 

다양한 위계를 가진 다수의 데이터를 다루며, 읽기 연산이 압도적으로 많은 경우에 적합합니다.

Closure Table

각 노드의 모든 조상–자손 관계를 별도 테이블에 미리 저장하기 때문에, 전체 조회나 특정 경로 조회가 단순 JOIN이나 WHERE 조건으로 빠르게 수행됩니다. 노드 추가/삭제시 처리해야 할 작업은 있지만, 구현 복잡도 측면에서는 비교적 간단합니다. 다만 대량의 데이터에 대해서 공간복잡도가 크게 증가되는 문제가 있습니다.

 

하지만 일반적으로 계층형 데이터가 대량이기는 어렵기에 공간복잡도는 큰 문제가 되지 않을 것으로 보이며, 오히려 가장 RDB다운 해법이라고 판단됩니다.

PostgreSQL ltree

성능측면에서 나무랄데가 없습니다. 다만 특정 RDBMS에 종속성이 생긴다는 점, 그리고 특정 러닝커브가 생긴다는 점에서 부정적입니다.

최종 결론

저의 주관을 종합해보면 읽기 연산이 압도적으로 많은 환경에서는:

• Nested Set Model과 Closure Table이 조회 성능 면에서 우수합니다.
• Nested Set Model은 조회 쿼리가 매우 빠르지만, 노드 추가/삭제 시 전체 트리 재계산 등 업데이트 비용이 높습니다.
• Closure Table은 조회 성능도 뛰어나면서, 노드 추가/삭제 작업에 있어서도 구현이 비교적 간단하며, RDB를 이용한 해결책이라는 점이 더 잘 와닿습니다.

• PostgreSQL ltree는 기능적으로 매우 매력적이지만, 특정 RDBMS(즉, PostgreSQL)에 종속성이 생긴다는 점에서 범용성이 떨어진다고 생각합니다.
• Adjacency List Model은 구현이 간단하고 단순한 수정 작업에는 효과적이지만, 조회 연산이 많은 경우에는 재귀 탐색 비용 때문에 효율성이 떨어집니다.

따라서, 전체 Record 수(N)가 상대적으로 적고, 위계 깊이(Depth)가 2~5 정도인 환경에서, READ 연산이 주를 이루는 상황이라면, 공간 복잡도만 감수할 수 있다면 Closure Table 방식이 Nested Set 방식보다 구현 복잡도 면에서 우수하며, RDB 기반 해법으로서도 더 직관적이라고 판단됩니다.

Response Interface는?

백엔드 개발자로서 또 하나의 고민은 DB는 저렇게 해결한다고 하는데 "프론트에게 내려주는 데이터 구조는 어떻게 가야하는걸까?" 입니다. 이러한 고민은 백엔드 뿐만 아니라 프론트도 많이 해왔고, React 진영에는 관련 라이브러리가 있는것을 확인했습니다. 

 

그 결과 다음과 같이 데이터를 내려주는 것으로 합의가 되었습니다.

 

{
    "id": 1,
    "name": "item1",
    "parentId": null,
    "depth": 0
},
{
    "id": 2,
    "name": "item1.1",
    "parentId": 1,
    "depth": 1
},
{
    "id": 3,
    "name": "item1.2",
    "parentId": 1,
    "depth": 1
},
{
    "id": 4,
    "name": "item2",
    "parentId": null,
    "depth": 0
}

 

---

참고

managing-hierarchical-data-in-mysql:  https://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

closure table: https://fueled.com/the-cache/posts/backend/closure-table/

closure talbe: https://kntmr.hatenablog.com/entry/2020/08/14/080000

postgresql ltree: https://www.postgresql.org/docs/16/ltree.html

postgresql ltree: https://patshaughnessy.net/2017/12/13/saving-a-tree-in-postgres-using-ltree