PHP Mysql 트리 구조(무한 분류) 데이터베이스 설계의 두 가지 예_php 기술

카테고리, 메뉴, 포럼 게시물에 대한 트리 응답 등과 같은 일부 트리 구조 데이터를 관계형 데이터베이스에 저장해야 하는 경우가 많습니다. 일반적으로 사용되는 두 가지 방법이 있습니다:

1. 양식 수집 방법

2. 사전 정렬 트리 순회 방법

트리 구조는 다음과 같다고 가정합니다.

테이블 픽업 방법

주로 상위 노드를 가리키고 인접한 상위 및 하위 노드를 연결하는 데 사용되는 상위 필드에 의존합니다. id는 자동으로 증가하고 parent_id는 상위 노드의 ID입니다. 얼핏 보면 "Java"는 "Language"의 자식 노드이다.

우리는 트리를 표시하고 싶습니다. PHP 코드도 매우 직관적일 수 있습니다. 코드는 다음과 같습니다.

코드 복사 코드는 다음과 같습니다.

/**
* 상위 노드 아래의 모든 하위 노드 가져오기
*
* @since2011-05-18
*
* @param $parent_id 상위 노드 id, 0은 전체 트리 구조를 표시합니다.
* @param $level 현재 노드가 위치한 레벨로, 표시된 노드를 들여쓰기하는 데 사용됩니다.
* @return 무효
​*/
show_children 함수($parent_id = 0, $level = 0)
{
// 상위 노드 아래의 모든 하위 노드를 가져옵니다.
$result = mysql_query('SELECT id, name FROM tree WHERE parent_id=' . intval($parent_id));
// 각 하위 노드 표시
동안($row = mysql_fetch_array($result)) {
​​​​//들여쓰기 표시
echo '

' . $row['name'] .               // 현재 함수를 재귀적으로 호출하고 다음 수준의 하위 노드를 표시합니다
          show_children($row['id'], $level 1);
}
}
?>

전체 트리 구조를 표시하려면 show_children()을 호출하세요. "Database" 하위 트리를 표시하려면 "Database"의 ID가 2이므로 show_children(2)을 호출합니다.

자주 사용되는 또 다른 기능은 노드 경로를 가져오는 것, 즉 노드가 주어지면 루트 노드에서 현재 노드까지의 경로를 반환하는 것입니다. 해당 기능은 다음과 같이 구현됩니다.

코드 복사 코드는 다음과 같습니다.

/**
* @param $id 경로를 얻어야 하는 현재 노드의 ID입니다.
* @return 배열
​*/
함수 get_path($id)
{
//현재 노드의 상위 노드 ID와 현재 노드 이름을 가져옵니다
$result = mysql_query('SELECT parent_id, name FROM tree WHERE id='.intval($id));
$row = mysql_fetch_array($result);
//이 배열을 사용하여 경로를 저장하세요
$path = 배열();
//현재 노드 이름을 경로 배열에 저장
$path[] = $row['이름'];
// 부모 노드가 0이 아닌 경우, 즉 루트 노드가 아닌 경우 재귀 호출을 통해 부모 노드의 경로를 구한다
If ($row['parent_id']) {
                 // 재귀 호출, 상위 노드의 경로를 가져와 현재 경로 배열의 다른 요소 앞에 병합
          $path = array_merge(get_path($row['parent_id']), $path);
}
$path 반환;
}
?>

"MySQL 5.0"의 경로를 얻으려면 get_path(4)를 호출하세요. 4는 이 노드의 ID입니다.

테이블 수집 방식의 장점은 이해하기 쉽고 코드가 비교적 간단하고 명확하다는 것입니다. 단점은 재귀 SQL 쿼리로 인해 부하가 증가한다는 점이며, 특히 상대적으로 큰 트리 구조를 처리해야 하는 경우 레벨이 높아질수록 쿼리 문이 증가하므로 WEB 애플리케이션의 병목 현상은 기본적으로 데이터베이스에 있습니다. 이는 트리 구조의 확장을 직접적으로 어렵게 만드는 치명적인 단점이다.

