1、为什么要使用左右值来表示无限极分类
一般的，我们会使用parent标志来表示节点之间的上下级关系，好处是结构清晰，修改起来很方便，缺点是查找起来稍微麻烦一点，可能需要使用递归查询，递归的使用将会使性能大幅降低尤其是递归层级多的时候。有些查找，比如统计当前节点的所有子节点个数，这就必须要递归到最后一级，所以在类似于这种需要递归到最后一级才能返回结果的场景，我们可以补充以左右值来提升性能。
以下是常规的数据结构，数据随机生成：
/**
* 生成测试数据
* php think data --action cate
* @return void
*/
protected function cate()
{
$pre = "A";
for ($i = 1; $i <= 20; $i++) {
if ($i == 1) {
$p = 0;
} else {
$p = rand(1, $i-1);
}
$name = $pre . $i;
$this->opDataModel->setTable('test111')->insert([
'id' => $i,
'name' => $name,
'p' => $p,
]);
}
}
对应的树结构
2、左右值如何表示
在上面的树结构上，从根出发，从上到下，从左到右，使用一根连续且不打结的线将所有节点串联起来，并标上序号，效果如下。注意用手指一个一个点来体会。
写入到数据库如下：
然而，我们不可能手动来实现，还是需要借助于程序，先有了树结构之后。
/**
* 将传统模式转换成左右值模式
* php think data --action initCate
* @return void
*/
protected function initCate()
{
$this->n = 1;
$this->initCateDo(0);
}
protected function initCateDo($p)
{
$list = $this->opDataModel->setTable('test111')->where('p', $p)->select();
if($list){
foreach($list as $k => $v){
$this->opDataModel->setTable('test111')->where('id', $v['id'])
->update(['left'=>$this->n++]);
$this->initCateDo($v['id']);
$this->opDataModel->setTable('test111')->where('id', $v['id'])
->update(['right'=>$this->n++]);
}
}
}
如何更新节点
显然，带有左右值的结构在更新节点的时候就没那么容易了，但是往往的无限极分类都是以查询为主的，修改操作占比较少，因此我们还是正常的修改节点，然后调用上面的方法重新生成左右值。
/**
* 增加一个节点
* php think data --action=addNode
* @return void
*/
protected function addNode()
{
$this->opDataModel->setTable('test111')->insert([
'id' => 21,
'name' => 'A21',
'p' => 14,
]);
$this->initCate();
}
4、使用场景
查看某个节点下的所有子节点
select * from test111 where id = 10;
select * from test111 where `left` > 12 and `left` < 17 ORDER BY `left` ASC;
是不是不用递归就能达到目的了。注意 BETWEEN包含首尾数值。
那么某个节点到底有多少子孙节点呢？很简单，子孙总数=(右值-左值-1)/2
select COUNT(*) from test111 where `left` > 12 and `left` < 17; // 2
c = (17 - 12 - 1) / 2 = 2
是不是很神奇，当然前提是，你的left和right得是连续的。
查找某个节点的上游路径
select * from test111 where `left` < 12 and `right` > 17 order by `left` asc;
增删节点
移动节点可以理解为先删再增。
上面已经讲到，可以通过初始化左右值的方式来达到效果，但是也有效率更高的方式，可以分析规律。
比如上面的例子在A14下面增加A21，而A14为（23，28），此时不好确定A21的左右值，但是我们知道在这个串联的线上，处于A14后面的所有节点都需要往后挪动一个位置，也就是左右值分别加2。
update test111 set `left` = `left` + 2 where `left` >= 28;
update test111 set `right` = `right` + 2 where `right` >= 28;
update test111 set `right` = 29 where id = 21;
如果A21存在子节点，那么所有的子节点的左右值加1，此时需要通过p值来判断。
左值的话就要分情况了，如果A21没有子节点，那么左值为28，如果有子节点，那么就是子节点的左值减1，放心此时它最多只有一个子节点，或者没有子节点。
看来增加节点的操作还是有点麻烦的。
删除节点就简单一些了，也可以参照着推算。
显示树结构
两种方式都可以。
列出一级分类节点
显然传统的方式更加适合。
5、总结
综上所述，在存储上，还是建议两种方式都存起来，在不同的场景下使用不同的方式。对于层次多数量大的结构使用第二种方法。如果查询量较小但是需要频繁添加和更新的数据，则第一种方法更为简便。