트리 구조 저장을 위한 NoSQL 모델 (Materialized Path, Nested Sets)

핵심 인사이트 (3줄 요약)

본질: 조직도, 카테고리, 대댓글(Thread)과 같은 계층적(Hierarchical) 트리 구조 데이터를 NoSQL(MongoDB 등)에 저장할 때, 무한한 탐색과 조인(Join)의 부하를 피하기 위해 경로(Path) 자체를 문자열로 구워 넣거나(Materialized Path), 집합의 범위(Left/Right)를 수학적으로 쪼개 넣는(Nested Sets) 역정규화 데이터 모델링 기법이다.

가치: RDBMS처럼 parent_id 하나만 덜렁 저장해 두면(Adjacency List) 하위 노드 전체를 찾기 위해 악몽 같은 재귀 쿼리(Recursive Query)나 N+1 조인을 수십 번 날려 시스템이 마비된다. 이 패턴들은 트리의 뼈대 정보를 각 노드에 미리 복제해 둠으로써 단 한 번의 O(1) 정규표현식 쿼리만으로 특정 부서의 모든 하위 조직이나 모든 자식 댓글을 광속으로 조회하게 해준다.

융합: 읽기(조회) 성능은 극적으로 상승하지만 데이터의 이동이나 삭제(Update) 시 관련된 수많은 노드의 경로/값을 갱신해야 하는 '쓰기 병목(Write Penalty)'이 필연적으로 발생하므로, 도메인의 특성(읽기 위주인가 쓰기 위주인가)에 따라 Array of Ancestors 패턴과 융합하여 적절히 선택하는 아키텍트의 결단이 요구된다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념: 트리(Tree) 구조 데이터란 뿌리(Root)부터 나뭇가지(Node)로 뻗어 나가는 데이터다 (예: 전자제품 > 컴퓨터 > 노트북 > 맥북). NoSQL은 테이블 간의 Join을 지양하기 때문에, ಈ 트리를 어떻게 설계하느냐가 시스템 성능의 성패를 가른다. 대표적인 해법으로 부모 배열(Array of Ancestors), 구체화된 경로(Materialized Path), 중첩 집합(Nested Sets)이 쓰인다.
필요성: 만약 '전자제품' 카테고리를 눌렀을 때 그 아래에 있는 모든 '노트북, 핸드폰, 냉장고'의 상품을 다 긁어와야 한다고 치자. 옛날 방식(Adjacency List: 자기 부모 ID만 가지고 있는 방식)에서는 '전자제품'의 자식을 찾고, 그 자식들의 자식을 또 찾고... 끝도 없이 DB를 들락날락(N번 호출)해야 한다. 트래픽 폭주 시 DB는 죽어버린다. NoSQL의 철학인 '읽기 최적화'를 달성하려면, 한 번의 쿼리로 전자제품 아래의 모든 자식을 퍼올릴 수 있도록 족보(경로)를 미리 각 데이터 뱃속에 문신처럼 새겨두는 강력한 꼼수가 필요했다.
💡 비유: 회사 조직도를 생각해 보세요.
- 구식 방식: 신입사원에게 "네 바로 위 팀장님이 누구야?"(parent_id)만 적어줍니다. 사장님이 "우리 본부 밑에 있는 직원 다 모여!"라고 하면, 사장님 → 본부장 → 팀장 → 신입사원 순서로 일일이 전화를 돌려야(재귀 쿼리) 모일 수 있습니다. (답답함)
- Materialized Path 방식: 아예 신입사원의 사원증에 "나는 [사장님/본부장님/팀장님/나] 소속이다"라고 족보 전체 경로(Path)를 텍스트로 인쇄해 둡니다. 사장님이 "본부장님 소속 다 모여!"라고 방송하면, 사원증에 '본부장님' 글자가 찍힌 사람만 1초 만에 튀어나오면 끝입니다. (초고속!)
등장 배경 및 발전 과정:
1. RDBMS의 재귀 CTE (Common Table Expression): SQL 표준에서는 WITH RECURSIVE 쿼리를 통해 계층 구조를 풀었으나, NoSQL은 이런 복잡한 연산 엔진이 없다.
2. MongoDB의 Array/Path 도입: MongoDB 매뉴얼에서 공식적으로 "트리 모델링 패턴" 가이드를 내놓으며, NoSQL 개발자들이 RDBMS의 멘탈 모델에서 벗어나 조인 없이 트리를 푸는 기법(Materialized Path 등)을 정석으로 삼게 되었다.
3. 다양한 패턴의 분화: 쇼핑몰 카테고리(읽기 위주)에는 Nested Sets를, 사내 게시판의 끝없는 대댓글(쓰기 위주)에는 Materialized Path를 쓰는 식의 도메인 특화 모델링 패턴으로 정교하게 분화되었다.
📢 섹션 요약 비유: 우편물을 배달할 때 동네 이름, 골목 이름, 집 번호를 일일이 지도에서 퍼즐 맞추듯 찾아가는 게 아니라, 편지 봉투 자체에 "서울시 강남구 역삼동 1번지"라는 완성된 경로(Path)를 아예 구워버려서 우체부가 고민 없이 1초 만에 배달하게 해주는 속도 혁명입니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

