php / Mysql лучшая древовидная структура
Я должен построить дерево, которое будет содержать около 300 узлов внутри него. Дерево не имеет ограничений по глубине. Так что может иметь 3 или 15 уровней. Каждый узел может иметь неограниченное количество детей.
Приоритет состоит в том, чтобы получить полное дерево / поддерево как можно быстрее, но мне также нужно иногда добавлять узлы или перемещать узлы, но не так часто.
Я хочу знать, как лучше всего хранить дерево в базе данных и как можно получить данные, если это возможно, в php.
3 ответа
Вы можете использовать модель вложенного набора, поскольку она дает очень эффективные запросы. Ознакомьтесь с разделом " Управление иерархическими данными в MySQL" и прочитайте раздел " Модель вложенного множества".
Если вы используете ORM, такой как Doctrine, он включает возможности вложенного набора.
Некоторым может быть трудно понять вложенный набор понятий слева и справа. Я обнаружил, что используя эти числа в качестве аналогии для номеров строк открывающих / закрывающих тегов в 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>
Видя это таким образом, для некоторых будет намного проще визуализировать результирующую иерархию вложенных множеств. Это также проясняет, почему этот подход повышает эффективность, так как позволяет выбирать целые узлы без необходимости в нескольких запросах или объединениях.
Это отличная статья об этом: Управление иерархическими данными в MySQL. Я использовал в течение длительного времени.
Если у вас есть математические возможности, вы можете понять, почему это так здорово!
<?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;
}
?>