层次模型是一种用树形结构描述实体及其之间关系的数据模型。在这种结构中，每一个记录类型都是用节点表示，记录类型之间的联系则用结点之间的有向线段来表示。每一个双亲结点可以有多个子节点但是每一个子节点只能有一个双亲结点。这种结构决定了采用层次模型作为数系组织方式的层次数据库系统只能处理一对多的实体联系。

层次模型示例：

 

层次模型与SQL存储

典型存储、查询层次数据场景

• 分类/子分类
• 物料清单
• 主题讨论（如网易盖楼）

解决方案

• 邻接表（adjacency list）
• 路径枚举(path enumeration)
• 嵌套集(nested sets)
• 闭包表(closure table)

---

邻接表(adjacency list)：

• 最原始的方案，几乎每个人都会
• 每个条目知道它的父条目

 

添加新节点：

INSERT INTO comments(parent_id,author,comment) VALUES(5,’Fran’,’I agree!’);

移动节点/子树：

UPDATE comments SET parent_id=3 WHERE comment_id=6;

查询子节点/父节点：

• 子节点
  • SELECT * FROM comments c1 LEFT JOIN comments c2 ON (c2.comment_id=c1.commnet_id);
• 父节点
  • SELECT * FROM comments c1 JOIN comments c2 ON (c1.parent_id=c2.commnet_id);

无法处理过深的树：

SELECT * FROM comments c1 LEFT JOIN comments c2 ON (c2.parent_id=c1.commnet_id)

LEFT JOIN comments c3 ON (c3.parent_id=c2.commnet_id)

LEFT JOIN comments c4 ON (c4.parent_id=c3.commnet_id)

LEFT JOIN comments c5 ON (c5.parent_id=c4.commnet_id)

LEFT JOIN comments c6 ON (c6.parent_id=c5.commnet_id)

……

---

路径枚举(path enumeration)

• 每个节点中都存储到祖先节点的链路

查询祖先节点和子树：

• comment#7的祖先节点
  • SELECT * FROM comments WHERE path LIKE ‘1/4/6/’;
• comment#4的子树
  • SELECT * FROM comments WHERE path LIKE ‘1/4/%’;

添加子节点：

• 添加子节点到comment#7
  • INSERT INTO comments (author, comment) VALUES (‘Ollie’, ‘Good job!’);
  • SELECT path FROM comments WHERE comment_id = 7;
  • UPDATE comments SET path =$new_path  WHERE comment_id = LAST_INSERT_ID();(其中$new_path的值为 $parent_path+ LAST_INSERT_ID() + ‘/’ )

---

嵌套集(nested sets)

• 每条评论使用两个数字编码它的子节点
  • 评论的左数字比该评论所有子评论数字都小（以comment#4为例，左数字6小于子评论comments#5，comment#6，comment#7中的所有数字）
  • 评论的右数字比该评论所有子评论数字都大（以comment#4为例，右数字13大于子评论comments#5，comment#6，comment#7中的所有数字）
  • 评论的左右数字居于该评论所有祖先节点数字之间（以comment#4为例，左数字6和右数字13居于其祖先节点comments#1的左数字1和右数字14之间，即1 < (6 < 13) < 14）

 

 

查询祖先节点和子树：

• 查询comment#7的祖先节点：
  • SELECT * FROM comments child JOIN comments ancestor ON (child.nsleft BETWEEN ancestor.nsleft AND ancestor.nsright) WHERE child.comment_id = 7;(即查询子节点数字10在父节点左数字和父节点右数字之间的记录，明显是comment#1，comment#4和comment#6)
• 查询comment#4的后继节点
  • SELECT * FROM comments parent JOIN comments descendant ON (descendant.nsleft BETWEEN parent.nsleft AND parent.nsright) WHERE parent.comment_id = 4;(即查询子节点左数字在6和13之间的记录，明显是comment#5，comment#6和comment#7)

添加子节点：

• 添加子节点到comment#5:
  • UPDATE comments SET nsleft = (CASE WHEN nsleft >= 8 THEN nsleft+2 ELSE nsleft END), nsright = nsright+2 WHERE nsright >= 7;
  • INSERT INTO comments (nsleft, nsright, author, comment) VALUES (8, 9, ‘Fran’, ‘I agree!’);
  • 重新计算该节点右边节点的所有左数字值.
  • 重新计算该节点右边、上边节点的右数字值.

查询父节点：

• SELECT parent.* FROM comments AS c JOIN comments AS parent ON (c.nsleft BETWEEN parent.nsleft AND parent.nsright) LEFT OUTER JOIN comments AS in_between ON (c.nsleft BETWEEN in_between.nsleft AND in_between.nsright AND in_between.nsleft BETWEEN parent.nsleft AND parent.nsright) WHERE c.comment_id = 6 AND in_between.comment_id IS NULL;

查询子节点与上面相似

---

闭包表(closure table)

• 多对多的表
• 存储每个节点到其后继节点的路径
• 节点连接到自身

创建表：

CREATE TABLE TreePaths (

ancestor INT NOT NULL,

descendant INT NOT NULL,

PRIMARY KEY (ancestor, descendant),

FOREIGN KEY(ancestor) REFERENCES comments(comment_id),

FOREIGN KEY(descendant) REFERENCES comments(comment_id)

);

查询comment4的后继节点：

• SELECT c.* FROM comments c JOIN TreePaths t ON (c.comment_id = t.descendant) WHERE t.ancestor = 4;

查询comment#6的祖先节点：

• SELECT c.* FROM comments c JOIN TreePaths t ON (c.comment_id = t.ancestor) WHERE t.descendant = 6;

添加新节点到comment#5:

• INSERT INTO comments VALUES (8, ‘Fran’, ‘I agree!’);
• INSERT INTO TreePaths (ancestor, descendant) SELECT ancestor, 8 FROM TreePaths WHERE descendant = 5 UNION ALL SELECT 8, 8;

删除comment#7:

• DELETE FROM TreePaths WHERE descendant = 7;

删除comment#4的子树：

• DELETE FROM TreePaths WHERE descendant IN (SELECT descendant FROM TreePaths WHERE ancestor = 4);

---

选择正确的设计很重要