分层数据管理-邻接表模型

关于作者/译者
Mike Hillyer,本文的作者,MySQL Ab的技术作家,生活在加拿大的阿尔伯达省6 。
Yimin,本文的译者,就读于浙江理工大学计算机系。我的Blog:http://liyimin.net/blog

引言

  大多数用户都曾在数据库中处理过分层数据(hierarchical data),认为分层数据的管理不是关系数据库的目的。之所以这么认为,是因为关系数据库中的表没有层次关系,只是简单的平面化的列表;而分层数据具有父-子关系,显然关系数据库中的表不能自然地表现出其分层的特性。


  我们认为,分层数据是每项只有一个父项和零个或多个子项(根项除外,根项没有父项)的数据集合。分层数据存在于许多基于数据库的应用程序中,包括论坛和邮件列表中的分类、商业组织图表、内容管理系统的分类、产品分类。我们打算使用下面一个虚构的电子商店的产品分类:

分层数据管理-临界表模型


  这些分类层次与上面提到的一些例子中的分类层次是相类似的。在本文中我们将从传统的邻接表(adjacency list)模型出发,阐述2种在MySQL中处理分层数据的模型。


邻接表模型


  上述例子的分类数据将被存储在下面的数据表中(我给出了全部的数据表创建、数据插入的代码,你可以跟着做):

CREATE TABLE category(
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
parent INT DEFAULT NULL);
INSERT INTO category
VALUES(1,'ELECTRONICS',NULL),(2,'TELEVISIONS',1),(3,'TUBE',2),
(4,'LCD',2),(5,'PLASMA',2),(6,'PORTABLE ELECTRONICS',1),
(7,'MP3 PLAYERS',6),(8,'FLASH',7),
(9,'CD PLAYERS',6),(10,'2 WAY RADIOS',6);
SELECT * FROM category ORDER BY category_id;

分层数据管理-临界表模型


  在邻接表模型中,数据表中的每项包含了指向其父项的指示器。在此例中,最上层项的父项为空值(NULL)。邻接表模型的优势在于它很简单,可以很容易地看出FLASH是MP3 PLAYERS的子项,哪个是portable electronics的子项,哪个是electronics的子项。虽然,在客户端编码中邻接表模型处理起来也相当的简单,但是如果是纯SQL编码的话,该模型会有很多问题。

检索整树

  通常在处理分层数据时首要的任务是,以某种缩进形式来呈现一棵完整的树。为此,在纯SQL编码中通常的做法是使用自连接(self-join):

SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS';

分层数据管理-临界表模型
检索所有叶子节点

  我们可以用左连接(LEFT JOIN)来检索出树中所有叶子节点(没有孩子节点的节点):

SELECT t1.name FROM
category AS t1 LEFT JOIN category as t2
ON t1.category_id = t2.parent
WHERE t2.category_id IS NULL;

分层数据管理-临界表模型


检索单一路径

  通过自连接,我们也可以检索出单一路径:

SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS' AND t4.name = 'FLASH';

分层数据管理-临界表模型


  这种方法的主要局限是你需要为每层数据添加一个自连接,随着层次的增加,自连接变得越来越复杂,检索的性能自然而然的也就下降了。


邻接表模型的局限性

  用纯SQL编码实现邻接表模型有一定的难度。在我们检索某分类的路径之前,我们需要知道该分类所在的层次。另外,我们在删除节点的时候要特别小心,因为潜在的可能会孤立一棵子树(当删除portable electronics分类时,所有他的子分类都成了孤儿)。部分局限性可以通过使用客户端代码或者存储过程来解决,我们可以从树的底部开始向上迭代来获得一颗树或者单一路径,我们也可以在删除节点的时候使其子节点指向一个新的父节点,来防止孤立子树的产生。

加支付宝好友偷能量挖...


评论(0)网络
阅读(972)喜欢(1)SQL及数据库