중첩된 세트로 트리 구조 모델링하기

개요

이 문서에서는 트리의 가변성 대신 하위 트리 검색을 최적화하는 트리와 같은 구조를 설명하는 데이터 모델을 소개합니다.

패턴

중첩 세트 패턴은 트리의 각 노드를 트리 왕복 순회 시 정지(stop) 포인트로 식별합니다. 애플리케이션은 트리의 각 노드를 두 번 방문합니다. 첫 번째 이동 시 한 번, 돌아오는 경로에 한 번입니다. 중첩 집합 패턴은 문서에 각 트리 노드를 저장하며, 문서에는 트리 노드 외에도 노드의 상위 항목(parent) ID, left 필드 내 노드의 첫 정지(stop) 포인트, right 필드 내 돌아오는 경로의 정지 포인트를 저장합니다.

다음과 같은 카테고리 계층 구조를 고려하세요:

다음 예시에서는 중첩 세트를 사용하여 트리를 모델링합니다.

db.categories.insertMany( [
   { _id: "Books", parent: 0, left: 1, right: 12 },
   { _id: "Programming", parent: "Books", left: 2, right: 11 },
   { _id: "Languages", parent: "Programming", left: 3, right: 4 },
   { _id: "Databases", parent: "Programming", left: 5, right: 10 },
   { _id: "MongoDB", parent: "Databases", left: 6, right: 7 },
   { _id: "dbm", parent: "Databases", left: 8, right: 9 }
] )

노드의 하위 노드를 쿼리 및 조회할 수 있습니다.

var databaseCategory = db.categories.findOne( { _id: "Databases" } );
db.categories.find( { left: { $gt: databaseCategory.left }, right: { $lt: databaseCategory.right } } );

중첩 세트 패턴은 하위 트리를 빠르고 효율적으로 찾을 수 있는 솔루션을 제공하지만 트리 구조를 수정하기에는 비효율적입니다. 따라서 이 패턴은 변경되지 않는 정적 트리에 가장 적합합니다.