키-값 데이터 저장소에 디렉터리 계층 구조 저장

Question

키-값 데이터베이스(내 경우에는 MongoDB이지만 그 중 하나)에 계층 구조/트리 디렉토리를 저장하는 깨끗하고 효율적인 방법은 무엇입니까?

예를 들어 트리 구조

- Cars 
   + Audi 
   + BMW
      - M5
   + Ford
- Color
   + Red
      - Apple
      - Cherry
   + Purple
- Funny

지금 사용하고 있는 방법은 각 개체가 해당 개체의 상위 개체에 연결되는 것입니다.

{ 
  dir: "red"
  parent-dir: "color"
}

이렇게 하면 트리의 모든 측면을 삽입하고 순서를 바꾸는 것이 매우 효율적이고 빠릅니다(예를 들어 Red와 그 모든 하위 항목을 Cars 디렉터리로 이동하려는 경우).

그러나 이 방법은 주어진 디렉토리에 대한 모든 하위 디렉토리와 그 하위 디렉토리를 재귀적으로 원할 때 짜증납니다.효율적으로 구문 분석하기 위해 다음과 같은 구조를 가질 수 있습니다.

{ 
  dir: "red"
  children: "audi, bmw, ford"
}

{ 
  dir: "bmw"
  children: "m5"
}

하지만 트리를 수정하려면 전체 개체를 터치하고 수정해야 합니다.

KV 스토어에 디렉토리 구조를 저장하는 다른 방법이 있습니까?

Answer 1

현재 사용하고 있는 메소드는 다음과 같습니다. 인접 목록 모델.

(관계형) 데이터베이스에 계층적 데이터를 저장하는 또 다른 모델은 중첩 세트 모델.그것은 SQL 데이터베이스에서의 구현은 잘 알려져 있습니다..또한 참조하십시오 수정된 선주문 트리 탐색 알고리즘에 대한 이 문서.

매우 간단한 방법:객체별로 경로를 저장할 수 있습니다. 이를 사용하면 NOSQL 데이터베이스에서 트리를 쉽게 쿼리할 수 있습니다.

{ path: "Color", ... }
{ path: "Color.Red", ... }
{ path: "Color.Red.Apple", ... }
{ path: "Color.Red.Cherry", ... }

노드가 제거되거나 이름이 변경되면 일부 경로를 업데이트해야 합니다.그러나 일반적으로 이 방법은 유망해 보입니다.구분 기호로 특수 문자를 예약하면 됩니다.저장 공간 오버헤드는 무시할 수 있어야 합니다.

편집하다:이 방법이 호출됩니다 구체화된 경로

마지막으로 여기는 NOSQL 데이터베이스의 계층적 데이터에 대한 다양한 방법 비교.

Answer 2

저는 NOSQL 경험이 많지 않기 때문에 이것이 확실한 답은 아니지만, 이에 접근하는 방법은 다음과 같습니다.

나는 다음과 같은 첫 번째 접근 방식을 사용할 것입니다.

{
  dir: 'dir_name',
  parent_dir: 'parent_dir_name'
}

그런 다음 디렉토리의 하위 항목을 빠르게 쿼리하기 위해 map-reduce를 설정합니다.MongoDB의 맵 축소 기능은 여전히 ​​개발 브랜치에서만 사용할 수 있고 아직 작업해 본 적은 없지만 CouchDB(그리고 MongoDB에서 몇 가지 수정을 가하면)에서는 다음과 같은 작업을 수행할 수 있습니다.

map:
function(doc) {
  emit( doc.parent_dir, doc.dir );
}

reduce:
function(key, values) {
  return( values );
}

그러면 각 상위 디렉토리에 대한 하위 디렉토리 목록이 제공됩니다.

Answer 3

데이터 항목의 ID에 힙을 저장하는 것이 좋습니다. 나는 이것이 최고의 계획이라고 생각합니다. 많은 물건이 필요한 경우 힙 요소가 다른 힙에 대한 색인이 될 수 있습니다.

예를 들어

{ "id:xxx", "id:yyy", "sub-heap-id:zzz"....}

이것이 명확하지 않으면 의견을 게시하고 집에 도착하면 더 많은 설명을하겠습니다.

Answer 4

색인을 만드십시오!

http://www.mongodb.org/display/docs/indexes