패턴 1: Materialized Path (구체화된 경로)

각 노드가 최상위 루트(Root)부터 자신까지 도달하는 전체 경로를 하나의 문자열(String)이나 배열(Array)로 저장한다.

  ┌───────────────────────────────────────────────────────────────┐
  │         Materialized Path 패턴의 데이터 모델링 (MongoDB 예시)      │
  ├───────────────────────────────────────────────────────────────┤
  │                                                               │
  │   [ 카테고리 트리 구조 ]                                            │
  │     Books                                                     │
  │       ├─ Programming                                          │
  │       │     └─ Database (내가 찾는 곳)                           │
  │       └─ Novel                                                │
  │                                                               │
  │   [ NoSQL Document 저장 모습 ]                                  │
  │     { _id: "Books" }                                          │
  │     { _id: "Programming", path: ",Books," }                   │
  │     { _id: "Novel",       path: ",Books," }                   │
  │     { _id: "Database",    path: ",Books,Programming," }       │
  │                                                               │
  │   ▶ 핵심 장점 (조회)                                             │
  │     "Programming 이하의 모든 카테고리를 다 가져와라!"               │
  │      ─▶ `db.categories.find({ path: /,Programming,/ })`        │
  │     (단 한 번의 정규표현식(Regex) 쿼리로 하위 뎁스 끝까지 싹쓸이 가능!)     │
  │                                                               │
  │   ▶ 단점 (수정)                                                │
  │     만약 'Programming'의 부모가 'IT'로 바뀌어 이사를 간다면?           │
  │     자식, 손자들의 `path` 텍스트를 몽땅 찾아서 정규식으로 다 바꿔줘야 함.    │
  └───────────────────────────────────────────────────────────────┘

패턴 2: Nested Sets (중첩 집합)

