数据库中的树结构应该怎样去设计

翻译自：Trees in SQL by Joe Celko

这个主题是我的旧主题，但是值得重复的再谈一次，我在新闻讨论组中看到过太多关于SQL树和层次结构的问题。SQL书籍中树结构的常见示例称为邻接列表明细，它如下所示：

CREATE TABLE Personnel (
	emp CHAR(10) NOT NULL PRIMARY KEY,
	boss CHAR(10) DEFAULT NULL REFERENCES Personnel (emp),
	salary DECIMAL (6,2) NOT NULL DEFAULT 100.00
);

2021-07-12-uZcAyE

另外一种表示树的方法是将他们显示为嵌套集，因为SQL是一种面向集合的语言，所以该模型比你在大多数教科书上看到的常见的邻接表更好。我们像这样定义一个简单的Personal表，暂时忽略左(lft)和右(rgt)列：

CREATE TABLE Personnel (
	emp CHAR(10) NOT NULL PRIMARY KEY,
	lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
	rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),
	CONSTRAINT order_okay CHECK (lft < rgt)
);

这个问题总是在教科书书中为员工提供一列，为他的老板提供一列。这个表(表2)没有lft和rgt列--被称为邻接表模型，以同名的图论技术命名；节点对彼此相邻。

2021-07-12-XrN01g

组织结构图类似于图1的有向图：

2021-07-12-9RHJ29

表1以多种方式进行了非规范化。我们在一张表中对人员和组织结构图进行建模。但是为了节省空间，假设名称是职位，并且我们有另一个表格来描述担任这个职位的人员。

邻接表模型的另外一个问题是，boss列和employee列是同一种类型（人员姓名），因此应该只显示在规范化表中的一列上。为了证明这不是规范化的，假设”Chuck“将他的名字改为”Charles“；你必须在两列和其他的地方更改他的名字。规范化表的定义特征是一次在一个地方有一个事实。

最后一个问题是邻接表模型没有对从属进行建模。权利在等级制度中向下流动，但如果我解雇Chuck，我就会断开他所有的下属和Albert的联系。有时(例如水管)确实如此，但在嵌套集中不会出现这种情况。

要将树显示为嵌套集，请将节点替换为椭圆，然后将下级椭圆相互嵌套。根将是最大的椭圆，将包含所有其他的节点。叶节点将是最里面的椭圆，里面没有任何其他东西，嵌套将显示层次关系。rgt列和lft列（不能在SQL中使用保留关键字LEFT和RIGHT）显示嵌套。

如果不理解这个模型，那么想象一条小虫子沿着树逆时针爬行。每次到达节点的左侧或右侧时，虫子都会对其进行编号，当虫子回到顶部时，它就会停止。

此模型是显示子节点的一种自然方式，因为最终装配是由其分解未单独节点的物理嵌套组成的。

此时，boss列既是多余的，又是非规范化的，因残可以将其删除。另外注意，树型结构可以保存在一张表中，有关节点的所有信息可以放在第二张表中，你可以在员工编号上加入两者以进行查询。

要将图形转换为嵌套集模型，请考虑沿着树爬行的小虫子。虫子从顶部(根部)开始，然后绕着树完整的走一圈，当涉及到一个节点时，它就会在它正在访问的一侧单元格中放置一个数字并增加计数器。每个节点将得到两个数字-一个用于右侧(rgt)，一个用于左侧(lft)。（计算机科学专业的学生会认为这是一种经过修改的预排序树的遍历算法），最后删除不需要的”Personnel.boss“列，它表示图的变。

这有一些可预测的结果，我们可以使他们来构建查询。根的形式总是(lft=1,rgt=2 * (SELECT COUNT(*) FROM TreeTable))，叶子节点总是有(lft+1=rgt)，between谓词定义了子树等等；以下是一些可用于构建其他查询的常见查询：

1. 找到一个员工的所有主管，无论树有多深。

    SELECT
    	P2.*
    FROM
    	Personnel AS P1,
    	Personnel AS P2
    WHERE
    	P1.lft BETWEEN P2.lft
    	AND P2.rgt
    	AND P1.emp = :myemployee;

2. 找到该员工及其所有下属（此查询与第一个查询具有很好的对称性）。

   SELECT
   	P2.*
   FROM
   	Personnel AS P1,
   	Personnel AS P2
   WHERE
   	P1.lft BETWEEN P2.lft
   	AND P2.rgt
   	AND P2.emp = :myemployee;

