博客

DBMS中的无级差

  • Post category:database

DBMS中的无级差

什么是无级差

无级差（Nested Sets Model）是一种管理层次结构（Hierarchy）数据的方法，常被用于实现分类目录（例如商品分类）、组织机构架构等具有层次结构的数据的管理。无级差是一种高效而稳定的数据管理方式，能够快速地查询、插入、更新等操作。

在无级差模型中，每个节点都以一个左右值对表示，左值称为L-Value，右值称为R-Value。这些值确定了每个节点在层次结构中的位置和范围。左值和右值是用来表明子结构的，在一个嵌套集中，每个节点都在一个父节点包裹的左值和右值之间。

无级差的优势

相比于传统的关系型数据库设计，无级差具有以下优势：

  1. 高效查询：在无级差中，用一组左右值来代表一个节点，这样可以避免使用递归查询，从而提高查询效率。

  2. 简单、明了的层次管理：无级差的表现形式是一个二维表，易于理解和操作。

  3. 层次扩展方便：当需要添加一个新节点时，只需要通过修改已有的L-Value和R-Value，而不需要重新为整棵树分配ID。

无级差的实现

下面以一个简单的分类目录为例，说明无级差的实现过程。

假设我们需要实现一个电商网站的商品分类系统，其层次结构如下图所示：

        ┌─食品
        ├─家电
        ├─书籍
顶级分类┼─化妆品
        ├─电子产品
        └─户外产品

为了更好地理解无级差的实现过程，我们可以将上述分类结构转换为一个二维表，每行表示一个节点，每个节点都有一个左值和右值。如下所示：

+---------------+---------------+---------+
| category_name | left_val      | right_val|
+---------------+---------------+---------+
+---------------+---------------+---------+
| 顶级分类      | 1             | 10      |
| 食品          | 2             | 5       |
| 家电          | 6             | 7       |
| 书籍          | 8             | 9       |
| 化妆品        | 11            | 12      |
| 电子产品      | 13            | 14      |
| 户外产品      | 15            | 16      |
+---------------+---------------+---------+

如上所示，我们将每个节点表示成了一行，根节点代表整棵树，因此L-Value为1，R-Value为10。每个节点的左值和右值范围定义了节点的位置。比如，当查找节点”书籍”时，需要查询left_val为8且right_val为9的记录。

无级差的操作

无级差的基本操作包括：查询、插入、删除、移动节点等。

查询

由于每个节点都对应一个左值和右值，因此查询一个节点只需要查询其左右值范围内的所有节点即可。例如，查询分类结构下所有的叶子节点，可以使用如下SQL语句：

SELECT category_name FROM category WHERE right_val - left_val = 1;

插入

在插入一个新节点时，需要先确定该节点在树中的位置。以插入节点”手机”到”电子产品”下面为例：

  1. 首先确定新节点的左值和右值。由于”电子产品”的左值为13，右值为14，那么在这个范围内插入节点。即新节点的左值为14，右值为15。

  2. 然后将位于14及其右侧所有节点的左值加上2，将位于14及其右侧所有节点的右值加上2。

  3. 最后新增节点，将左值为14、右值为15以及对应的分类名称插入到数据库中。

具体实现如下：

UPDATE category SET left_val = left_val + 2 WHERE left_val > 13;
UPDATE category SET right_val = right_val + 2 WHERE right_val >= 14;
INSERT INTO category VALUES('手机', 14, 15);

删除

当删除一个节点时，需要将位于节点左值和右值范围内的所有节点删除。以删除节点”电子产品”为例：

  1. 首先确定”电子产品”节点的左值和右值。由于”电子产品”节点的左值为13，右值为14，那么在这个范围内的所有节点都需要被删除。

  2. 删除节点：删除左值和右值在13到14之间的所有节点。

  3. 更新节点：将左值大于14的所有节点减去2，将右值大于14的所有节点减去2。

具体实现如下：

DELETE FROM category WHERE left_val >= 13 AND right_val <= 14;
UPDATE category SET left_val = left_val - 2 WHERE left_val > 14;
UPDATE category SET right_val = right_val - 2 WHERE right_val > 14;

移动节点

当移动一个节点时，需要将节点及其子节点移动到新的父节点下面。以将节点”家电”移动到节点”化妆品”下面为例：

  1. 首先确定节点”家电”的左值和右值。由于”家电”的左值为6，右值为7，那么在这个范围内的所有节点都需要被移动到”化妆品”下。

  2. 将节点的左值减去6，将右值减去5，获得节点的宽度。

  3. 找出目标父节点的左值和右值，并将左右值都减去1，得到目标范围。

  4. 判断目标范围是否与原始节点范围重叠。如果是，则需要将目标范围右边的节点偏移节点宽度的大小。

  5. 更新节点信息。

具体实现如下：

--确定节点"家电"的左值和右值
SET @left_val = 6;
SET @right_val = 7;

--确定节点的宽度
SET @width = @right_val - @left_val + 1;

--确定目标父节点的左值和右值
SELECT @parent_left_val:=left_val,@parent_right_val:=right_val FROM category WHERE category_name = '化妆品';

--将目标父节点的左值和右值都减去1
UPDATE category SET left_val = left_val - 1, right_val = right_val - 1 WHERE left_val >= @parent_left_val;

--判断目标范围是否与原始节点范围重叠
IF @left_val < @parent_left_val THEN
    SET @offset := @parent_right_val - @right_val - 1;
ELSE
    SET @offset := @parent_left_val - @left_val;
END IF;

--更新节点信息
UPDATE category SET left_val = left_val + @offset, right_val = right_val + @offset WHERE left_val BETWEEN @left_val and @right_val;

总结

无级差可以在管理层次数据的过程中提高操作的效率，使得在具有层次结构的数据中进行各种CRUD操作，变得更加便利和高效。无级差的实现思想相对简单，但是需要较为熟练的MySQL编程技巧，比较适合中高级开发者进行研究和实现。

Tags: ,