정렬 트리 순회 방법

이제 두 번째 방법인 선주문 트리 순회 방법(일반적으로 MPTT, Modified Preorder Tree Traversal이라고도 함)에 대해 이야기하겠습니다. 이 알고리즘은 다음 그림과 같이 노드의 순회 순서를 식별하기 위해 각 노드에 왼쪽 및 오른쪽 숫자를 추가하는 첫 번째 방법을 기반으로 합니다.

루트 노드부터 왼쪽이 1이 되고, 다음 노드의 왼쪽이 2가 되는 식으로, 최하위 노드에 도달한 후 최하위 노드의 오른쪽이 1을 더합니다. 왼쪽에. 이 노드를 따라가면 전체 트리를 쉽게 탐색할 수 있습니다. 위 그림에 따르면 데이터 테이블을 일부 변경하고 왼쪽과 오른쪽 숫자를 저장하는 데 사용되는 두 개의 필드 lft와 rgt를 추가합니다(왼쪽과 오른쪽은 MySQL의 예약어이므로 대신 약어를 사용합니다). 테이블의 각 행 내용은 다음과 같습니다.

다음으로 트리/하위 트리를 표시하는 것이 얼마나 간단한지 살펴보겠습니다. 예를 들어 "데이터베이스" 하위 트리를 표시하려면 "데이터베이스"의 왼쪽 및 오른쪽 번호를 가져와야 합니다. 왼쪽은 2이고 오른쪽은 11입니다. , SQL 문은 다음과 같습니다.

코드 복사 코드는 다음과 같습니다.

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

SQL 문은 간단하지만 우리가 원하는 들여쓰기 표시가 문제입니다. 들여쓰기는 언제 표시해야 합니까? 들여쓰기할 단위는 몇 개입니까? 이 문제를 해결하려면 스택, 즉 LIFO(후입선출)를 사용해야 합니다. 노드에 도달할 때마다 해당 노드의 오른쪽에 있는 숫자를 스택에 밀어넣습니다. 모든 노드의 오른쪽 값이 상위 노드의 오른쪽 값보다 작다는 것을 알고 있습니다. 그런 다음 현재 노드의 오른쪽 값을 스택 상단의 올바른 값과 비교합니다. 현재 노드가 스택 상단의 값보다 작다는 것은 현재 스택의 값이 임을 의미합니다. 나머지는 부모 노드입니다. 이때 들여쓰기는 스택의 요소 수입니다. 들여쓰기 깊이. PHP 코드는 다음과 같이 구현됩니다.

코드 복사 코드는 다음과 같습니다.

/**
* @param $root_id 표시할 트리/하위 트리의 루트 노드 ID입니다.
​*/
함수 show_tree($root_id = 1)
{
// 현재 루트 노드의 왼쪽 및 오른쪽 값을 가져옵니다
$result = mysql_query('SELECT lft, rgt FROM tree WHERE id='.intval($root_id));
$row = mysql_fetch_array($result);
// 스택, 노드 오른쪽에 값을 저장하고 들여쓰기를 표시하는 데 사용
$스택 = 배열();
// $root_id 노드의 모든 하위 노드를 가져옵니다
$result = mysql_query('SELECT name, lft, rgt FROM tree WHERE lft BETWEEN '.$row['lft'].' AND '.$row['rgt'].' ORDER BY lft ASC');
// 트리의 각 노드를 표시합니다
동안($row = mysql_fetch_array($result)) {
            if (count($stack)>0) { //스택이 비어 있지 않은 경우에만 감지
// 현재 노드의 오른쪽 값이 스택 맨 위의 값보다 크면, 이 값에 해당하는 노드는 현재 노드의 부모 노드가 아니므로 스택 맨 위의 값을 제거한다.
while ($row['rgt'] > $stack[count($stack)-1]) {
                 array_pop($stack);
                  } //while 루프가 끝난 후 현재 노드의 상위 노드만 스택에 남습니다
       }
             // 이제 들여쓰기를 표시할 수 있습니다
echo '

'.$row['name'].'

';
                // 현재 노드를 스택에 푸시하고 루프 후 노드의 들여쓰기 표시를 준비합니다
         array_push($stack, $row['rgt']);
}
}
?>

전체 트리를 얻으려면 show_tree()를 호출하고, "데이터베이스" 하위 트리를 얻으려면 show_tree(2)를 호출하십시오. 이 함수에서는 마침내 재귀를 사용할 필요가 없습니다. 하하.

다음 단계는 루트 노드에서 특정 노드까지의 경로를 표시하는 것입니다. 이는 테이블 액세스 방법보다 훨씬 간단합니다. 예를 들어 "ORACLE"의 경로를 가져오는 작업은 필요하지 않습니다. 노드의 왼쪽과 오른쪽 값은 각각 7과 10이고 SQL 문은 다음과 같습니다.

코드 복사 코드는 다음과 같습니다.

WHERE lft = 10 ORDER BY lft ASC;
트리에서 이름 선택

PHP 함수는 다음과 같이 구현됩니다.

코드 복사 코드는 다음과 같습니다.

/**
* @param $node_id 경로를 얻어야 하는 노드 id
​*/
함수 get_path2($node_id) {
// 현재 노드의 왼쪽 및 오른쪽 값을 가져옵니다
$result = mysql_query('SELECT lft, rgt FROM tree WHERE id='.intval($node_id));
$row = mysql_fetch_array($result);
//경로의 모든 노드를 가져옵니다
$result = mysql_query('SELECT name FROM tree WHERE lft = '.$row['rgt'].' ORDER BY lft ASC');
$path = 배열();
동안($row = mysql_fetch_array($result)) {
          $path[] = $row['name'];
}
$path 반환;
}
?>

트리와 경로를 표시하는 데 문제가 없습니다. 이제 노드를 삽입하는 방법을 알아야 합니다. 새 노드를 삽입하기 전에 먼저 이 노드를 위한 공간을 만들어야 합니다. 이제 "ORACLE 9i" 노드 오른쪽에 "ORACLE 10"을 추가하려고 한다고 가정합니다. 비울 SQL 문은 다음과 같습니다(올바른 값). "ORACLE 9i"는 9):

코드 복사 코드는 다음과 같습니다.

업데이트 트리 SET rgt=rgt 2 WHERE rgt>9;
업데이트 트리 SET lft=lft 2 WHERE lft>9;

위치는 무료입니다. 새 노드 삽입을 시작하세요.

코드 복사 코드는 다음과 같습니다.

INSERT INTO 트리 SET lft=10, rgt=11, name='ORACLE 10';

결과가 올바른지 확인하려면 show_tree()를 호출하세요. 여기에는 특정 PHP 구현 코드가 작성되지 않습니다.

이제 사전 정렬된 트리 탐색의 장점과 단점을 요약해 보겠습니다. 단점은 알고리즘이 상대적으로 추상적이고 이해하기 어렵다는 점입니다. 노드를 추가할 때 몇 가지 SQL 문만 사용하더라도 많은 레코드를 업데이트해야 하므로 차단이 발생할 수 있습니다. 장점은 리드 테이블 방식보다 트리 구조와 경로 획득 성능이 훨씬 좋다는 점이다. 즉, 이 알고리즘은 읽기 성능을 희생하는 대신 쓰기 성능을 희생합니다. WEB 응용 프로그램에서는 데이터베이스를 읽는 비율이 데이터베이스를 쓰는 비율보다 훨씬 크기 때문에 사전 정렬 트리 순회 방법이 더 많이 사용됩니다. 리드 테이블 방법이며 더 실용적이며 MPTT의 그림자는 많은 응용 프로그램에서 볼 수 있으며 일반적으로 lft 및 rgt 필드가 사용되는 테이블에 포함됩니다.