什么是预排序遍历树算法（MPTT）
在了解什么是『预排序遍历树算法』之前，我们先思考⼀个问题如何处理『多级分类的⼦分类查询』。例如：
要存储表⽰层级关系的数据，⼀种最简单的⽅案，存储当前分类的名称，以及上⼀级分类的名称，通常我们称这种存储结构为『邻接表』。
数据库存储结构：
分类名称⽗级分类
food
fruit food
meat food
apple fruit
breef meat
pork meat
这种⽅式有什么问题：查询效率过低。当我们在程序⾥查询 food 的⼦分类时，要先在数据库中，查询 food 的⼀级⼦分类（fruit、meat）、在对⼀级分类的⼦分类进⾏递归查询，需要进⾏ logN 次（ N 为
⼦分类个数） I/O 操作（向数据库进⾏查询），这样的查询效率不⾼，但是很容易实现。
⽽ MPTT 预排序⽣成树算法正是为了解决多层级关系数据的查询效率问题。
MPTT 是什么？
MPTT（Modified Preorder Tree Taversal）预排序遍历树算法，主要应⽤于层级关系的存储和遍历。
在 MPTT 中是如何表⽰层级关系的：
MTTP 不直接存储⽗分类信息，⽽是通过 left、right 指来表⽰层级关系。
还是以 food 为例，我们从头开始构建⼀棵『预排序遍历树』。
# 创建数据表，left_value、right_value 表⽰左右⼦树区间
CREATE TABLE`product_category`(
`id`int(11)NOT NULL AUTO_INCREMENT,
category_name varchar(20)not null,
left_value int(10)not null,
right_value int(10)not null,
PRIMARY KEY(`id`)
)ENGINE=InnoDB DEFAULT CHARSET=utf8;
然后开始插⼊ food 的⼀级⼦分类，根据当前分类的 left_value 来确定插⼊分类的左右值，同时更新受影响的其他分类。
show code，插⼊⼦分类
INSERT into product_category(category_name,`left_value`,`right_value`)
values('food',1,2);# 插⼊ food 数据
# 锁表，防⽌被同时修改，数据不⼀致
lock table`product_category`write;
# 插⼊ food ⼦分类
select@myLeft :=`left_value`
from`product_category`
where category_name='food';
# 更新其他受影响分类左右区间值
update product_category SET left_value=left_value+2
where left_value>@myLeft;
update product_category set right_value=right_value+2
where right_value>@myLeft;
# 插⼊⼦分类信息
INSERT into product_category(category_name,`left_value`,`right_value`)
values('meat',@myLeft+1,@myLeft+2);
unlock tables;# 解除表锁定
除了插⼊⼦分类的⽅式，我们还可以选择 插⼊同级分类，和插⼊⼦分类的区别在于，插⼊点的左右值取决于被插⼊点的 right_value。# 插⼊ meat 同级分类
lock table`product_category`write;
select@myRight :=`right_value`
from`product_category`
where category_name='meat';
update product_category SET left_value=left_value+2
where left_value>@myRight;
update product_category set right_value=right_value+2
where right_value>@myRight;
INSERT into product_category(category_name,`left_value`,`right_value`)
values('fruit',@myRight+1,@myRight+2);
unlock tables;
删除指定分类，也等于删除包括指定分类在内的所有⼦分类，所有受影响左右⼦分类都受影响。
# 删除 meat 分类
lock table`product_category`write;
select@myLeft:=`left_value`,@myRight:=`right_value`,@myDiff:=@myRight-@myLeft+1
from`product_category`
where`category_name`='meat';
delete from`product_category`
where`left_value`>=@myLeft and`right_value`<=@myRight;
update`product_category`
set`right_value`=`right_value`-@myDiff
where`right_value`>@myRight;
update是什么
update`product_category`
set`left_value`=`right_value`-@myDiff
where`left_value`>@myLeft;
unlock tables;
那如何 查询指定分类的⼦分类 呢？
select@myLeft:=`left_value`,@myRight:=`right_value`
from`product_category`
where`category_name`='meat';# 指定分类名称
select*
from`product_category`
where`left_value`>=@myLeft and`right_value`<=@myRight;# 不包括指定分类，去掉等号即可
通过 MPTT 我们查询某⼀特定分类的⼦分类信息只要做两次查询操作，解决了『邻接表』递归查询的低效查询问题。
『邻接表』和『预排序遍历树』的优劣
『邻接表』，适⽤于 增删改 操作较多的场景，每次删改只需要修改⼀条数据。在查询⽅⾯，随着 分类层级的增加『邻接表』的递归查询效率逐渐降低。
『预排序遍历树』，适⽤于 查询 操作较多的场景，查询的效率不受分类层级的增加的影响，但是随着数据的增多，每增删数据，都要同时操作多条受影响数据，执⾏效率逐渐下降。
具体要选择哪⼀种存储结构和算法，需要根据具体的应⽤场景来做选择。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。