평평한 테이블에서 트리 계층을 효율적으로 구성하고 RDBMS에서 스토리지를 최적화하는 방법은 무엇입니까?

플랫 테이블에서 트리 구조 추출

효율적이고 우아한 데이터 구조 분석

'Id', 'Name', 'ParentId', 'Order'와 같은 열을 포함하는 평면 데이터 구조가 있고 목표는 트리 구조를 효율적으로 구축하는 것이라고 가정합니다. 배열 및 해시 테이블과 같은 기본 데이터 구조만 사용할 수 있는 경우 유효한 접근 방식은 다음과 같습니다.

1. 해시 테이블 만들기: 키가 'Id' 값이고 값이 해당 '이름' 값인 해시 테이블을 초기화합니다.
2. 데이터 테이블 반복: 테이블의 각 행에 대해 'Id' 및 'ParentId' 값을 검색하여 해시 테이블에 추가합니다.
3. 재귀적으로 트리 구축: 루트 노드('ParentId'가 0으로 설정됨)에서 시작하여 트리를 재귀적으로 순회합니다. 각 노드에 대해 'ParentId'에서 'Id'를 검색하고 해시 테이블에서 해당 이름을 가져와 하위 노드가 있는지 확인합니다.
4. 결과 취합: 트리를 순회하면서 원하는 출력 형식(예: HTML 또는 텍스트)을 취합합니다.

RDBMS의 트리 구조 저장 최적화

질문에 언급된 플랫 테이블 구조는 일반적인 접근 방식이지만 관계형 데이터베이스에서 트리 저장을 최적화하는 다른 방법이 있습니다.

1. 마감 테이블:

클로저 테이블은 각 상위-하위 관계를 명시적으로 저장합니다. 이를 통해 SQL 쿼리를 사용하여 자손 또는 조상을 효율적으로 검색할 수 있습니다.

예:

<code class="language-sql">CREATE TABLE ClosureTable (
  ancestor_id INT REFERENCES MyTable(id),
  descendant_id INT REFERENCES MyTable(id),
  PRIMARY KEY (ancestor_id, descendant_id)
);</code>

2. 중첩 세트:

중첩 세트는 트리의 각 노드에 정수 범위를 할당합니다. 범위 간격은 트리 계층 구조에서 노드의 위치를 ​​정의합니다.

예:

테이블:

<code class="language-sql">CREATE TABLE NestedSets (
  id INT PRIMARY KEY,
  left_value INT,
  right_value INT
);</code>

트리 구조:

<code>                       |-----|   [0, 9]   |-----|
                       |     |          |     |
                 |-----|     |-----|     |-----|
                 | [0, 2]   |     | [4, 6]   |     | [8, 9]  |
                 |         |     |         |     |        |
                |-----|   |-----|   |-----|   |-----|
                | [0, 1] |   | [2, 3] |   | [4, 5] |   | [6, 7] |
                |       |   |       |   |       |   |       |
               | [0, 0] |   | [2, 2] |   | [4, 4] |   | [6, 6] |</code>

3. 인접 목록:

인접 목록은 트리를 id와 parent_id라는 두 개의 열이 있는 테이블로 나타냅니다. 각 행은 노드를 나타내고 parent_id 열은 해당 상위 노드를 가리킵니다.

예:

<code class="language-sql">CREATE TABLE AdjacencyList (
  id INT PRIMARY KEY,
  parent_id INT REFERENCES AdjacencyList(id)
);</code>

트리 스토리지 최적화 기술의 선택은 데이터 크기, 쿼리 모드, 데이터베이스 성능 요구 사항 등의 요소에 따라 달라집니다.

추가 질문: 예, 위에서 설명한 기술(클로저 테이블, 중첩 세트, 인접 목록)을 사용하여 RDBMS에 트리 구조를 저장하는 근본적으로 더 나은 방법이 있습니다.

위 내용은 평평한 테이블에서 트리 계층을 효율적으로 구성하고 RDBMS에서 스토리지를 최적화하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!