MPTT预排序算法

邻接表

类似菜单信息的信息查询，如需要查询子节点，可通过parentId进行递归调用查询。但是查询次数需要进行 logN 次（ N 为子分类个数） I/O 操作（向数据库进行查询），这样的查询效率不高，但是很容易实现。

MPTT(modified preorder tree traversal algorithm)是什么?

MPTT预排序遍历树算法，主要应用于层级的关系的存储和遍历。
在MPTT数据层级的表示:

MPTT不存储父节点的信息，通过left，right表示自己所在的层级，level。

若我们想查询 fruit的子集节点，我们只需要查询到fruit的left 和right 数值，然后再根据这2个参数值筛选即可。
从查询角度来讲只需要查询两次。

MPTT算法和邻接表的比较

邻接表的使用场景，适用于增删改较多的场景，因为每次只需要修改一条数据。随着分层的累加邻接表递归效率降低
预排序遍历树，适用于查询场景较多的场景，因为每次修改都会影响多条数据。查询的效率不会受分层的影响。