如何在关系型数据库中存储含邻接关系与子节点的Linked Tree？

Hey there! Let's work through how to model your LinkedTree structure in MySQL to handle both adjacency and parent-child relationships, while supporting efficient loading from any position—even with millions of nodes.

Table Structure Design #

First, let's create a table that captures all the relationships your nodes need: adjacency (previous/next in the linked list) and parent-child (hierarchical tree structure). We'll also optimize for quick lookups with indexes.

Table: linked_tree_nodes #

Indexes for Performance #

Add these indexes to speed up common queries:

• INDEX idx_prev (prev_node_id): Fast lookups for previous nodes.
• INDEX idx_next (next_node_id): Fast lookups for next nodes.
• INDEX idx_parent (parent_node_id): Fast retrieval of all child nodes for a parent.
• INDEX idx_branch (branch_id): Quick loading of entire linked list branches.

Data Read/Write Strategies #

Now let's map your Java LinkedTree and Node logic to database operations.

1. Saving Nodes to MySQL #

When persisting your tree, traverse each linked list and recursively handle child trees:

• For each Node, serialize its item to a JSON string and insert it into the table.
• Set prev_node_id and next_node_id using the node_id of the adjacent nodes (from the database, not just in-memory references).
• Set parent_node_id if the node belongs to a child tree of another node.
• Use batch inserts for large node sets to minimize database round-trips.

Example save method (using Spring JdbcTemplate as an example):

private final ObjectMapper objectMapper = new ObjectMapper();
private final JdbcTemplate jdbcTemplate;

public Long saveNode(Node<E> node, Long parentNodeId, String branchId) {
    // Serialize node data to JSON
    String dataJson;
    try {
        dataJson = objectMapper.writeValueAsString(node.item());
    } catch (JsonProcessingException e) {
        throw new RuntimeException("Failed to serialize node data", e);
    }

    // Insert node and get generated ID
    String insertSql = """
        INSERT INTO linked_tree_nodes(data, prev_node_id, next_node_id, parent_node_id, branch_id)
        VALUES (?, ?, ?, ?, ?)
    """;
    Long nodeId = jdbcTemplate.queryForObject(
        insertSql,
        new Object[]{
            dataJson,
            node.hasPrevious() ? getNodeId(node.previous()) : null,
            node.hasNext() ? getNodeId(node.next()) : null,
            parentNodeId,
            branchId
        },
        Long.class
    );

    // Attach the database ID to your in-memory Node (add a `nodeId` field to your Node class)
    node.setNodeId(nodeId);

    // Recursively save child trees (adjust based on your LinkedTree structure)
    if (nodeHasChildTree(node)) {
        saveLinkedTree(node.getChildTree(), nodeId, branchId + "_child");
    }

    return nodeId;
}

public void saveLinkedTree(LinkedTree<E> tree, Long parentNodeId, String branchId) {
    Node<E> current = tree.first;
    while (current != null) {
        saveNode(current, parentNodeId, branchId);
        current = current.next();
    }
}

// Helper method to get the database ID from an in-memory Node
private Long getNodeId(Node<E> node) {
    // Assume your Node class has a `getNodeId()` method after adding the field
    return node.getNodeId();
}

2. Loading Nodes from Any Position #

You can load nodes individually, their adjacent nodes, entire branches, or full subtrees—here's how:

Load a Single Node + Adjacent Nodes

To load a node and its immediate neighbors (great for incremental loading):

SELECT * FROM linked_tree_nodes 
WHERE node_id = ?
UNION ALL
SELECT * FROM linked_tree_nodes 
WHERE node_id = (SELECT prev_node_id FROM linked_tree_nodes WHERE node_id = ?)
UNION ALL
SELECT * FROM linked_tree_nodes 
WHERE node_id = (SELECT next_node_id FROM linked_tree_nodes WHERE node_id = ?);

Map the results back to your Node class, setting prev and next references using the returned node_id values.

Load an Entire Linked List Branch

If you have a branch_id, load all nodes in the branch and reconstruct the linked list:

SELECT * FROM linked_tree_nodes 
WHERE branch_id = ?
ORDER BY CASE WHEN prev_node_id IS NULL THEN 0 ELSE 1 END, node_id;

This orders the nodes starting with the first node in the list (where prev_node_id is NULL), then follows the sequence.

Load a Node and Its Subtree

To load a node plus all its child nodes (and their linked lists):

SELECT * FROM linked_tree_nodes 
WHERE parent_node_id = ?
ORDER BY CASE WHEN prev_node_id IS NULL THEN 0 ELSE 1 END, node_id;

Reconstruct the child LinkedTree from the results, just like the main branch.

Optimization Tips for Large Datasets #

• Batch Operations: Always use batch inserts/queries when dealing with thousands of nodes—this drastically reduces database overhead.
• Lazy Loading: Only load adjacent nodes or child trees when needed, instead of loading the entire tree at once.
• Table Partitioning: If you have tens of millions of nodes, partition the table by branch_id or parent_node_id to speed up queries.
• Data Compression: If your data field is large, use MySQL's COMPRESS() function to store compressed JSON, reducing storage and I/O costs.

内容的提问来源于stack exchange，提问作者Ste7