php/Mysql最佳樹結構

Question

我必須構建一棵樹，其中將包含約300個節點。樹沒有深度限制。所以它可以有3個或15個級別。每個節點可以有無限數量的子節點。

優先考慮的是儘可能快地獲得完整的樹/子樹，但我也需要添加節點或移動節點，但有時候並不經常。

我想知道在數據庫中存儲樹的最佳方式，以及如果可能的話，在php中檢索數據的最佳方法。

Answer 1

您可以使用嵌套集模型，因爲它可以產生非常有效的查詢。檢出Managing Hierarchical Data in MySQL並閱讀嵌套式模型一節。

如果您使用的是像Doctrine這樣的ORM，它includes nested set capabilities。

對於某些人來說，可能很難掌握左邊的和的嵌套集合概念。我發現使用這些數字作爲XML文檔中打開/關閉標籤行數的類比，人們發現它更易於理解。

例如，從上面的MySQL的鏈接採取了數據示例：

+-------------+----------------------+-----+-----+ 
| 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 | 
+-------------+----------------------+-----+-----+ 

如果拿LFT，RGT領域，並把它們作爲一個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; 

      } 

      ?>