프로그래밍 언어/Database

관계형 데이터베이스에 계층 적 데이터를 저장하는 옵션

Rateye 2021. 7. 12. 11:44
728x90
반응형

 

질문 : 관계형 데이터베이스에 계층 적 데이터를 저장하는 옵션은 무엇입니까?

좋은 개요

일반적으로 빠른 읽기 시간 (예 : 중첩 세트) 또는 빠른 쓰기 시간 (인접 목록) 중에서 결정을 내립니다. 일반적으로 필요에 가장 적합한 아래 옵션 조합으로 끝납니다. 다음은 몇 가지 심층 자료를 제공합니다.

옵션

내가 알고있는 것 및 일반적인 기능 :

  • 인접 목록 :
    • 열 : ID, ParentID
    • 구현하기 쉽습니다.
    • 저렴한 노드 이동, 삽입 및 삭제.
    • 수준, 조상 및 후손, 경로를 찾는 데 비쌉니다.
    • 이를 지원하는 데이터베이스에서 공통 테이블 표현식 을 통해 N + 1을 피하십시오.
  • 중첩 세트 (일명 수정 된 사전 주문 트리 순회 )
    • 열 : 왼쪽, 오른쪽
    • 값싼 조상, 후손
    • 휘발성 인코딩으로 인해 매우 비싼 O(n/2) 이동, 삽입, 삭제
  • 브리지 테이블 (일명클로저 테이블 / w 트리거 )
    • 상위, 하위 항목, 깊이 (선택 사항)와 함께 별도의 조인 테이블을 사용합니다.
    • 값싼 조상과 후손
    • 삽입, 업데이트, 삭제를위한 쓰기 비용 O(log n)
    • 정규화 된 인코딩 : 조인의 RDBMS 통계 및 쿼리 플래너에 적합
    • 노드 당 여러 행 필요
  • 계보 열 (구체화 된 경로 , 경로 열거라고도 함)
    • 열 : 계보 (예 : / parent / child / grandchild / etc ...)
    • 접두사 쿼리를 통한 저렴한 하위 항목 (예 : LEFT(lineage, #) = '/enumerated/path' )
    • 삽입, 업데이트, 삭제를위한 쓰기 비용 O(log n)
    • 비 관계형 : 배열 데이터 유형 또는 직렬화 된 문자열 형식에 의존
  • 중첩 된 간격
    • 중첩 세트와 비슷하지만 실수 / 부동 / 소수를 사용하여 인코딩이 휘발성이 아닙니다 (비싼 이동 / 삽입 / 삭제).
    • 실수 / 부동 / 소수 표현 / 정밀도 문제가 있습니다.
    • 매트릭스 인코딩 변형 은 "자유"에 대한 조상 인코딩 (구체화 된 경로)을 추가하지만 선형 대수의 까다로운 부분이 추가되었습니다.
  • 플랫 테이블
    • 각 레코드에 수준 및 순위 (예 : 정렬) 열을 추가하는 수정 된 인접 목록입니다.
    • 반복 / 페이지 매김이 저렴
    • 비싼 이동 및 삭제
    • 좋은 사용 : 스레드 토론-포럼 / 블로그 댓글
  • 여러 계보 열
    • 열 : 각 계보 수준에 대해 하나씩, 루트까지 모든 상위를 참조하고, 항목 수준에서 아래로 수준은 NULL로 설정됩니다.
    • 저렴한 조상, 자손, 레벨
    • 저렴한 삽입, 삭제, 잎 이동
    • 고가의 내부 노드 삽입, 삭제, 이동
    • 계층 구조의 깊이에 대한 엄격한 제한

데이터베이스 별 참고 사항

MySQL

신탁

  • CONNECT BY 를 사용하여 인접 목록 탐색

PostgreSQL

SQL 서버

답변

제가 가장 좋아하는 대답은이 스레드의 첫 번째 문장이 제안한 것과 같습니다. 인접 목록을 사용하여 계층을 유지하고 중첩 집합을 사용하여 계층을 쿼리합니다.

지금까지 문제는 Adjacecy List에서 Nested Sets로 커버링 방법이 매우 느리다는 것이 었습니다. 대부분의 사람들이 변환을 수행하기 위해 "Push Stack"이라는 극단적 인 RBAR 방법을 사용하고 비용이 많이 드는 방법으로 간주 되었기 때문입니다. 인접 목록에 의한 유지 관리의 단순성과 Nested Sets의 놀라운 성능의 열반에 도달했습니다. 결과적으로 대부분의 사람들은 특히 10 만 개 이상의 노드가있는 경우 하나 또는 다른 하나에 만족해야합니다. 푸시 스택 방법을 사용하면 MLM 관리자가 작은 백만 노드 계층 구조로 간주하는 변환을 수행하는 데 하루 종일 걸릴 수 있습니다.

불가능 해 보이는 속도로 인접 목록을 중첩 세트로 변환하는 방법을 제시함으로써 Celko에게 약간의 경쟁을 줄 것이라고 생각했습니다. 내 i5 노트북에서 푸시 스택 방식의 성능은 다음과 같습니다.

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

그리고 다음은 새 메서드의 기간입니다 (괄호 안에 푸시 스택 메서드 포함).

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

네, 맞습니다. 1 분 이내에 100 만 개의 노드가 변환되고 4 초 이내에 100,000 개의 노드가 변환됩니다.

다음 URL에서 새 메소드에 대해 읽고 코드 사본을 얻을 수 있습니다. http://www.sqlservercentral.com/articles/Hierarchy/94040/

또한 유사한 방법을 사용하여 "사전 집계 된"계층 구조를 개발했습니다. MLM 및 재료 명세서를 작성하는 사람들은 특히이 기사에 관심을 가질 것입니다. http://www.sqlservercentral.com/articles/T-SQL/94570/

두 기사 중 하나를 살펴 보려면 "토론 참여"링크로 이동하여 귀하의 생각을 알려주십시오.

출처 : https://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database
728x90
반응형

'프로그래밍 언어 > Database' 카테고리의 다른 글

MongoDB 데이터베이스의 이름을 변경하는 방법  (0) 2021.07.12
Sqlite3 데이터베이스에서 열 이름 목록을 얻는 방법  (0) 2021.07.12
SQLite의 초당 INSERT 성능 향상  (0) 2021.07.09
PostgreSQL 데이터베이스로 SQL 덤프 가져 오기  (0) 2021.07.09
데이터베이스와 함께 애플리케이션 전송 하는 방법  (0) 2021.07.09

'프로그래밍 언어/Database'의 다른글

  • 현재글관계형 데이터베이스에 계층 적 데이터를 저장하는 옵션

관련글

댓글

티스토리툴바