标签: modified-preorder-tree-t

在关系数据库中保存复合模式的"最佳实践"是什么？

我们一直在使用Modified Preorder Tree Traversal.这可以非常快速地构建整个树,但插入或删除新节点的速度非常慢(需要调整所有左右值).查询节点的子节点也不容易且非常慢.

我们注意到的另一件事是你必须确保树不会变得混乱.您需要事务锁定,否则左侧和右侧值可能会损坏,修复损坏的左侧树不是一件容易的事.

它确实工作得非常好,修改后的预订树遍历,但我想知道是否有更好的选择.

我没有CS或数据结构的背景知识.我想创建一个PHP类,它存储一个修改过的预订序横向树,用于操作和与数据库同步.

基本上我需要存储数据,如:

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

我有这张桌子:

CREATE TABLE `categories` (
  `id` int(11) NOT NULL auto_increment,
  `category_id` int(11) default NULL,
  `root_id` int(11) default NULL,
  `name` varchar(100) collate utf8_unicode_ci NOT NULL,
  `lft` int(11) NOT NULL,
  `rht` int(11) NOT NULL,
  PRIMARY KEY  (`id`),
  KEY `category_id` (`category_id`),
  KEY `lft` (`lft`,`rht`),
  KEY `root_id` (`root_id`)
) 

基于这个问题: 将修改后的预订树遍历模型(嵌套集)转换为<ul>

不同的是,我在一张桌子上有很多树.每行都有一个代表其父级及其顶级父级的外键:category_id和root_id.我还有基于这个例子的lft和rht字段:http://articles.sitepoint.com/article/hierarchical-data-database/2

基于这些行:

INSERT INTO `categories` VALUES(1, NULL, NULL, 'Fruits', 1, 14);
INSERT INTO `categories` VALUES(2, 1, 1, 'Apple', 2, 3);
INSERT INTO `categories` VALUES(3, 1, 1, 'Orange', 4, 9);
INSERT INTO …

我使用修改的预订树遍历算法保存了分层有序数据.

这是表格内容:

id  lft  rgt  name
1   1    10   topnode
2   2    3    level1
3   4    7    level1
4   5    6    level2
5   8    9    level1

可视化:

我想要的只是选择某个节点的子节点(所以不是子节点的子节点).让我们说'topnode'.我正在尝试修复查询,但我似乎无法理解它.

搜索互联网给我带来了一段时间,例如:我可以计算每个节点的深度,但我似乎无法选择它.

这个查询

SELECT node.*, (COUNT(parent.id) - 1) AS depth
FROM tree AS node
CROSS JOIN tree AS parent
WHERE (node.lft BETWEEN parent.lft AND parent.rgt)
GROUP BY node.id
ORDER BY node.lft

显示每个节点的深度:

id  lft  rgt  name     depth
1   1    10   topnode  0
2   2    3    level1   1
3   4    7    level1   1
4 …

我正在c + +中实现DFS算法以找到生成树,使用算法DFS的生成树的输出总是预先排序或者它是纯粹的巧合吗？