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; 

      } 

      ?>