Ch.12 사례 - 카테고리 트리를 매번 재귀로 조회한다

< 환경 세팅 | BFS, DFS, 그리고 DAG >

---

앞에서 B-Tree라는 "디스크를 위한 트리"를 봤다. 이번에는 애플리케이션 레벨에서 트리를 다루는 문제다. 같은 트리지만 다루는 위치가 다르면 고민거리도 달라진다.

12-1. 사례 설명

쇼핑몰에서 카테고리 트리를 관리한다. 카테고리는 부모-자식 관계로 계층 구조를 이룬다.

graph TD
    R["전자제품 (id=1)"] --> C1["컴퓨터 (id=2)"]
    R --> C2["스마트폰 (id=3)"]
    R --> C3["가전 (id=4)"]
    C1 --> L1["노트북"]
    C1 --> L2["데스크탑"]
    C1 --> L3["모니터"]
    C2 --> L4["안드로이드"]
    C2 --> L5["iOS"]
    C3 --> L6["TV"]
    C3 --> L7["냉장고"]

DB에는 이렇게 저장되어 있다. self-referential 테이블의 가장 흔한 패턴이다.

CREATE TABLE categories (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    parent_id INT NULL  -- 최상위는 NULL
);

주니어 개발자가 "특정 카테고리의 모든 하위 카테고리를 가져오는" API를 재귀로 만들었다.

def get_children(category_id):
    children = db.query(
        "SELECT * FROM categories WHERE parent_id = ?", category_id
    )
    result = []
    for child in children:
        result.append(child)
        result.extend(get_children(child["id"]))  # 재귀 호출
    return result

카테고리가 5단계면 잘 동작한다. 그런데 운영에 올리면 두 가지 문제가 숨어 있다.

1. 재귀 호출마다 DB 쿼리가 발생한다 (N+1 Problem의 트리 버전, Ch.13에서 자세히 다룬다)
2. 카테고리가 1,000단계 깊이면 RecursionError 발생 (Ch.4의 Stack Overflow가 여기서도 재등장한다)

12-2. 결과 예측

• 카테고리가 1,000개이고 평균 깊이가 5단계면 DB 쿼리는 몇 번 발생하는가?
• 깊이가 1,000단계면 Python의 기본 재귀 제한(1,000)에 걸리는가?
• 재귀를 반복문으로 바꾸면 Stack Overflow가 해결되는가?
• "DB가 빠르니까 쿼리 1,000번 정도는 괜찮겠지"가 맞는 말인가?

12-3. 측정

카테고리 1,000개, 평균 깊이 5단계, 루트 1개의 데이터로 세 가지 방식을 비교한다.

방식	DB 쿼리 횟수	응답 시간(p50)	응답 시간(p99)	Stack Overflow
재귀 + N+1 (현재 코드)	1,000	412 ms	1,820 ms	깊이 1,000+에서 발생
재귀 CTE (WITH RECURSIVE)	1	18 ms	47 ms	DB 엔진 한계까지 안전
Materialized Path	1	6 ms	14 ms	없음 (LIKE 한 방 쿼리)
메모리 BFS (전체 로딩 후)	1	22 ms	51 ms	없음 (Heap Stack)

측정 환경: MacBook Pro M2, MySQL 8.0, Python 3.12, FastAPI, 카테고리 1,000건. p50/p99는 k6 100 VU, 30초 부하 기준.

재귀 + N+1이 100배 느리다. "쿼리 한 번이 1ms니까 1,000번이면 1초"가 그냥 그대로 나타난다. 그것도 평균이고, 트래픽이 몰리면 Connection Pool이 같이 고갈된다 (Ch.16에서 다룬다).

12-4. 세 가지 해결 방식

방식 1: 메모리에서 트리 구성 (BFS 순회)

DB를 한 번만 때리고, 나머지는 메모리에서 처리한다.

from collections import deque

def get_all_children(root_id):
    # DB 쿼리 1번으로 전체 카테고리를 가져온다
    all_categories = db.query("SELECT id, name, parent_id FROM categories")

    # 메모리에서 부모-자식 관계를 구성 (Dict 사용 → O(1) 검색)
    children_map = {}
    for cat in all_categories:
        children_map.setdefault(cat["parent_id"], []).append(cat)

    # BFS로 하위 카테고리 수집 (재귀 없음, Stack Overflow 없음)
    result = []
    queue = deque([root_id])  # list 아닌 deque, popleft() O(1)
    while queue:
        current_id = queue.popleft()
        for child in children_map.get(current_id, []):
            result.append(child)
            queue.append(child["id"])

    return result

DB 쿼리 1번, 메모리에서 트리 순회. 카테고리가 수만 건 미만이라면 이게 가장 단순하고 빠른 답이다.

(카테고리가 수십만 건이 넘어가면 전체 로딩이 부담스러워진다. 이때부터는 방식 2 또는 3이 답이다.)

방식 2: 재귀 CTE (Common Table Expression)

MySQL 8.0+, PostgreSQL, SQLite가 지원하는 재귀 쿼리다. DB 엔진이 알아서 트리 순회를 처리한다.