3. 将group by和其他的聚合函数添加到这些基本查询中，你就有了分层的报告。例如，每个员工控制的总工资。

   SELECT
   	P2.emp,
   	SUM(S1.salary)
   FROM
   	Personnel AS P1,
   	Personnel AS P2,
   	Salaries AS S1
   WHERE
   	P1.lft BETWEEN P2.lft
   	AND P2.rgt
   	AND P1.emp = S1.emp
   GROUP BY
   	P2.emp;

   在邻接表模型中，你必须使用游标来完成这个功能。

4. 找到每个节点的级别，以便你可以将树打印为缩进列表。

   SELECT
   	COUNT(P2.emp) AS indentation,
   	P1.emp
   FROM
   	Personnel AS P1,
   	Personnel AS P2
   WHERE
   	P1.lft BETWEEN P2.lft
   	AND P2.rgt
   GROUP BY
   	P1.emp
   ORDER BY
   	P1.lft;

5. 嵌套集模型具有邻接表模型没有的兄弟姐妹的隐含排序。插入一个新的节点作为最右边节点的兄弟节点。

   BEGIN
   DECLARE
   	right_most_sibling INTEGER;
   	SET right_most_sibling = (
   	SELECT
   		rgt
   	FROM
   		Personnel
   	WHERE
   		emp = :your_boss);
   	UPDATE
   		Personnel
   	SET
   		lft = CASE WHEN lft > right_most_sibling THEN
   			lft + 2
   		ELSE
   			lft
   		END,
   		rgt = CASE WHEN rgt >= right_most_sibling THEN
   			rgt + 2
   		ELSE
   			rgt
   		END
   	WHERE
   		rgt >= right_most_sibling;
   	INSERT INTO Personnel (emp, lft, rgt)
   		VALUES('New Guy', right_most_sibling, (right_most_sibling + 1))
   END;

6. 要将邻接表模型转换为嵌套集模型，请使用下推堆栈算法。假设我们有这些表：

   树持有邻接表模型。

   CREATE TABLE Tree
   (emp CHAR(10) NOT NULL,
   boss CHAR(10));
   
   INSERT INTO Tree
   SELECT emp, boss FROM Personnel;
   
   -- Stack starts empty, will holds the nested set model
   CREATE TABLE Stack
   (stack_top INTEGER NOT NULL,
   emp CHAR(10) NOT NULL,
   lft INTEGER,
   rgt INTEGER);
   
   BEGIN
   	ATOMIC
   DECLARE
   	counter INTEGER;
   DECLARE
   	max_counter INTEGER;
   DECLARE
   	current_top INTEGER;
   	SET counter = 2;
   	SET max_counter = 2 * (
   	SELECT
   		COUNT(*)
   		FROM
   			Tree);
   	SET current_top = 1;
   	INSERT INTO Stack
   	SELECT
   		1,
   		emp,
   		1,
   		NULL
   	FROM
   		Tree
   	WHERE
   		boss IS NULL;
   	DELETE FROM Tree
   	WHERE boss IS NULL;
   	WHILE counter <= (max_counter - 2)
   	LOOP
   		IF EXISTS (
   			SELECT
   				*
   			FROM
   				Stack AS S1,
   				Tree AS T1
   			WHERE
   				S1.emp = T1.boss
   				AND S1.stack_top = current_top) THEN
   BEGIN
   	-- push when top has subordinates, set lft value
   	INSERT INTO Stack
   	SELECT
   		(current_top + 1), MIN(T1.emp), counter, NULL
   	FROM
   		Stack AS S1,
   		Tree AS T1
   	WHERE
   		S1.emp = T1.boss
   		AND S1.stack_top = current_top;
   	DELETE FROM Tree
   	WHERE emp = (
   			SELECT
   				emp
   			FROM
   				Stack
   			WHERE
   				stack_top = current_top + 1);
   	SET counter = counter + 1;
   	SET current_top = current_top + 1;
   END
   ELSE
   	BEGIN
   		-- pop the stack and set rgt value
   		UPDATE
   			Stack
   		SET
   			rgt = counter,
   			stack_top = - stack_top -- pops the stack
   		WHERE
   			stack_top = current_top
   		SET
   			counter = counter + 1;
   	SET current_top = current_top - 1;
   END IF;
   END LOOP;
   END;
   

   尽管此过程有效，但是你可能希望使用一种包含数组的语言，而不是坚持使用SQL。