[数据库]数据库存储层级结构数据

无论你想建立自己的论坛,在你的网站上从一个邮件列表发布消息,或编写自己的cms:你将会遇到一种情况：将分层数据（层级结构）存储在数据库中。除非你使用一个类似xml的数据库,通用的关系型数据库是很难做到这一点。关系型数据库中的表不分层;他们只是一个简单

无论你想建立自己的论坛,在你的网站上从一个邮件列表发布消息,或编写自己的cms:你将会遇到一种情况：将分层数据（层级结构）存储在数据库中。除非你使用一个类似xml的数据库,通用的关系型数据库是很难做到这一点。关系型数据库中的表不分层;他们只是一个简单列表。你必须找到一个方法来把层次结构数据转换为一个简单文件数据。

存储树是一种常见的问题,可以有多个解决方案来实现。有两种主要方法:邻接表模型和修改后的树前序遍历的算法。

在本文中,我们将探讨这两种方法来存储层级结构数据。我将使用从一个虚构的在线食品商店虚拟的这棵树为例。这个食品商店通过类别、颜色以及种类来来组织它的食品。

这颗树如下：

这篇文章包含一些代码示例展示了如何保存和检索数据。原文是使用的PHP，在这我将使用java来演示它的代码展示。

[一] 邻接列表模型

我们最先尝试或者最优雅的方式我们称为“邻接表模式”或者我们称它为“递归方法”。

这是一种优雅的方法,因为你只需要一个简单的函数就可以遍历树。在我们的食品商店的例子中,邻接表的表可以这样表示：

如您所见,在邻接表的方法,你只保存每个节点的父节点。我们可以从表上清楚的看到,“Pear”是“Green”的一个孩子，同时“Green”又是'Fruit'的孩子。

根节点“Food”没有父节点。为简单起见,我使用了“标题”值来确定每个节点。当然,在一个真正的数据库,可以使用id来标示。

Give Me the Tree

既然我们已经在数据库中插入我们的树,是时候写一个显示功能。这个函数将不得不从根节点（没有父节点）开始，应该显示所有该节点的孩子。对于这些孩子节点来说,这个函数应该检索和显示这些孩子节点的所有子节点。然后在显示这些孩子节点的子节点，递归的进行。

public void DisplayTree(int parentId,int level){
		String sql = "select NodeId,NodeName,ParentId from Tree where parentid="+ parentId;
		conn = sqlManager.GetConn();
		try {
			statement = conn.createStatement();
			ResultSet rs = statement.executeQuery(sql);
			while(rs.next()){
				for(int i = 0;i < level*2;i++){
					System.out.print("-");
				}
				System.out.println(rs.getString("NodeName"));
				DisplayTree(rs.getInt("NodeId"),level+1);
			}
		} catch (SQLException e) {
			e.printStackTrace();
		}
	}

注：sqlManager类是数据库操作类。 

数据库存储的数据：

打印整个树

DisplayTree(0,0)

结果：

如果你只是想看到一个子树,你可以告诉函数这个开始节点的Id即可。

例如,显示“Fruit”子树,运行DisplayTree(2,0);

The Path to a Node

有时候我们需要知道某个节点所在的路径。举例来说，“Cherry”所在的路径为Food > Fruit > Red > Cherry。在这里，我们可以从Cherry开始查起，然后递归查询查询节点前的节点，直到某节点的父节点ID为0。

 

//获取某个节点所在路径
	public ArrayList<String> GetPath(int nodeId){
		String sql = "select ParentId,NodeName from Tree where NodeId = "+nodeId;
		ArrayList<String> path = new ArrayList<String>();
		try {
			conn = sqlManager.GetConn();
			statement = conn.createStatement();
			ResultSet rs = statement.executeQuery(sql);
			rs.next();
			int parentId = rs.getInt("ParentId");
			String nodeName = rs.getString("NodeName");
			if(parentId != 0){
				path.addAll(GetPath(parentId));
			}
			path.add(nodeName);
		} catch (SQLException e) {
			e.printStackTrace();
		}
		return path;
	}

ArrayList<String> path = main.GetPath(9);
		int index = 0;
		for (String node : path) {
			if(index != 0){
				System.out.print("->");
			}
			System.out.print(node);
			index++;
		}

id= 9 对应为Banana 路径为：Food->Fruit->Yellow->Banana

优缺点

我们可以看到，用邻接表模型确实是个不错的方法。它简单易懂，而且实现的代码写起来也很容易。那么，缺点是什么呢？那就是，在大多数语言中，邻接表模型执行起来效率低下和缓慢。这主要是由于递归引起的，我们查询树中的每个节点的时候都需要进行依次数据库查询。因为每个查询需要一些时间,这使得函数非常缓慢的在处理大树时。

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

[二] 树前序遍历的算法变形

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

现在我们把树“横”着放。如下图所示，我们首先从根节点（“Food”）开始，先在它左侧标记“1”，然后我们到“Fruit”，左侧标记“2”，接着按照前序遍历的顺序遍历完树，依次在每个节点的左右侧标记数字。最后一个数字写在“Food”节点右边的。在这张图片里,你可以看到用数字标记的整个树和几个箭头指示编号顺序。

我们叫这些数字为Left和Right(例如“Food”的Left值是1,Right值是18)。正如你所看到的,这些数字表示每个节点之间的关系。

比如，“Red”节点左边的数为3、右边的数为6，它是Food（1-18）的后代。同样的，我们可以注意到，左数大于2、右数小于11的节点都是“Fruit”的子孙。现在，所有的节点将以左数-右数的方式存储，这种通过遍历一个树、然后给每一个节点标注左数、右数的方式称为修改过的前序遍历算法。

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

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

Retrieve the Tree

如果你想使用一个带有左值和右值的表显示树与,你首先要确定你想要检索的节点。例如,如果您希望检索“Fruit”子树,你将不得不选择左值在2至11之间的那些节点。 sql语句：

SELECT * FROM FoodTree WHERE Lft BETWEEN 2 AND 11;

注：FoodTree是存储数据的表

返回：

整个树只需要一次查询。

显示这棵树就像我们做递归函数,我们将不得不ORDER BY子句添加到查询语句中。如果你从你的表添加和删除行,你的表可能不会以正确的顺序存储。我们应该按左值进行排序。

SELECT * FROM FoodTree WHERE Lft BETWEEN 2 AND 11 ORDER BY Lft ASC;

现在唯一的问题是缩进问题。

显示树结构,孩子应该缩进略高于他们的父母。

正如我们面对树的问题常常会想到的方案——栈。这里，我们可以维护一个只保存右数的栈。我们知道该节点所有的孩子的Rgt值小于父的Rgt值,所以通过比较当前节点的Rgt值和堆栈中最后一个节点的Rgt值。当当前节点的Rgt值大于栈顶元素的值（说明栈顶元素的子树都以遍历完毕），这个时候弹出栈顶值。再循环检查栈顶值，直到栈顶值小于当前查询节点的Rgt值。这个时候只要检查栈中元素，有多少个元素说明当前查询节点有多少个祖先节点（设为n）。只需要打印n个空格即可。代码如下：