第一章: 在RDB中的树结构数据

在本章中，我将写一个基本的知识来理解这个问题

一  模型的作用

RBD处理树模型的作用总结为两点：

1  在RDB表中保存树的数据

2  效率的查询节点的相关节点

1  在RDB表中保存树的数据

我们可以定义的标准，该模型是否具有存储层次数据的功能

可以由保存的所有节点再现原有的层次结构

如果不能通过保存的数据再现原有的树结构，就不能说这个模型实现了树。

2  效率的查询节点的相关节点

通常，我们将数据保存到数据库中进行搜索，数据中保存了分层数据，可能会查询任何节点的关系数据（如子树、父节点、子节点，祖先节点，子孙节点等）。这是一个树模型的重要作用。

如下[A], [B], [C]等表示节点。

                [A]               |           +---+---+           |       |          [B]     [C]           |       |         +-+-+   +-+-+         |   |   |   |        [D] [E] [F] [G]                     |                   +-+-+                   |   |                  [H] [I]

当我们查询[C]的子树时，通过跟踪向下延伸的分支来获取所有的节点。

           [C]           |         +-+-+         |   |        [F] [G]             |           +-+-+           |   |          [H] [I]

跟踪向下延伸的分支是很有规律性的，因此很多人认为如果将分层数据保存在数据库中，我们将很容易地查找到任何节点的相关节点。

树形结构数据会像一下的数据集合被频繁的搜索。

二  实例

通过实例，说明如何利用查询查找层次数据中的相关节点。

查找祖先节点使用网上的"breadcrumbs list"。

1  祖先节点查找的实例

        [Top Page]            |--[Products]            |     |--[Smart Phone Apps]            |     +--[Desktop Apps]            |--[News]            |     |--[2015/10]            |     |--[2015/09]            |     |--[2015/08]            |     +--[2015/07]            +--[About Us]                  |--[Corporate Philosophy]                  |--[Access]                  +--[Contact Us]

当我们查询[Corporate Philosophy]的节点，通过跟踪向上延伸在其顶端的节点如下。

Top Page > About Us > Corporate Philosophy

所有的过度的页面都会被认为是树结构，首页为根节点。当能够找到Corporate Philosophy的祖先节点就可以再现breadcrumbs list。

2  子孙节点查找的实例

论坛有回复注释的功能，以此为树，当将所有注释视为节点时，所存储的数据具有层次结构。查询论坛中的评论时，我们会使用寻找子树节点。

        [2015/03/31]            |--[Let‘s Party tonight! (John)]            |     |--[I will join! (Mike)]            |     |     +--[Thanks! (John)]            |     |--[Can not join tonight. (Anne)]            |     |     +--[When OK? (John)]            |     +--[OK, but 2 hours only. (Tom)]            |           |--[Me too. (Eucen)]            |           +--[I see! (John)]            +--[I losted my smart phone. (Bill)]                  |--[When? (Diana)]                  |     +--[Yesterday. (Bill)]                  +--[Did you check GPS? (Fred)]                        +--[Yet (Bill)]

如上，在2015年3月31日有两个线程，当只显示Let‘s Party tonight! (John)时就需要查询评论John的所有子树。在这种情况下，由于论坛海量数据节点的纯在效率问题，不能使用查找所有节点的方法。

三  关系模型的问题点

再次重申下RBD处理树模型的作用。

1  在RDB表中保存树的数据

2  效率的查询节点的相关节点

很难写出一个高效的查询原因有一下几点。

1  要想搜索，首先要保存每个节点的所有祖先节点

2  节点关系数据量相对深度呈指数倍增长

3  层次的深度不取决于数据的内容

4  在数据库中对层次数据赋予索引是困难的。因为树结构具有二维扩散，但指数是一维结构

5  等等

如果从指定节点找到一组子孙节点，可以通过跟踪分支方向来确定，这是一个简单的事。然而SQL是说明性编程（declarative programming），因此不能为每个节点确定关系，比如在单独的进程中使用命令式编程。

在声明式编程，我们如何能够表达在搜索查询子树和祖先节点的关系？

世界各地的数据库工程师都在挑战这个问题，RDB中的分层数据的问题点关键就在于“如何有效的查询节点相关的任何节点”。

四  列的追加

为了解决存储层次树数据，工程师们已经研发了四种模型来解决这个问题。

邻接表模型(adjacency list model)

路径枚举模型（path enumeration model）

嵌套集合模型（nested set model）

关闭表模型（closure table model）

无论在哪一种模型中，无非都是在RDB中添加一些列来保存分层数据。所添加的列按照其作用可以分为两类。

1  层次结构列

2  效率搜索列

1  层次结构列

需要保存层次数据在RDB表中。也在查询中被用作为一个检索条件的列。

2  效率搜索列

第一章: 在RDB中的树结构数据