트리를 집합(Set)의 벤다이어그램으로 인식하고, 부모 노드의 범위 안에 자식 노드가 완벽히 포함되도록 수학적 좌표(left, right)를 부여하는 천재적인 기법이다. 트리의 각 노드를 왼쪽에서 오른쪽으로 순회하며(Pre-order Traversal) 번호를 매긴다.

  ┌───────────────────────────────────────────────────────────────┐
  │           Nested Sets 패턴의 수학적 맵핑 (좌표 기반 트리)            │
  ├───────────────────────────────────────────────────────────────┤
  │                                                               │
  │   [ 트리 구조와 Left/Right 좌표 부여 ]                           │
  │                   의류 (1, 12)                                 │
  │                    /        \                                 │
  │        남성복 (2, 7)       여성복 (8, 11)                      │
  │           /     \             |                               │
  │     바지 (3, 4) 셔츠 (5, 6) 원피스 (9, 10)                        │
  │                                                               │
  │   [ NoSQL Document 저장 모습 ]                                  │
  │     { name: "의류", left: 1, right: 12 }                       │
  │     { name: "남성복", left: 2, right: 7 }                      │
  │     { name: "셔츠", left: 5, right: 6 }                        │
  │                                                               │
  │   ▶ 핵심 장점 (부분 트리 조회)                                     │
  │     "남성복과 그 아래 모든 상품을 다 가져와라!"                       │
  │     ─▶ `db.categories.find({ left: {$gte: 2}, right: {$lte: 7} })` │
  │     (단 1번의 숫자 대소 비교 쿼리로 1억 개의 자식을 O(1) 광속 조회!)        │
  │                                                               │
  │   ▶ 치명적 단점 (추가/삭제 병목)                                  │
  │     '남성복' 아래에 '넥타이'를 하나 새로 추가하려면?                     │
  │     오른쪽에 있는 모든 상품들(여성복, 원피스 등)의 left/right 번호를     │
  │     +2씩 전부 밀어서 업데이트해 줘야 하는 끔찍한 쓰기 재앙 발생!            │
  └───────────────────────────────────────────────────────────────┘

Ⅲ. 실무 적용 및 기술사적 판단

트리 모델링 전략의 황금률 (Use Case)

이 패턴들은 트레이드오프(읽기 vs 쓰기)가 너무 극명하기 때문에 도메인의 성격에 따라 무조건 맞춤형을 써야 한다.

Adjacency List (부모 ID만 저장)
- 적합: 뎁스(Depth)가 1~2개로 매우 얕고, 데이터 추가/삭제가 매우 빈번한 경우.
- 사례: 단순 부서 조직도, 1단짜리 댓글 게시판.
Materialized Path (문자열 경로 저장)
- 적합: 뎁스가 깊고 하위 트리를 한 번에 조회할 일이 많지만, 노드의 위치 이동은 적은 경우. 문자열 파싱이 편한 언어에 유리.
- 사례: 무한 대댓글(Reddit, 네이버 뉴스 댓글), 대용량 쇼핑몰 카테고리.
Nested Sets (수학적 중첩 집합)
- 적합: 쓰기/수정(Update/Insert)이 거의 영원히 일어나지 않고, 오직 조회(Read)만 미친 듯이 발생하는 초거대 정적 트리.
- 사례: 식물 도감(문 단위부터 종 단위까지 절대 변하지 않음), 지질학적 좌표 트리, 글로벌 산업 분류 체계(GICS).

실무 시나리오

시나리오 — 무한 뎁스(Depth) 대댓글의 재앙: 게시판 시스템을 NoSQL로 만들었다. 댓글의 대댓글, 또 그 대댓글이 달릴 수 있는 무한 뎁스 구조다. 개발자가 parent_id만 저장해 두었다. 글 하나에 댓글이 5,000개 달렸을 때, 이 트리를 화면에 예쁘게(들여쓰기) 그려주기 위해 백엔드 코드가 MongoDB에 5,000번의 find() 루프 쿼리를 날려 API 서버가 터져버린 상황.
- 판단: 전형적인 Adjacency List(인접 리스트) 안티패턴에 당했다. NoSQL은 조인을 못 하므로, 뎁스만큼 N+1 쿼리가 발생한다.
- 해결책: Materialized Path 패턴으로 스키마를 마이그레이션한다. 대댓글을 달 때 부모의 경로 문자열을 복사해서 내 뒤에 붙여 저장한다(path: "001.042.003"). 게시판을 읽을 때는 게시글에 달린 모든 댓글을 1번의 쿼리로 다 쓸어온 뒤, 문자열 path 기준으로 클라이언트(또는 백엔드 메모리)에서 정렬(Sort)만 해주면 들여쓰기 뎁스(Depth)가 완벽히 재현되며 응답 속도는 5000배 빨라진다.

도입 체크리스트

