php/Mysql 最佳树状结构
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5916482/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
php / Mysql best tree structure
提问by Marm
I have to build a tree that will contain about 300 nodes inside it. The tree has no depth limitations. So it can have 3 or 15 levels. Each node can have an unlimited number of children.
我必须构建一棵树，其中包含大约 300 个节点。树没有深度限制。所以它可以有 3 或 15 个级别。每个节点可以有无限数量的子节点。
The priority is to get a complete tree / subtree the faster as possible, but I also need to add nodes or move nodes sometimes but not that often.
优先事项是尽可能快地获得完整的树/子树，但我有时也需要添加节点或移动节点，但不是那么频繁。
I want to know the best way to store the tree in the database and the best way to retrieve the data, if possible, in php.
我想知道在数据库中存储树的最佳方法以及在 php 中检索数据的最佳方法（如果可能）。
回答by webbiedave
You can use a Nested Set Modelas it yields very efficient queries. Check out Managing Hierarchical Data in MySQLand read the section called Nested Set Model.
您可以使用嵌套集模型，因为它会产生非常有效的查询。查看在 MySQL 中管理分层数据并阅读名为Nested Set Model的部分。
If you're using an ORM like Doctrine, it includes nested set capabilities.
如果您使用像 Doctrine 这样的 ORM，它包括嵌套集功能。
It can be difficult for some to grasp the nested set concepts of leftand right.I have found that using those numbers as an analogy for the line numbers of open/close tags in an XML document, folks find it easier to grasp.
有些人可能很难掌握左和右的嵌套集合概念。我发现使用这些数字作为 XML 文档中打开/关闭标记的行号的类比，人们发现它更容易掌握。
For instance, take the data example from the MySQL link above:
例如，从上面的 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 |
+-------------+----------------------+-----+-----+
If you take the lft, rgtfields and use them as line numbers for an XML document, you get:
如果您使用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>
Seeing it this way can make it much easier for some to visualize the resulting nested set hierarchy. It also makes it clearer why this approach improves efficiency as it makes it possible to select entire nodes without the need for multiple queries or joins.
以这种方式查看它可以使某些人更容易地可视化结果嵌套集层次结构。它还更清楚地说明了为什么这种方法可以提高效率，因为它可以选择整个节点而无需多次查询或连接。
回答by Marcin
This is great article about it: Managing Hierarchical Data in MySQL. I used for a long time.
这是一篇关于它的好文章：在 MySQL 中管理分层数据。我用了很长时间。
If you have some mathematical capabilities, you can really understand why it is so great!
如果你有一些数学能力，你就可以真正理解它为什么这么棒了！
回答by Gaurav
<?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;
}
?>
