>  기사  >  백엔드 개발  >  트리 데이터 구조 저장 방법(쿼리)

트리 데이터 구조 저장 방법(쿼리)

藏色散人
藏色散人앞으로
2019-09-07 11:05:303291검색

인접 목록 모델

일상적인 비즈니스 개발에서 우리는 종종 계층 구조를 가진 트리 같은 데이터를 접하게 됩니다. 관계형 데이터베이스에 저장될 때 이 데이터 구조는 종종 다음과 같이 인접 목록이라는 모델에 저장됩니다.

CREATE TABLE `categories` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `title` char(100) NOT NULL,
  `pid` int(11) DEFAULT 0,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

트리 데이터 구조 저장 방법(쿼리)

이 모델이 나타내는 그림은 다음과 같습니다. 데이터 모델에 익숙하므로 여기서는 너무 자세히 설명하지 않겠습니다. 다음 데이터 모델

트리 데이터 구조 저장 방법(쿼리)nested set model

에 집중해 보겠습니다. 트리를 표현하는 또 다른 방법은 트리를 세트로 저장하는 것입니다. 다음 테이블 구조를 재정의합니다.

CREATE TABLE `categories` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `title` char(100) NOT NULL,
  `lft` int(11) NOT NULL UNIQUE CHECK (lft> 0),
  `rgt` int(11) NOT NULL UNIQUE CHECK (rgt> 1),
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

이 모델의 다이어그램은 다음과 같습니다.

트리 데이터 구조 저장 방법(쿼리)

lft와 rgt는 둘 사이의 차이가 클수록 더 커집니다. 세트 내부에는 더 많은 요소가 있습니다.

하위 집합을 기준으로 부모의 분류를 찾습니다트리 데이터 구조 저장 방법(쿼리)

SELECT c2.* 
  FROM categories as c1, categories as c2
  WHERE c1.lft BETWEEN c2.lft and c2.rgt 
      AND c1.title = '华为';
+----+-------------+-----+-----+
| id | title       | lft | rgt |
+----+-------------+-----+-----+
|  1 | Smartphones |   1 |  14 |
|  5 | Harmony OS  |  10 |  13 |
|  8 | 华为        |  11 |  12 |
+----+-------------+-----+-----+

부모를 기준으로 그 아래의 모든 하위 집합을 찾습니다.

SELECT c1.*
   FROM categories AS c1, categories AS c2
  WHERE c1.lft BETWEEN c2.lft AND c2.rgt
    AND c2.title = 'Smartphones';
+----+-------------+-----+-----+
| id | title       | lft | rgt |
+----+-------------+-----+-----+
|  1 | Smartphones |   1 |  14 |
|  3 | Android     |   2 |   5 |
|  4 | iOS         |   6 |   9 |
|  5 | Harmony OS  |  10 |  13 |
|  6 | 小米        |   3 |   4 |
|  7 | iPhone      |   7 |   8 |
|  8 | 华为        |  11 |  12 |
+----+-------------+-----+-----+

각 분류의 수준 보기

 SELECT COUNT(c2.id) AS indentation, c1.title
  FROM categories AS c1, categories AS c2下周三we'fv
  WHERE c1.lft BETWEEN c2.lft AND c2.rgt
  GROUP BY c1.title
  ORDER BY c1.lft;
+-------------+-------------+
| indentation | title       |
+-------------+-------------+
|           1 | Smartphones |
|           2 | Android     |
|           3 | 小米        |
|           2 | iOS         |
|           3 | iPhone      |
|           2 | Harmony OS  |
|           3 | 华为        |
+-------------+-------------+

인접 목록 모델

Adjacency 목록 모델 이해하기 쉽고 필요한 코드도 간단합니다.

그러나 대부분의 프로그래밍 언어에서는 느리고 비효율적입니다. 이는 대부분 재귀로 인해 발생합니다. 트리의 각 노드에 대해 데이터베이스 쿼리를 수행해야 합니다.

각 쿼리에 시간이 걸리기 때문에 큰 트리를 처리할 때 기능이 매우 느려질 수 있습니다. 각 함수마다 숫자를 얻으려면 재귀 알고리즘이 필요하기 때문입니다.

물론 List처럼 재귀에 친화적인 언어를 사용한다면 이 데이터 모델의 단점을 무시할 수 있습니다. 그러나 PHP의 경우 이 데이터 모델의 전체 처리 속도가 매우 느려집니다.

중첩 집합 모델

인접 목록 모델에 비해 이 데이터 모델은 분명히 이해하기 쉽지 않습니다. 그리고 데이터 추가가 그렇게 간단할 수가 없습니다. 추가할 때 왼쪽과 오른쪽의 값을 계산하고, 후속 값을 이동해야 하므로 데이터 추가에 대한 부담이 커집니다.

마찬가지로, 간단한 쿼리로 트리 쿼리를 완성할 수 있고, 두 매개변수 lft와 rgt를 기반으로 하위 요소 수를 계산할 수 있다는 이점이 있습니다.

요약

두 모델 모두 장단점이 있는데, 하나는 삽입보다 좋고 다른 하나는 쿼리보다 좋습니다. 나는 중첩 세트 모델을 선호하지만 여전히 특정 비즈니스에 따라 선택해야 합니다.

위 내용은 트리 데이터 구조 저장 방법(쿼리)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
이 기사는 learnku.com에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제