预排序遍历树
预排序遍历树算法
预排序遍历树算法(modified preorder tree traversal algorithm)是一种为查询而生的遍历树算法，如果业务需求要求查询的场景高于、多于增删改，可以考虑此算法，该算法会牺牲掉一些插入、删除的性能。算法简单概括：类二叉树先序遍历，将树上的每个节点标示 left、right、level、parent 属性（parent 可以更方便画出树结构），查询通过 left 和 right 取值，一般情况可以通过一条 sql 查询和排序出整个需要的树节点。
为了能够像上面的递归函数那样显示整个树状结构，我们还需要对这样的查询进行排序。用节点的左值进行排序：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
添加同一层次的节点的方法如下：
LOCK TABLE nested_category WRITE;
SELECT @myRight := rgt FROM nested_category WHERE name = 'Cherry';
UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;
INSERT INTO nested_category(name, lft, rgt) VALUES('Strawberry', @myRight + 1, @myRight + 2);
UNLOCK TABLES;
添加树的子节点的方法如下：
LOCK TABLE nested_category WRITE;
SELECT @myLeft := lft FROM nested_category WHERE name = 'Beef';
UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO nested_category(name, lft, rgt) VALUES('charqui', @myLeft + 1, @myLeft + 2);
UNLOCK TABLES;
每次插入节点之后都可以用以下 SQL 进行查看验证：
SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;