데이터베이스

계층 구조를 문자열로 저장하는 Path Enumeration

전제

Adjacency List의 재귀 조회 문제를 우회하는 방식 중 하나다. 계층 구조를 저장하는 Closure Table에서 비교 대상으로만 짧게 언급했었다. 같은 계열의 Nested Set과 함께 보면 차이가 뚜렷하다.

왜 필요한가

인접 리스트(parent_id만 저장)는 조상·자손 조회에 재귀가 필요하다. Path Enumeration은 각 행에 루트부터 자신까지의 경로를 문자열로 저장해, 이 조회를 문자열 매칭으로 바꾼다. 추가 테이블 없이 컬럼 하나만 더하면 된다는 게 가장 큰 매력이다.

용어 정리

Materialized Path라는 이름으로도 불린다. “경로를 미리 계산해(materialize) 저장해둔다”는 뜻이다. PostgreSQL의 ltree 확장 문서도 이 개념을 같은 이름으로 설명한다.

핵심 정리

내용
저장 컬럼 path (문자열, 구분자로 구간을 나눔)
자손 조회 path LIKE '자기경로%'
조상 조회 자기 path를 파싱하거나, 역방향 LIKE '%자기경로'
삽입·이동 비용 자신과 하위 트리 노드의 path만 수정
인덱스 활용 접두사 매칭(LIKE 'x%')은 인덱스를 타지만, 접미사 매칭은 타지 못한다

항목별 설명

경로는 구분자(보통 /)로 상위 노드의 id를 이어붙인 문자열이다. 쇼핑몰 카테고리를 예로 든다.

id name path
1 전자제품 /1/
2 노트북 /1/2/
3 게이밍노트북 /1/2/3/
4 사무용노트북 /1/2/4/
5 가전 /1/5/
6 냉장고 /1/5/6/

자손 조회는 접두사 매칭이라 인덱스를 탄다. 조상 조회는 방향이 반대라서 사정이 다르다. “게이밍노트북(id=3)의 조상”을 구하려면 다른 행의 path가 /1/2/3/의 접두사인지를 봐야 하는데, 이건 WHERE '/1/2/3/' LIKE path || '%' 형태가 되어 인덱스를 타지 못한다. 그래서 조상 조회는 자기 path를 애플리케이션에서 파싱해 id 목록(1, 2, 3)을 뽑아낸 뒤 IN 절로 조회하는 방식을 더 많이 쓴다.

예시

-- 노트북(2)의 모든 하위 카테고리
SELECT * FROM category
WHERE path LIKE '/1/2/%' AND id != 2;
-- 결과: 게이밍노트북(3), 사무용노트북(4)

-- 게이밍노트북(3)의 조상 — path를 파싱해서 IN으로 조회
SELECT id, name FROM category
WHERE id IN (1, 2, 3)
ORDER BY LENGTH(path);
-- 결과: 전자제품(1), 노트북(2), 게이밍노트북(3) 순 → 브레드크럼으로 그대로 사용

댓글·대댓글 정렬에도 같은 원리가 쓰인다.

id content path
1 원 댓글 /1/
2 대댓글 /1/2/
3 대댓글의 대댓글 /1/2/3/
4 다른 대댓글 /1/4/ 
SELECT * FROM comment ORDER BY path;
-- 1, 2, 3, 4 순 — 트리를 깊이 우선으로 순회한 순서와 같다

혼동하기 쉬운 것

ORDER BY path 정렬은 자릿수가 다르면 깨진다. id를 그대로 이어붙이면 문자열 사전순 정렬이 된다. /1/2/와 /1/10/을 비교하면 두 번째 구간에서 '1'이 '2'보다 작아 /1/10/이 /1/2/보다 앞에 온다. 실제로는 10이 2의 하위가 아닌데도 그렇게 보이는 게 문제가 아니라, 2와 형제인 10이 2보다 먼저 나와야 하는데 순서가 뒤바뀌는 게 문제다. 방지책은 고정 자릿수로 0-padding하거나(/0001/0010/), 정렬 전용 컬럼을 따로 둔다.

접두사 LIKE와 접미사 LIKE는 성능이 다르다. path LIKE '/1/2/%'(접두사 고정, 뒤가 와일드카드)는 B-Tree 인덱스를 탄다. 반대로 앞이 와일드카드인 패턴은 인덱스를 못 타서 전체 스캔이 된다.

구현체별 차이

PostgreSQL은 이 패턴을 문자열 컬럼으로 손수 구현하지 않아도 되도록 ltree 타입을 제공한다. 레이블 경로를 전용 타입으로 다루고, <@(자손인지)·@>(조상인지) 연산자와 GiST 인덱스를 지원해 조상·자손 조회 양쪽 다 인덱스를 탈 수 있다. 문자열 컬럼과 LIKE로 직접 구현하기 전에 DBMS가 이미 지원하는지부터 확인할 만하다.

언제 어떤 것을 쓰나

경로 자체를 화면에 노출하고 싶을 때 강점이 크다. 쇼핑몰 브레드크럼(가전 > 냉장고), 파일 탐색기의 디렉터리 경로, 댓글 트리를 ORDER BY path 하나로 깊이 우선 순서 그대로 보여주는 경우가 그렇다. 값 자체가 이미 사람이 읽을 수 있는 형태라 별도 가공 없이 쓸 수 있다.

반대로 조회가 압도적으로 많고 트리 구조가 거의 바뀌지 않는다면 Nested Set이 더 적합하다. 범위 비교 하나로 끝나기 때문이다.

더 깊이

참고