什么是预排序遍历树算法（MPTT）

什么是预排序遍历树算法（MPTT）

在了解什么是『预排序遍历树算法』之前，我们先思考一个问题如何处理『多级分类的子分类查询』。例如：

要存储表示层级关系的数据，一种最简单的方案，存储当前分类的名称，以及上一级分类的名称，通常我们称这种存储结构为『邻接表』。

数据库存储结构：

这种方式有什么问题：查询效率过低。当我们在程序里查询 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 CHA