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

이 페이지의 내용

개요

패턴

개요

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

패턴

중첩 세트 패턴은 트리의 각 노드를 트리 왕복 순회 시 정지(stop) 포인트로 식별합니다. 애플리케이션은 트리의 각 노드를 두 번 방문합니다. 첫 번째는 초기 이동 중에, 두 번째는 복귀 중에 방문합니다. 중첩 세트 패턴은 문서에 각 트리 노드를 저장합니다. 문서는 트리 노드 외에도 상위 노드의 ID, left 필드에서 노드의 초기 중지, right 필드 반환 중지 ID를 저장합니다.

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

계층형 데이터의 예시입니다. 숫자는 트리를 왕복 이동하는 동안 노드에서 정차하는 위치를 나타냅니다.

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

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 } } );

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

돌아가기

구체화된 경로

특정 애플리케이션 컨텍스트