浅谈Django中的mptt

层级结构

层级结构，也叫树形结构。在实际应用中，你经常需要保存层级结构到数据库中。比如说：你的网站上的目录。不过，除非使用类XML的数据库，通用的关系数据库很难做到这点。

对于树形数据的存储有很多种方案。主要的方法有两种：邻接表模型，以及修改过的前序遍历算法。因为mptt使用的是修改过的前序遍历算法，而此算法又是从邻接表改进得来的，所以本文先要说这两块。

本文以食品商店为例，通过类别、颜色以及种类来对其食品进行分类。

邻接列表模型(ADJACENCY LIST MODEL)

邻接列表模型的实现很优雅，只需要一个简单的递归。

在我们的食品店中，邻接列表的表格如下：

通过邻接表模型存储法中，我们可以看到Pear，它的父节点是Green，而Green的父节点又是Fruit，以此类推。而根节点是没有父节点的。这里为了方便观看，parent字段使用的字符串，实际应用中只要使用每个节点的ID即可。

现在已经在数据库中插入完毕数据，接下来开始先显示这棵树。

打印

public static void displayTree(int parentId, int level) throws SQLException {setUp();ResultSet result = dbc.query("SELECT ID, title FROM `adjacency_list` WHERE parentid="+ parentId);while(result.next()){System.out.println(repeatStr("  ", level) + result.getString("title"));displayTree(result.getInt("ID"), level+1);}
}

打印结果如下

FoodFruitRedCherryYellowBananaMeatBeefPork

注意如果你只想看一个子树，你可以告诉函数从另一个节点开始。例如，要显示“Fruit”子树，你只要displayTree(2,0)

节点的路径

利用类似的函数，我们也可以通过节点的ID来查询它的路径。

例如，“Cherry”的路径是“Food”>“Fruit”>“Red”。要获得这个路径，我们的函数要获得这个路径，这个函数必须从最深的层次开始：“Cheery”。然后查找这个节点的父节点，并添加到路径中。在我们的例子中，这个父节点是“Red”。如果我们知道“Red”是“Cherry”的父节点。

public static List<String> getPath(int id)throws SQLException {List<String> paths = new ArrayList<String>();setUp();ResultSet result = dbc.query("SELECT parentid, title FROM `adjacency_list` WHERE ID="+ id);result.next();int parentid = result.getInt("parentid");if(parentid != 0)paths.addAll(getPath(parentid));paths.add(result.getString("title"));return paths;
}

结果如下

Food -> Fruit -> Red -> Cherry

优缺点

我们可以看到，用邻接表模型确实是个不错的方法。它简单易懂，而且实现的代码写起来也很容易。

但是，邻接表模型执行起来效率低下和缓慢。

第一个原因是数据库访问的代价，我们在递归中，每次访问一个节点就需要进行数据库查询。每个查询需要一些时间,这使得函数非常缓慢的在处理大树时。

第二个原因是递归这个方法自身的代价。对于一门程序语言来说，除了Lisp这种，大多数不是为了递归而设计。当一个节点深度为4时，它得同时生成4个函数实例，它们都需要花费时间、占用一定的内存空间。所以，邻接表模型效率的低下可想而知。

树前序遍历的算法变形

那么就让我们来看另外一种存储树形结构的方法。如之前所讲，我们希望能够减少查询的数量，最好是只做到查询一次数据库。

现在我们把树竖着放。如下图所示，我们首先从根节点（“Food”）开始，先在它左侧标记“1”，然后我们到“Fruit”，左侧标记“2”，接着按照前序遍历的顺序遍历完树，依次在每个节点的左右侧标记数字。最后一个数字写在“Food”节点右边的。

在这张图片里,你可以看到用数字标记的整个树和几个箭头指示编号顺序。

对于参加过算法竞赛的同学，这种方式就是一个种简单的dfs出入序列。我们通常可以通过这种序列处理一棵子树上面的问题。在这儿，我们称这些数字为Left和Right(例如“Food”的Left值是1,Right值是18)。

对于这样的序列如何处理子树，举一个例子：我们可以注意到，左数大于2、右数小于11的节点都是“Fruit”的子孙。所以这就是一个种区间包含的关系、

现在，所有的节点将以左数-右数的方式存储，这种通过遍历一个树、然后给每一个节点标注左数、右数的方式称为修改过的前序遍历算法。

在我们继续之前,让我们来看看在我们的表的这些值:

注意,“Left”和“Right”在SQL中有特殊的意义。因此,我们必须使用“lft”和“rgt”标识列。还要注意,我们并不真的需要“parent”列了。我们现在有lft和rgt值存储树结构。

获取树

如果你要通过左值和右值来显示这个树的话，你要首先标识出你要获取的那些节点。例如，如果你想获得“Fruit”子树，你要选择那些左值在2到11的节点。用SQL语句表达：