WITH RECURSIVE category_tree AS (
    -- Anchor: 시작 노드
    SELECT id, name, parent_id, 0 AS depth
    FROM categories
    WHERE id = ?

    UNION ALL

    -- Recursive: 자식을 한 단계씩 확장
    SELECT c.id, c.name, c.parent_id, ct.depth + 1
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.id
)
SELECT * FROM category_tree;

쿼리가 한 번에 끝나니까 N+1이 없다. depth 컬럼을 같이 넣으면 트리 깊이도 같이 받아볼 수 있다.

CTE (Common Table Expression, 공통 테이블 표현식)

WITH 키워드로 시작하는 임시 결과 집합이다. 서브쿼리를 미리 이름 붙여서 정의해두고 본 쿼리에서 참조하는 방식이다. WITH RECURSIVE는 그 자신을 참조할 수 있는 재귀 CTE로, 트리/그래프 순회를 SQL 한 방으로 처리할 수 있다. MySQL 8.0+, PostgreSQL, SQLite, SQL Server, Oracle이 지원한다.

방식 3: Materialized Path

트리 경로를 문자열로 저장하는 방식이다. 각 행에 "내 위치까지의 경로"를 같이 적어둔다.

CREATE TABLE categories (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    parent_id INT NULL,
    path VARCHAR(500)  -- 예: "1/2/5/12"
);

id	name	parent_id	path
1	전자제품	NULL	1
2	컴퓨터	1	1/2
5	노트북	2	1/2/5
12	게이밍 노트북	5	1/2/5/12

"id=2의 모든 하위 카테고리"는 LIKE 한 방으로 끝난다.

SELECT * FROM categories WHERE path LIKE '1/2/%';

빠르고, 정렬도 자연스럽다. 단점은 경로가 바뀌면 (예: 카테고리 이동) 하위 모든 행의 path를 같이 업데이트해야 한다는 점이다. 읽기가 압도적으로 많고 쓰기가 드문 카테고리 트리에는 잘 맞는다.

Materialized Path (구체화된 경로)

트리의 각 노드에 루트부터 자기까지의 경로를 문자열로 저장하는 패턴이다. 조회는 LIKE 또는 prefix 검색 한 번으로 빠르게 끝나지만, 트리 구조 변경 시 하위 경로를 전부 갱신해야 한다. 다른 트리 저장 패턴으로는 Adjacency List(현재 코드의 parent_id), Nested Set, Closure Table이 있다. 각각의 장단점은 트래픽 패턴에 따라 다르다.

12-5. 세 가지 패턴의 트레이드오프

패턴	조회	삽입	이동	깊이 제한	적합한 상황
Adjacency List + N+1 재귀	매우 느림	빠름	빠름	재귀 제한	안 쓰는 게 답
Adjacency List + 메모리 BFS	빠름	빠름	빠름	없음	트리 크기가 작을 때
재귀 CTE	빠름	빠름	빠름	DB 한계	DB 엔진 활용
Materialized Path	매우 빠름	빠름	느림 (경로 갱신)	문자열 길이	읽기 위주

"무조건 빠른 패턴"은 없다. 트래픽 패턴과 데이터 변경 빈도를 보고 골라야 한다.

(Python에서 Django를 쓴다면 django-treebeard나 django-mptt가 Materialized Path와 Nested Set을 라이브러리로 제공한다. SQLAlchemy를 쓴다면 sqlalchemy_mptt가 있다.)

12-6. 재귀 vs 반복문 - Stack Overflow 함정

Ch.4에서 봤듯이, 재귀는 함수 호출마다 Stack Frame이 쌓인다. Python의 기본 재귀 제한은 1,000이다.

import sys
print(sys.getrecursionlimit())  # 1000 (CPython 기본값)

깊이를 예측할 수 없는 트리에 재귀를 쓰면 어느 날 운영에서 RecursionError: maximum recursion depth exceeded가 난다. 그것도 사용자가 만든 데이터에서.

# 재귀 DFS - Stack Overflow 위험
def dfs_recursive(node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for child in get_children(node):
        if child not in visited:
            dfs_recursive(child, visited)
    return visited

# 반복문 DFS - Stack Overflow 없음 (명시적 Stack 사용)
def dfs_iterative(start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for child in get_children(node):
            stack.append(child)
    return visited

반복문 버전은 list를 Stack으로 사용한다. Heap 메모리를 사용하니까 Python 재귀 제한에 걸리지 않는다. sys.setrecursionlimit(10000)으로 늘릴 수도 있지만, 그건 진짜 OS Stack까지 터지기 전까지 미루는 거지 해결이 아니다.

(Java도 마찬가지다. JVM의 Stack 크기는 -Xss로 정해진다. 기본 512KB~1MB. 깊은 재귀는 StackOverflowError를 내고 죽는다. Go의 Goroutine은 Stack이 가변이라 좀 더 너그럽지만 한계는 있다.)

실무에서 깊이를 예측할 수 없는 트리는 반복문으로 순회하는 게 안전하다. 카테고리 트리, 댓글 트리, 조직도, 파일 시스템 전부 해당된다.

---

< 환경 세팅 | BFS, DFS, 그리고 DAG >