Хранить древовидную структуру данных в базе данных

Вы можете хранить данные в таблице, используя вложенные наборы.
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. Вы должны улучшить это, чтобы отслеживать глубину, но это будет легко.