You could store the data in a table using nested sets.
http://en.wikipedia.org/wiki/Nested_set_model#Example
I worry that your millions of nodes may make life difficult if you intend to constantly add new items. Perhaps that concern could be mitigated by using rational numbers instead of integers as the left and right values. Add a column for depth to speed up your desire to ask for descendants. I wrote some SQL to create the table and the stored procedures you asked for. I did it in SQL Server do the syntax might be slightly different but it's all standard SQL statements being executed. Also I just manually decided the upper and lower bounds for each Node. Obviously you'd have to deal with writing the code to get these nodes inserted (and maintained) in your database.
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';
For creating the nested sets in the table in the first place you can run some code to generate the inserts or start with the first node and then successively add each additional node - although since each add potentially modifies many of the nodes in the set there can be a lot of thrashing of the database as you build this.
Here's a stored procedure for adding a node as a child of another node:
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;
I got this from http://www.evanpetersen.com/item/nested-sets.html who also shows a nice graph walking algorithm for creating the initial L and R values. You'd have to enhance this to keep track of the depth as well but that's be easy.
