중첩된 세트로 트리 구조 모델링하기
개요
이 문서에서는 트리의 가변성 대신 하위 트리 검색을 최적화하는 트리와 같은 구조를 설명하는 데이터 모델을 소개합니다.
패턴
중첩 세트 패턴은 트리의 각 노드를 트리 왕복 순회 시 정지(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 } } );
중첩 세트 패턴은 하위 트리를 빠르고 효율적으로 찾을 수 있는 솔루션을 제공하지만 트리 구조를 수정하기에는 비효율적입니다. 따라서 이 패턴은 변경되지 않는 정적 트리에 가장 적합합니다.