php - 在数据库中存储树数据结构

Question

在上面的树中，每个节点都有一个名称和值。每个节点最多可以有 6 个 child 。如何将其存储在 MySQL 数据库中以高效地执行以下操作？

操作

1) grandValue(node) - 应该给出(所有后代值的总和，包括自身)

例如，

• grandValue(C) = 300
• grandValue(I) = 950
• grandValue(A) = 3100

2) children(node) - 应该给出所有 child 的列表(仅限直系后代)

例如，

• children(C) = null
• children(I) = L,M,N
• children(A) = B,C,D,E

3) family(node) - 应该给出后代列表

• family(C) = null
• family(I) = L,M,N
• family(A) = B,C,D,E,F,G,H,I,J,K,L,M,N

4) parent(node) - 应该给出节点的父节点

• parent(C) = A
• parent(I) = D
• parent(A) = null

5) insert(parent, node, value) - 应该将节点作为父节点的子节点插入

• insert(C, X, 500) 插入一个值为 500 的节点名称 X 作为 C 的子节点

我正在考虑使用递归方法来进行这些操作，就像我们对二叉树所做的那样。但我不确定这是否是最佳方式。这棵树可能有 10 到 3000 万个节点，并且可能是倾斜的。所以将数据转储到内存堆栈是我关注的领域。

请帮忙。

NOTE: I am using PHP, MySQL, Laravel, on VPS Machine.

UPDATE: Tree will grow in size. New nodes will be added as a child of leaf nodes or nodes which has less than 6 nodes and not in-between 2 nodes.

Answer 1

您可以使用嵌套集将数据存储在表中。
http://en.wikipedia.org/wiki/Nested_set_model#Example
如果您打算不断添加新项目，我担心您的数百万节点可能会过不去。或许可以通过使用有理数而不是整数作为左右值来减轻这种担忧。添加深度列以加快您要求后代的愿望。我写了一些 SQL 来创建您要求的表和存储过程。我是在 SQL Server 中做的，虽然语法可能略有不同，但都是执行的标准 SQL 语句。此外，我只是手动确定每个节点的上限和下限。显然，您必须编写代码才能将这些节点插入(并维护)到您的数据库中。

CREATE TABLE Tree(
    Node nvarchar(10) NOT NULL,
    Value int NOT NULL,
    L int NOT NULL,
    R int NOT NULL,
    Depth int NOT NULL,
);

INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('A', 100,  1, 28, 0);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('B', 100,  2,  3, 1);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('C', 300,  4,  5, 1);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('D', 150,  6, 25, 1);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('E', 200, 26, 27, 1);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('F', 400,  7,  8, 2);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('G', 250,  9, 10, 2);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('H', 500, 11, 12, 2);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('I', 350, 13, 21, 2);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('J', 100, 21, 22, 2);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('K',  50, 23, 24, 2);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('L', 100, 14, 15, 3);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('M', 300, 16, 17, 3);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('N', 200, 18, 19, 3);

CREATE PROCEDURE grandValue
    @Node NVARCHAR(10)
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @lbound INT;
    DECLARE @ubound INT;
    SELECT @lbound = L, @ubound = R FROM Tree WHERE Node = @Node
    SELECT SUM(Value) AS Total FROM TREE WHERE L >= @lbound AND R <= @ubound
    RETURN
END;

EXECUTE grandValue 'C';
EXECUTE grandValue 'I';
EXECUTE grandValue 'A';

CREATE PROCEDURE children
    @Node NVARCHAR(10)
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @lbound INT;
    DECLARE @ubound INT;
    DECLARE @depth INT;
    SELECT @lbound = L, @ubound = R, @depth=Depth FROM Tree WHERE Node = @Node
    SELECT Node FROM TREE WHERE L > @lbound AND R < @ubound AND Depth = (@depth + 1)
    RETURN
END;

EXECUTE children 'C';
EXECUTE children 'I';
EXECUTE children 'A';

CREATE PROCEDURE family
    @Node NVARCHAR(10)
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @lbound INT;
    DECLARE @ubound INT;
    SELECT @lbound = L, @ubound = R FROM Tree WHERE Node = @Node
    SELECT Node FROM TREE WHERE L > @lbound AND R < @ubound
    RETURN
END;

EXECUTE family 'C';
EXECUTE family 'I';
EXECUTE family 'A';

CREATE PROCEDURE parent
    @Node NVARCHAR(10)
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @lbound INT;
    DECLARE @ubound INT;
    DECLARE @depth INT;
    SELECT @lbound = L, @ubound = R, @depth = Depth FROM Tree WHERE Node = @Node
    SELECT Node FROM TREE WHERE L < @lbound AND R > @ubound AND Depth = (@depth - 1)
    RETURN
END;

EXECUTE parent 'C';
EXECUTE parent 'I';
EXECUTE parent 'A';

CREATE PROCEDURE ancestor
    @Node NVARCHAR(10)
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @lbound INT;
    DECLARE @ubound INT;
    SELECT @lbound = L, @ubound = R FROM Tree WHERE Node = @Node
    SELECT Node FROM TREE WHERE L < @lbound AND R > @ubound
    RETURN
END;

EXECUTE ancestor 'C';
EXECUTE ancestor 'I';
EXECUTE ancestor 'A';

为了首先在表中创建嵌套集，您可以运行一些代码来生成插入或从第一个节点开始，然后依次添加每个额外的节点——尽管因为每个添加都可能修改表中的许多节点设置在构建此数据库时可能会出现大量的数据库颠簸。

这是一个将一个节点添加为另一个节点的子节点的存储过程:

CREATE PROCEDURE insertNode
    @ParentNode NVARCHAR(10), @NewNodeName NVARCHAR(10), @NewNodeValue INT
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @ubound INT;
    DECLARE @depth INT;
    SELECT @ubound = R, @depth = Depth FROM Tree WHERE Node = @ParentNode
    UPDATE Tree SET L = L + 2 WHERE L >= @ubound
    UPDATE Tree SET R = R + 2 WHERE R >= @ubound
    INSERT INTO Tree (Node, Value, L, R, Depth) VALUES (@NewNodeName, @NewNodeValue,  @ubound, @ubound + 1, @depth + 1);
    RETURN
END;

我从 http://www.evanpetersen.com/item/nested-sets.html 得到这个谁还展示了一个用于创建初始 L 和 R 值的不错的图形步行算法。您必须对此进行增强以跟踪深度，但这很容易。