계층 적 순서 목록 유지 (flatfile/sql/nosql)

Question

계층 적 정렬 목록을 저장하고 싶습니다. 한 가지 예는 중첩 된 할 일 목록입니다. 또 다른 예는 XML입니다. 아이들이 주문한 나무 일뿐입니다. 단순화를 위해 항목은 텍스트 문자열입니다.

• 편집 요소
• 전에 항목을 삽입하는 요소
• 을 삭제하는 것이 중요하므로

  것은 일반적인 작업이 빠른 것을 목록은 사용자가 편집 할 것입니다 다른

데이터 구조에서이를 수행하는 방법을 상상할 수 있습니다. 항목은 링크 된 목록이고, 하위 항목이 포함되어 있으면 다른 링크 된 목록의 머리글을 가리 킵니다. 엔트리 ID를 실제 데이터에 연결하는 해시 테이블이 있습니다.

• 편집 해시를 찾고 다음
• 삭제 해시를보고
• 삽입은 해시를 찾고 있습니다
연결리스트 삭제를하고있다 링크 된 목록의 데이터 부분을 교체하고 연결리스트 삽입을하고있다

그러나 데이터를 저장할 필요가 있으며이를 달성하는 방법을 알지 못합니다. 하나의 요소 만 변경되면 전체 트리를 저장하고 싶지 않습니다. 가장 좋은 방법은 무엇입니까? 플랫 파일/SQL/NoSqls/voodoos?

Answer 1

관계형 데이터베이스를 사용하는 것이 실행 가능한 솔루션입니다.사용자의 요구를 들어 - 빠른 삽입, 업데이트, 삭제 - 나는 등의 추가 사용자 지정과 인접성 목록을 사용하십시오 :

id 
parent_id 
cardinality -- sort order for all nodes with the same parent_id 
depth -- distance from the root node 

는 cardinality을 계산하고 depth은 하나의 코드로 수행 또는 - 바람직 - 데이타베이스 트리거를 어떤을 위해 삽입, 삭제 또는 업데이트 할 수 있습니다. 또한, 하나의 SELECT 문 전체 계층을 입수하는 계층 브리지 테이블이 요구된다

id 
descendent_id 

이 테이블은 상기 한 바와 같은 트리거로 채워 상기 모든 노드를 검색하기위한 수단으로서 제공 될

또는 아래에 주어진 id.

See this question for additional detail around Adjacency List, Hierarchy Bridge and other approaches for storing hierarchical data in a relational database.

마지막으로 당신이 나열된 옵션에 대한 몇 가지 추가 설명을 제공합니다 :

• 플랫 파일 : 연결리스트와 메모리의 조합이 파일은 아마 봉사 할 것입니다 매핑,하지만 당신은 정말 그냥에서 자신의 압연있어 여기서 SQL 또는 NoSQL 솔루션이 더 잘 수행 될 것입니다.
• SQL : 이것은 내 방식 일 것입니다. 툴링은 데이터 조작, 백업 및 복구를위한 최고의 도구입니다.
  • : 이는 데이터베이스와 관련이있을 수 있습니다. 공급 업체마다 매우 다르므로 노드 삽입, 업데이트 및 삭제 구문을 연구해야합니다. 데이터베이스가 XML 데이터 유형을 제공하는 경우 매우 빠를 수 있습니다.
• NoSQL에 : 당신이 typical approach for hierarchical data appears to be materialized pathkey-value storage을 얘기하지만,이 가능성이 느린 변화에 영향을받는 모든 노드의 전체 경로를 재 계산 필요합니다. 대신 Java Content Repository (JCR)을 생각해보십시오. Apache Jackrabbit은 구현입니다. 전체 API는 계층 적 구조화 된 데이터를 표현하고이를 지속하는 데 중점을 두었습니다. 해결하려는 문제에 너무 무거울 수 있습니다.
• 부두 : 음 ...

업데이트하면,이 답변의 모든 조각을 구현하는 추가

경우가 저렴, 다시 종류의 작은 비용, 이동 비싸다. 트레이드 오프는 빠른 계층 트래버스 읽기입니다. 예를 들어 한 번의 작업으로 노드의 완전한 조상을 찾을 수 있습니다. 특히 리프 추가는 O (1) 연산입니다. 재 정렬은 이동 된 노드 다음에 오는 모든 피어 노드의 카디널리티를 업데이트하는 것을 의미합니다. 이동이란 (2) 이동 및 자손 노드 깊이, (3) 계층 구조 브리지 테이블에 조상을 제거하고 추가하는 것, (2) 이동하는 소스 및 대상 피어 노드에 대한 (1) 카디널리티의 업데이트를 의미합니다.

그러나 독점권 목록만으로는 (즉, id, parent_id) 쓰기가 저렴 해지고 한 단계의 읽기는 저렴하지만 계층 구조를 통과하는 읽기는 비용이 많이 듭니다. 후자의 경우 SQL Server 및 기타 RDBMS에서 볼 수있는 것처럼 Oracle의 CONNECT BY 또는 Common Table Expressions와 같은 재귀 SQL을 사용해야합니다.

Answer 2

목록 (또는 나무)을 저장하고 작은 나무 조각이 변경되면 전체 나무를 다시 쓰지 않으려합니다. 이것으로 나는 구조물이 거대하고 작은 변화가 상대적으로 자주 일어난다 고 결론 내린다.

링크 된 목록은 모두 포인터 추적에 관한 것이고 포인터와 참조는 키와 값과 비슷합니다. 키 - 값 쌍을 효율적으로 저장해야합니다. 항목의 순서는 연결된 목록 구조에 의해 보존됩니다.

현대적인 NoSQL 오퍼링에 대해 xDBM 또는 Berkeley DB의 일반적인 키 - 값 저장소를 사용한다고 가정합니다. 또한 소형 SQL 엔진을 사용할 수도 있습니다. sqlite. 일반적으로 키를 인덱싱하기 위해 트리를 사용하므로 키를 액세스하는 데 O (logN)가 걸리고, 그렇지 않으면 해시 테이블이 많거나 적습니다.

데이터를 점차적으로 유지할 때 지정하지 않았습니다. 모든 업데이트가 아닌 한 번만 수행한다면 데이터베이스를 기본 데이터 구조와 효과적으로 비교해야합니다. 이것은 전체 트리를 탐색해야하고 데이터베이스의 각 노드 ID를 조사해야하기 때문에 비교적 시간이 오래 걸릴 것입니다. 이것은 대수적이지만 필요한 I/O 때문에 거대한 상수가 있습니다. 그런 다음 더 이상 참조되지 않는 항목에서 영구 저장소를 정리하려고합니다. JSON으로 트리를 버리는 것이 훨씬 더 효율적입니다. 사실 그것은 많은 메모리 내 데이터베이스가하는 일입니다.

주 구조에 대한 모든 업데이트로 영구 구조를 업데이트하는 경우 주 구조를 가질 필요가 없습니다. 이미 영속 메커니즘 (및 다른 좋은 것들)을 가지고있는 Redis과 같은 메모리 내 키 - 값 저장소로 대체하는 것이 더 낫습니다.