如何基于MySQL表获取各父节点的全层级二叉树（Node.js+Express）

数据库表结构 #

CREATE TABLE IF NOT EXISTS Binary_Tree(
node_id VARCHAR(25) NOT NULL PRIMARY KEY,
parent_node_id VARCHAR(50) DEFAULT NULL CHECK (parent_node_id <> node_id),
node_flag CHAR(1) DEFAULT 'L' NOT NULL CHECK (node_flag IN ('L', 'R')),
username VARCHAR(25) DEFAULT NULL,
createdAt TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
updatedAt TIMESTAMP DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP
)

字段说明 #

• node_id：节点唯一ID（示例：937-G3876D）
• parent_node_id：父节点ID，根节点该字段为NULL（示例：-655R3876D）
• node_flag：节点在父节点下的位置，L代表左子节点，R代表右子节点
• username：关联的用户名（可选）
• createdAt：节点创建时间
• updatedAt：节点更新时间

实现思路与代码示例 #

根据数据量大小，提供两种可行方案：

方案1：内存构建树（推荐，性能优先） #

一次性拉取所有节点数据，在内存中通过映射关系组装二叉树，仅需1次数据库查询，适合数据量不大的场景。

1.1 基础配置（数据库连接+Express初始化）

const mysql = require('mysql');
const express = require('express');
const app = express();

// 数据库连接池（替换为你的数据库配置）
const pool = mysql.createPool({
  host: 'your_db_host',
  user: 'your_db_user',
  password: 'your_db_password',
  database: 'your_db_name'
});

// 封装Promise化的查询方法
const query = (sql, params) => {
  return new Promise((resolve, reject) => {
    pool.query(sql, params, (err, results) => {
      err ? reject(err) : resolve(results);
    });
  });
};

1.2 树结构构建函数

// 构建所有根节点的全层级树
function buildFullBinaryTree(nodes) {
  const nodeMap = new Map();
  const rootTrees = [];

  // 初始化节点映射表，添加left/right属性
  nodes.forEach(node => {
    nodeMap.set(node.node_id, { ...node, left: null, right: null });
  });

  // 挂载子节点到对应父节点
  nodes.forEach(node => {
    if (!node.parent_node_id) {
      rootTrees.push(nodeMap.get(node.node_id));
    } else {
      const parent = nodeMap.get(node.parent_node_id);
      if (parent) {
        parent[node.node_flag === 'L' ? 'left' : 'right'] = nodeMap.get(node.node_id);
      }
    }
  });

  return rootTrees;
}

// 根据指定parent_id获取其全层级子树
function getSubtreeByParentId(nodes, targetParentId) {
  const nodeMap = new Map();
  let subtreeRoot = null;

  nodes.forEach(node => {
    const formattedNode = { ...node, left: null, right: null };
    nodeMap.set(node.node_id, formattedNode);
    if (node.node_id === targetParentId) {
      subtreeRoot = formattedNode;
    }
  });

  if (!subtreeRoot) return null;

  nodes.forEach(node => {
    const parent = nodeMap.get(node.parent_node_id);
    if (parent) {
      parent[node.node_flag === 'L' ? 'left' : 'right'] = nodeMap.get(node.node_id);
    }
  });

  return subtreeRoot;
}

1.3 Express接口实现

// 获取所有根节点的全层级树
app.get('/api/binary-trees', async (req, res) => {
  try {
    const nodes = await query('SELECT node_id, parent_node_id, node_flag, username, createdAt, updatedAt FROM Binary_Tree');
    const trees = buildFullBinaryTree(nodes);
    res.json({ success: true, data: trees });
  } catch (err) {
    res.status(500).json({ success: false, error: err.message });
  }
});

// 获取指定父节点的全层级子树
app.get('/api/binary-tree/:parentId', async (req, res) => {
  try {
    const { parentId } = req.params;
    const nodes = await query('SELECT node_id, parent_node_id, node_flag, username, createdAt, updatedAt FROM Binary_Tree');
    const subtree = getSubtreeByParentId(nodes, parentId);
    
    if (!subtree) {
      return res.status(404).json({ success: false, message: '父节点不存在' });
    }
    res.json({ success: true, data: subtree });
  } catch (err) {
    res.status(500).json({ success: false, error: err.message });
  }
});

// 启动服务
const PORT = process.env.PORT || 3000;
app.listen(PORT, () => console.log(`服务运行在端口 ${PORT}`));

方案2：递归查询数据库（适合大数据量场景） #

通过递归方式逐层查询子节点，避免一次性拉取全量数据，但会产生多次数据库请求，适合数据量大但查询频率低的场景。

2.1 递归查询函数

async function getSubtreeRecursively(parentId) {
  // 查询当前父节点信息
  const parentRes = await query('SELECT node_id, parent_node_id, node_flag, username, createdAt, updatedAt FROM Binary_Tree WHERE node_id = ?', [parentId]);
  if (!parentRes.length) return null;

  const treeNode = { ...parentRes[0], left: null, right: null };

  // 递归查询左子节点
  const leftChild = await query('SELECT node_id FROM Binary_Tree WHERE parent_node_id = ? AND node_flag = ?', [parentId, 'L']);
  if (leftChild.length) {
    treeNode.left = await getSubtreeRecursively(leftChild[0].node_id);
  }

  // 递归查询右子节点
  const rightChild = await query('SELECT node_id FROM Binary_Tree WHERE parent_node_id = ? AND node_flag = ?', [parentId, 'R']);
  if (rightChild.length) {
    treeNode.right = await getSubtreeRecursively(rightChild[0].node_id);
  }

  return treeNode;
}

2.2 对应Express接口

app.get('/api/binary-tree-recursive/:parentId', async (req, res) => {
  try {
    const { parentId } = req.params;
    const subtree = await getSubtreeRecursively(parentId);
    
    if (!subtree) {
      return res.status(404).json({ success: false, message: '父节点不存在' });
    }
    res.json({ success: true, data: subtree });
  } catch (err) {
    res.status(500).json({ success: false, error: err.message });
  }
});

优化建议 #

• 给parent_node_id和node_flag建立联合索引，提升查询效率：

  CREATE INDEX idx_parent_flag ON Binary_Tree(parent_node_id, node_flag);
  

• 内存构建方案中，若数据量过大，可考虑分页拉取后分批组装，但需保证数据完整性。

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