기술적: Materialized Path를 쓸 때 경로 문자열이 무한히 길어지면 인덱스(Index)의 한계 사이즈(MongoDB 기준 약 1KB)를 초과할 위험이 있는가? 경로를 String으로 합치는 대신, 배열 형태 (Array of Ancestors ancestors: [1, 42, 3]) 로 저장하면 NoSQL의 멀티키 인덱스(Multikey Index)를 태울 수 있어 쿼리 성능이 극대화된다는 튜닝 팁을 적용하고 있는가?

Ⅳ. 기대효과 및 결론

정량/정성 기대효과

구분	일반적 방식 (Parent ID만 저장)	NoSQL 트리 패턴 (Path / Nested)	개선 효과
정량 (조회 I/O)	트리의 깊이(Depth) N만큼 반복 쿼리 발생	부분 트리(Sub-tree) 전체를 1번의 쿼리로 반환	하위 구조 탐색 속도 및 데이터베이스 부하 99% 단축
정량 (쓰기 병목)	삽입/이동 시 레코드 1개만 수정(빠름)	하위 자식 노드의 경로(Path)까지 전부 수정 파급	트리가 깊을수록 쓰기(Update) 지연 시간 폭발적 증가
정성 (설계 사상)	정규화에 집착한 RDBMS 사고방식의 잔재	화면 조회 패턴 중심의 철저한 역정규화 내재화	NoSQL의 장점을 100% 끌어내는 Read-heavy 아키텍처 완성

관계형(RDBMS) 시대의 데이터베이스 설계가 '예쁘고 완벽한 뼈대 조립'이었다면, NoSQL 시대의 설계는 '무엇을 잃고 무엇을 얻을 것인가'라는 야수 같은 트레이드오프(Trade-off)의 향연이다. 트리 데이터의 경로(Path)를 데이터마다 일일이 구워 넣는 것은 명백한 데이터 중복이자 쓰기 오버헤드다. 하지만 기술사는 무한 확장의 웹 생태계에서 '단 한 번의 읽기 속도(O(1))'를 쟁취하기 위해 그 추악한 중복(Denormalization)을 기꺼이 시스템의 척추로 삼는 과감한 결단력을 지녀야 한다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
역정규화 (Denormalization)	RDBMS의 조인을 피하려고, 부모의 족보(Path) 데이터를 모든 자식 문서 배 속에 욱여넣는(중복 저장) NoSQL 트리 모델링의 핵심 사상이다.
B-Tree & 멀티키 인덱스	Materialized Path(문자열)나 Array of Ancestors(배열)를 검색할 때, `Like %` 검색이나 배열 요소를 찰나에 찾아주기 위해 반드시 걸어둬야 하는 NoSQL의 색인 엔진이다.
N+1 쿼리 문제	Parent ID만 달랑 저장해 뒀을 때, 부모를 1번 찾고 그 자식 N명을 찾기 위해 쿼리를 N번 더 날려 DB를 죽여버리는 ORM 및 NoSQL의 악명 높은 버그 패턴이다.
최종 일관성 (Eventual Consistency)	Materialized Path에서 상위 폴더 이름이 바뀌어 하위 자식들 100만 개의 경로 문자를 업데이트해야 할 때, DB가 잠기지 않도록 Kafka 등을 통해 천천히 비동기로 업데이트를 맞추는 MSA 연계 기술이다.

👶 어린이를 위한 3줄 비유 설명

학교에서 선생님이 1학년 전체 학생을 부르고 싶은데, 예전에는 반장에게 전화하면 반장이 조장에게 전화하고 조장이 반원에게 일일이 전화(재귀 쿼리)해야 해서 1시간이 걸렸어요.
그래서 학교에서 아예 모든 학생의 이름표에 "나는 1학년-3반-2조-홍길동"이라고 소속 경로(Materialized Path)를 크게 써 붙이게 규칙을 바꿨어요.
이제 선생님이 마이크로 "이름표에 '1학년' 적힌 사람 다 모여!"라고 한 번만 쩌렁쩌렁 소리치면, 애들이 서로 전화 돌릴 필요 없이 1초 만에 우르르 운동장으로 뛰어 나올 수 있는 엄청난 스피드 마법이랍니다!