在 SQL 中创建树模板

Question

我正在使用一个数据库，该数据库用于以组件树的形式存储有关实体的信息。例如，它可能有一个带儿童空调和发动机的凯美瑞对象。发动机可能有活塞作为子项，空调可能有通风口作为子项。

这个想法是，用户可以自定义创建类似这样的东西作为 'template'，然后根据需要将其用于实例化凯美瑞 'tree'。因此，用户可能首先创建模板，然后使用它将 10 棵这样的 camry 树添加到车间，通过选择 'add new car'、选择 camry，然后选择一个名称来存储每棵树的唯一数据。

如何将这样的构造存储在数据库中，有没有简单的方法来实例化这样的树？

Answer 1

我之前已经完成了前半部分，所以我们将从这里开始（方便，不是吗？）。在不太了解您的需求的情况下，我推荐以下内容作为基础（您可以根据需要调整列宽）：

CREATE TABLE tree (
    id INT UNSIGNED NOT NULL AUTO_INCREMENT,
    parent_id INT UNSIGNED NOT NULL DEFAULT 0,
    type VARCHAR(20) NOT NULL,
    name VARCHAR(32) NOT NULL,
    PRIMARY KEY (id),
    UNIQUE KEY (parent_id, type, name),
    KEY (parent_id)
);

我为什么要这样做？好吧，让我们遍历每个字段。 id 是一个全局唯一值，我们可以用它来标识这个元素以及直接依赖于它的所有元素。 parent_id 让我们通过树向上返回，直到我们到达 parent_id == 0，这是树的顶部。 type 将是您的 "car" 或 "vent" 描述。 name 会让你有资格 type，所以像 "Camry" 和 "Driver Left"（对于 "vent" 显然）。

数据将存储为如下值：

INSERT INTO tree (parent_id, type, name) VALUES
    (0, 'car', 'Camry'),
    (1, 'hvac', 'HVAC'),
    (2, 'vent', 'Driver Front Footwell'),
    (2, 'vent', 'Passenger Front Footwell'),
    (2, 'vent', 'Driver Rear Footwell'),
    (2, 'vent', 'Passenger Rear Footwell'),
    (1, 'glass', 'Glass'),
    (7, 'window', 'Windshield'),
    (7, 'window', 'Rear Window'),
    (7, 'window', 'Driver Front Window'),
    (7, 'window', 'Passenger Front Window'),
    (7, 'window', 'Driver Rear Window'),
    (7, 'window', 'Passenger Rear Window'),
    (1, 'mirrors', 'Mirrors'),
    (14, 'mirror', 'Rearview Mirror'),
    (14, 'mirror', 'Driver Mirror'),
    (14, 'mirror', 'Passenger Mirror');

我可以继续，但我想你明白了。只是为了确定......所有这些值都会导致一棵看起来像这样的树：

(1, 0, 'car', 'Camry')
  |  (2, 1, 'hvac', 'HVAC')
  |    +- (3, 2, 'vent', 'Driver Front Footwell')
  |    +- (4, 2, 'vent', 'Passenger Front Footwell')
  |    +- (5, 2, 'vent', 'Driver Rear Footwell')
  |    +- (6, 2, 'vent', 'Passenger Rear Footwell')
  +- (7, 1, 'glass', 'Glass')
  |    +- (8, 7, 'window', 'Windshield')
  |    +- (9, 7, 'window', 'Rear Window')
  |    +- (10, 7, 'window', 'Driver Front Window')
  |    +- (11, 7, 'window', 'Passenger Front Window')
  |    +- (12, 7, 'window', 'Driver Rear Window')
  |    +- (13, 7, 'window', 'Passenger Rear Window')
  +- (14, 1, 'mirrors', 'Mirrors')
       +- (15, 14, 'mirror', 'Rearview Mirror')
       +- (16, 14, 'mirror', 'Driver Mirror')
       +- (17, 14, 'mirror', 'Passenger Mirror')

现在，困难的部分：复制树。由于 parent_id 引用，我们不能做类似 INSERT INTO ... SELECT 的事情；我们不得不使用递归函数。我知道，我们正在进入 The Dirty place。我将对此进行伪编码，因为您没有注意到您使用的是哪种语言。

FUNCTION copyTreeByID (INTEGER id, INTEGER max_depth = 10, INTEGER parent_id = 0)
    row = MYSQL_QUERY_ROW ("SELECT * FROM tree WHERE id=?", id)
    IF NOT row
    THEN
        RETURN NULL
    END IF

    IF ! MYSQL_QUERY ("INSERT INTO trees (parent_id, type, name) VALUES (?, ?, ?)", parent_id, row["type"], row["name"])
    THEN
        RETURN NULL
    END IF
    parent_id = MYSQL_LAST_INSERT_ID ()

    IF max_depth LESSTHAN 0
    THEN
        RETURN
    END IF

    rows = MYSQL_QUERY_ROWS ("SELECT id FROM trees WHERE parent_id=?", id)
    FOR rows AS row
        copyTreeByID (row["id"], max_depth - 1, parent_id)
    END FOR

    RETURN parent_id
END FUNCTION

FUNCTION copyTreeByTypeName (STRING type, STRING name)
    row = MYSQL_QUERY_ROW ("SELECT id FROM tree WHERE parent_id=0 AND type=? AND name=?", type, name)
    IF NOT ARRAY_LENGTH (row)
    THEN
        RETURN
    END IF
    RETURN copyTreeByID (row["id"])
END FUNCTION

copyTreeByTypeName 查找匹配的 type 和 name 的树 ID，并将其传递给 copyTreeByID。这主要是一个实用功能，可帮助您通过 type/name.

复制内容

copyTreeByID才是真正的野兽。害怕它，因为它是递归的和邪恶的。为什么是递归的？因为你的树是不可预测的，可以是任何深度。但没关系，我们有一个变量来跟踪深度并限制它 (max_depth)。那么让我们来看看吧。

首先获取元素的所有数据。如果我们没有得到任何数据，就 return。用元素的 type 和 name 以及传递的 parent_id 重新插入数据。如果查询失败，return。将 parent_id 设置为最后一个插入 ID，以便我们稍后传递它。检查 max_depth 是否小于零，这表明我们已经达到最大深度；如果我们有 return。从树中获取父元素为 id 的所有元素。然后对于这些元素中的每一个递归到 copyTreeByID 传递元素的 id、max_depth 减 1 和新的 parent_id。最后 return parent_id 这样你就可以访问元素的新副本了。

有道理吗？（我回头读了一遍，它是有道理的，但这并不意味着什么）。

在 SQL 中创建树模板

Creating a tree template in SQL

sql

postgresql

tree