메모장 서비스를 개발하면서, 무한 뎁스(Infinite Depth)를 지원하는 폴더 및 파일 트리 구조를 설계한 과정을 기록합니다.
초기 비즈니스 요구사항
- 폴더 깊이를 무한으로 생성할 수 있어야 한다.
- 폴더와 파일 순서를 사용자가 임의로 지정할 수 있어야 한다.
프로젝트 초기에는 데이터베이스 레벨에서 트리를 완벽하게 제어하려 했으나, 시스템 리소스(DB CPU, 메모리)와 비즈니스 요구사항을 조율하며 아키텍처를 리팩토링했습니다.
초기 설계: PostgreSQL ltree 검토
초기 비즈니스 요구사항을 분석했을 때, 백엔드에서 가장 해결하기 까다로운 미션은 '특정 폴더 하위에 존재하는 모든 N-Depth의 자손(손자, 증손자) 노드들을 한 번에 찾고 제어하는 것'이었습니다.
예를 들어 특정 폴더를 통째로 다른 곳으로 이동시키거나, 특정 폴더 내에서만 파일 키워드를 검색해야 하는 상황을 가정해 보겠습니다.
일반적인 parent_id를 사용한 인접 리스트(Adjacency List) 구조라면 DB에서 재귀 쿼리를 돌리거나 N+1 쿼리를 감수해야 합니다.
이를 해결하기 위해 경로(Path)를 문자열로 저장하고 GiST 다차원 인덱스를 활용하여 하위 트리를 O(log N) 속도로 빠르게 스캔할 수 있는 PostgreSQL의 ltree 익스텐션과 Materialized Path 패턴을 적극 검토했습니다.
ltree의 장단점
특정 노드의 하위 트리를 빠르게 검색(Read)하는 데는 최적이지만, 트리 구조가 변경(Move)될 때마다 문자열 연산과 대량의 업데이트 락(Write Lock)이 발생합니다.
초기 ltree 기반 DDL
PostgreSQL
SQL
CREATE EXTENSION IF NOT EXISTS ltree;
CREATE TABLE note_folder (
id BIGINT PRIMARY KEY,
name VARCHAR(255) NOT NULL,
path ltree NOT NULL, -- 예: '1.5.12' (루트부터 현재까지의 ID 경로)
sort_order INT NOT NULL -- 사용자 임의 지정 순서 (Custom Ordering)
);
CREATE INDEX idx_folder_path_gist ON note_folder USING GIST (path);초기 ltree 기반 Entity 구조
NoteFolder.class
Java
@Entity
public class NoteFolder {
@Id
private Long id; // path 조립을 위해 INSERT 전에 ID 채번 필요 (TSID 등)
private String name;
@Column(columnDefinition = "ltree", nullable = false)
private String path;
}하지만 이 구조는 폴더를 이동시킬 때마다 속해 있는 수만 개의 하위 폴더/파일 path를 일괄 업데이트해야 하는 치명적인 쓰기 오버헤드를 안고 있었습니다.
설계 변경: 요구사항 타협과 아키텍처 변경
데이터베이스 레벨에서 트리를 완벽하게 제어하기에는 시스템 리소스(DB CPU, 메모리) 부담이 컸기 때문에 비즈니스 요구사항을 조율하게 되었습니다.
1. 임의 정렬(Custom Ordering) 포기
폴더/파일의 순서를 드래그 앤 드롭으로 임의 지정할 경우 매번 대량의 순서(sort_order) 재정렬 쿼리가 발생합니다.
옵시디언, 에버노트, Windows/Mac OS의 파일 시스템 등의 사례를 참고하여 기획 파트와 협의 하에 이를 '이름순/생성일순 정렬'로 단순화했습니다.
2. 응답 구조의 변화 (전체 트리 한 번에 로드)
프론트엔드 개발자와 논의 결과, API 통신 횟수를 줄이기 위해 클릭할 때마다 하위 폴더를 호출(Lazy Loading)하지 않고, 초기 진입 시 사용자의 '전체 중첩 트리(Nested Tree)'를 한 번에 내려주어 클라이언트에서 상태를 관리하기로 결정했습니다.
이 두 가지 결정으로 인해, 굳이 DB 레벨에서 ltree를 사용해 특정 부분 트리(Sub-tree)만 조각내어 검색할 이유가 완전히 사라졌습니다.
RDBMS는 범용적인 MySQL로 확정했고, 데이터 구조는 가장 가볍고 직관적인 Adjacency List (parent_id)로 회귀했습니다.
MySQL
SQL
-- 폴더 테이블 (path가 사라지고 parent_id만 남음)
CREATE TABLE note_folder (
id BIGINT PRIMARY KEY AUTO_INCREMENT,
member_id BIGINT NOT NULL,
parent_id BIGINT COMMENT 'NULL이면 최상위 루트 폴더',
name VARCHAR(255) NOT NULL
);
CREATE INDEX idx_folder_member_parent ON note_folder (member_id, parent_id);
-- 노트(파일) 테이블
CREATE TABLE note_file (
id BIGINT PRIMARY KEY AUTO_INCREMENT,
member_id BIGINT NOT NULL,
note_folder_id BIGINT NULL COMMENT 'NULL이면 최상위 루트 파일',
title VARCHAR(255) NOT NULL
);
CREATE INDEX idx_file_member_folder ON note_file (member_id, note_folder_id);경로 문자열(path)이 사라지면서, 데이터 삽입 시 분산 ID(TSID)를 메모리에서 미리 채번해야 했던 복잡성도 사라지고 단순한 단일 INSERT 구조를 사용할 수 있게 되었습니다.
DB 연산 최소화와 인메모리(In-Memory) 트리 조립
가장 큰 난관은 { child: [ { child: [] } ] } 형태의 중첩 트리(Nested Tree)로 전체 데이터를 응답해야 한다는 점이었습니다.
RDBMS에서 쿼리로 트리를 만들려 하면 조인과 정렬로 인해 DB CPU에 큰 부하가 가해집니다.
따라서 DB에서는 평탄화(Flat)된 리스트만 가져오고, Spring Boot 애플리케이션의 메모리(HashMap)에서 O(N) 시간 복잡도로 트리를 조립하고 정렬하는 방식을 채택했습니다.
사용자 1인당 생성할 수 있는 폴더와 파일의 최대 기대치를 고려했을 때, 해당 데이터를 애플리케이션 메모리에 올려서 조립하더라도 서버 리소스에 안전하다고 판단했습니다.
NoteTreeReadService.class
Java
@Service
@RequiredArgsConstructor
public class NoteTreeReadService {
private final FolderRepository folderRepository;
private final FileRepository fileRepository;
private final NoteOptionRepository noteOptionRepository;
@Transactional(readOnly = true)
public List<NoteDirListDto> getFullTree(long memberId) {
// 1. 유저별 정렬 옵션 로드
boolean isAscending = noteOptionRepository.findById(memberId)
.map(NoteOption::getIsAscending).orElse(true);
// 2. DB 연산 최소화: 인덱스를 태워 평탄화된 데이터 일괄 로드
List<NoteFolder> folders = folderRepository.findByMemberId(memberId);
List<NoteFile> files = fileRepository.findByMemberId(memberId);
Map<Long, NoteDirListDto> nodeMap = new HashMap<>();
List<NoteDirListDto> rootNodes = new ArrayList<>();
// 3. 폴더 노드 맵핑 (Type: DIR)
folders.forEach(f -> nodeMap.put(
f.getId(),
NoteDirListDto.builder()
.id(f.getId())
.name(f.getName())
.type("DIR")
.build()
));
// 4. 폴더 트리 조립
folders.forEach(f -> {
NoteDirListDto current = nodeMap.get(f.getId());
if (f.getParentId() == null) {
rootNodes.add(current); // 루트 폴더
} else {
NoteDirListDto parent = nodeMap.get(f.getParentId());
if (parent != null) parent.getChild().add(current);
else rootNodes.add(current); // 부모가 유실된 노드는 루트로 편입
}
});
// 5. 파일 노드 맵핑 및 조립
files.forEach(file -> {
NoteDirListDto fileDto = NoteDirListDto.builder()
.id(file.getId())
.name(file.getTitle())
.type("FILE")
.build();
if (file.getNoteFolderId() == null) {
rootNodes.add(fileDto); // 루트 파일
} else {
NoteDirListDto parent = nodeMap.get(file.getNoteFolderId());
if (parent != null) parent.getChild().add(fileDto);
}
});
// 6. 메모리 정렬 (Timsort 활용 O(N log N))
sortTree(rootNodes, isAscending);
return rootNodes;
}
// WAS의 Timsort 연산으로 오프로딩(Offloading)하여 DB의 ORDER BY 부하를 방지
private void sortTree(List<NoteDirListDto> nodes, boolean isAscending) {
nodes.sort((a, b) -> {
int typeCompare = a.getType().compareTo(b.getType()); // DIR 우선 정렬
if (typeCompare != 0) return typeCompare;
int nameCompare = a.getName().compareToIgnoreCase(b.getName());
return isAscending ? nameCompare : -nameCompare;
});
nodes.forEach(node -> {
if (!node.getChild().isEmpty()) sortTree(node.getChild(), isAscending);
});
}
}이 방식을 통해 수만 건의 노드 병합 및 정렬 처리가 애플리케이션 메모리 위에서 10~20ms 이내로 안전하게 완료됩니다.
여담: 자바스크립트 숫자 정밀도 손실(Precision Loss)
프론트엔드 연동 중, 백엔드에서는 정상적인 Long 타입 ID(1234567890123456789)가 브라우저에서는 끝자리 정밀도가 손실된 값(1234567890123456770)으로 변형되는 치명적인 버그가 발생했습니다.
이는 자바스크립트 Number 타입(IEEE 754)이 안전하게 표현할 수 있는 최대 정수(16자리)를 백엔드의 ID 값이 초과했기 때문이었습니다.
잘못된 ID 전송은 타인의 데이터를 수정하는 심각한 오작동을 유발할 수 있으므로, 응답 DTO의 ID 필드를 String으로 직렬화하도록 조치하여 해결했습니다.
Java
public class NoteDirDto {
// 프론트엔드에는 문자열("id": "12345...")로 전달되어 정밀도 손실 방지
@JsonSerialize(using = ToStringSerializer.class)
private Long id;
// ...
}마무리
기능적 욕심(ltree, 사용자 임의 정렬)을 덜어내고 본질(이름순 정렬, 계층 렌더링)에 집중한 결과, 시스템 아키텍처를 훨씬 단순하고 견고하게 만들 수 있었습니다.
복잡한 문제를 가장 단순한 자료구조(HashMap)와 쿼리로 풀어내는 과정에서 백엔드 개발자로서 큰 배움을 얻었습니다.
