欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

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

程序员文章站 2022-06-01 18:34:17
...

无论你想建立自己的论坛,在你的网站上从一个邮件列表发布消息,或编写自己的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 
注:sqlManager类是数据库操作类。 

数据库存储的数据:

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

打印整个树

DisplayTree(0,0)

结果:

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

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

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

The Path to a Node

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

//获取某个节点所在路径
	public ArrayList GetPath(int nodeId){
		String sql = "select ParentId,NodeName from Tree where NodeId = "+nodeId;
		ArrayList path = new ArrayList();
		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 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个空格即可。代码如下: