[数据库]数据库存储层级结构数据
无论你想建立自己的论坛,在你的网站上从一个邮件列表发布消息,或编写自己的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 ArrayListGetPath(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; } ArrayListid= 9 对应为Banana 路径为:Food->Fruit->Yellow->Bananapath = main.GetPath(9); int index = 0; for (String node : path) { if(index != 0){ System.out.print("->"); } System.out.print(node); index++; } 优缺点
我们可以看到,用邻接表模型确实是个不错的方法。它简单易懂,而且实现的代码写起来也很容易。那么,缺点是什么呢?那就是,在大多数语言中,邻接表模型执行起来效率低下和缓慢。这主要是由于递归引起的,我们查询树中的每个节点的时候都需要进行依次数据库查询。因为每个查询需要一些时间,这使得函数非常缓慢的在处理大树时。第二个原因是在你可能使用的编程语言这个方法不是那么快,。对于一门程序语言来说,除了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个空格即可。代码如下:
上一篇: Photoshop制作带有光斑的梦幻蓝紫色光束心形
下一篇: php递归删除目录与文件的方法
推荐阅读