php/mysql 최고의 트리 구조

Question

그 안에 약 300 개의 노드를 포함 할 트리를 만들어야합니다. 나무에는 깊이가 없습니다. 그래서 그것은 3 또는 15 레벨을 가질 수 있습니다. 각 노드는 무제한의 자식을 가질 수 있습니다.

우선 순위는 최대한 빨리 전체 트리/서브 트리를 얻는 것이지만 노드를 추가하거나 노드를 이동해야하는 경우도 있습니다.

가능한 경우 데이터베이스에서 트리를 데이터베이스에 저장하는 가장 좋은 방법과 데이터를 검색하는 가장 좋은 방법을 알고 싶습니다.

Answer 1

매우 효율적인 쿼리를 생성하기 때문에 중첩 세트 모델을 사용할 수 있습니다. Managing Hierarchical Data in MySQL을 확인하고 중첩 세트 모델 섹션을 읽어보십시오.

Doctrine과 같은 ORM을 사용하는 경우 includes nested set capabilities입니다.

의 중첩 세트 개념을 이해하기 어려울 수 있습니다. 및 이 맞습니다. 나는 그 숫자를 XML 문서의 open/close 태그의 라인 번호에 대한 비유로 사용함으로써 사람들이 쉽게 파악할 수 있음을 발견했다.

예를 들어, 위의 MySQL의 링크에서 데이터의 예를 가지고 : 당신이 LFT, RGT 필드를 취할 경우

+-------------+----------------------+-----+-----+ 
| category_id | name     | lft | rgt | 
+-------------+----------------------+-----+-----+ 
|   1 | ELECTRONICS   | 1 | 20 | 
|   2 | TELEVISIONS   | 2 | 9 | 
|   3 | TUBE     | 3 | 4 | 
|   4 | LCD     | 5 | 6 | 
|   5 | PLASMA    | 7 | 8 | 
|   6 | PORTABLE ELECTRONICS | 10 | 19 | 
|   7 | MP3 PLAYERS   | 11 | 14 | 
|   8 | FLASH    | 12 | 13 | 
|   9 | CD PLAYERS   | 15 | 16 | 
|   10 | 2 WAY RADIOS   | 17 | 18 | 
+-------------+----------------------+-----+-----+ 

및 XML 문서에 대한 행 번호로 사용, 당신은 얻을 : 이런 식으로 보는

는

1. <electronics> 
2. <televisions> 
3.  <tube> 
4.  </tube> 
5.  <lcd> 
6.  </lcd> 
7.  <plasma> 
8.  </plasma> 
9.  </televisions> 
10. <portable electronics> 
11.  <mp3 players> 
12.   <flash> 
13.   </flash> 
14.  </mp3 players> 
15.  <cd players> 
16.  </cd players> 
17.  <2 way radios> 
18.  </2 way radios> 
19. </portable electronics> 
20. </electronics> 

훨씬 쉽게 어떤 결과 중첩 된 일련의 계층 구조를 시각화 할 수 있도록 할 수 있습니다. 또한 여러 가지 쿼리 또는 조인이 필요없이 전체 노드를 선택할 수 있으므로이 방법이 효율성을 향상시키는 이유를보다 명확하게 설명합니다.

Answer 2

이것에 대한 훌륭한 기사입니다 : Managing Hierarchical Data in MySQL. 나는 오랫동안 사용했다.

수학 능력이 있다면 정말 왜 그렇게 좋은지 이해할 수 있습니다!

Answer 3

  <?php 

      $host = "localhost"; 
      //Database user name. 
      $login = "root"; 
      //Database Password. 
      $dbpass = ""; 
      $dbname = "abc"; 
      $PDO = new PDO("mysql:host=localhost;dbname=$dbname", "$login", "$dbpass"); 
      $rows = array(); 
      $sql = 'SELECT id, parent_id, name FROM employee'; 
      $query = $PDO->prepare($sql); 
      $query->execute(); 
      $rows = array(); 

       if (!$query) 
       { 
        $error = 'Error fetching page structure, for nav menu generation.'; 
        exit(); 
       } 

      while($row = $query->fetch(PDO::FETCH_ASSOC)){ 
       if(strcasecmp($row['parent_id'],'null') === 0 || empty($row['parent_id'])) { 
        $row['parent_id'] = null; 
       } 

       $rows[] = $row; 
      } 


      // covert raw result set to tree 
      $menu = convertAdjacencyListToTree(null,$rows,'id','parent_id','links'); 
      // echo '<pre>',print_r($menu),'</pre>'; 

      // display menu 
      echo themeMenu($menu,1); 

      /* 
      * ------------------------------------------------------------------------------------ 
      * Utility functions 
      * ------------------------------------------------------------------------------------ 
      */ 

      /* 
      * Convert adjacency list to hierarchical tree 
      * 
      * @param value of root level parent most likely null or 0 
      * @param array result 
      * @param str name of primary key column 
      * @param str name of parent_id column - most likely parent_id 
      * @param str name of index that children will reside ie. children, etc 
      * @return array tree 
      */ 
      function convertAdjacencyListToTree($intParentId,&$arrRows,$strIdField,$strParentsIdField,$strNameResolution) { 

       $arrChildren = array(); 

       for($i=0;$i<count($arrRows);$i++) { 
        if($intParentId === $arrRows[$i][$strParentsIdField]) { 
         $arrChildren = array_merge($arrChildren,array_splice($arrRows,$i--,1)); 
        } 
       } 

       $intChildren = count($arrChildren); 
       if($intChildren != 0) { 
        for($i=0;$i<$intChildren;$i++) { 
         $arrChildren[$i][$strNameResolution] = convertAdjacencyListToTree($arrChildren[$i][$strIdField],$arrRows,$strIdField,$strParentsIdField,$strNameResolution); 
        } 
       } 

       return $arrChildren; 

      } 

      /* 
      * Theme menu 
      * 
      * @param array menu 
      * @param runner (depth) 
      * @return str themed menu 
      */ 
      function themeMenu($menu,$runner) { 

       $out = ''; 

       if(empty($menu)) { 
        return $out; 
       } 

       $out.='<ul>'; 
       foreach($menu as $link) { 
        $out.= sprintf(
         '<li class="depth-%u">%s%s</li>' 
         ,$runner 
         ,$link['name'] 
         ,themeMenu($link['links'],($runner+1)) 
        ); 
       } 

       $out.='</ul>'; 
       return $out; 

      } 

      ?>