树形结构数据存储方案对比：父子关系 vs 改进后的先序树

树形结构数据存储方案对比：父子关系 vs 改进后的先序树

在处理树形结构数据时，通常会遇到节点的增删改、查询子节点、统计数量等需求。本文将通过一个简单的公司组织架构示例，详细讲解两种常见的树形结构设计方案：父子关系方案和改进后的先序树方案，并对比它们的实现方式和优缺点。

1. 父子关系方案

父子关系方案的核心思想是每个节点只关注自己的父节点，并通过递归方式获取层级关系。这种方案简单易懂，但当数据量大、层级深时，性能会受到影响。

方案特点

• 优点

• 方案简单易懂

• 数据结构简单清晰

• 层级直观、鲜明

• 易维护（层级关系只需要关注自己的父ID）

• 缺点

• 查找麻烦、统计麻烦（需要递归逐层查找）

示例

以一个简单的公司组织架构为例：

对应的表结构如下：

SQL脚本：

DROP TABLE IF EXISTS `department_info`;
CREATE TABLE `department_info`  (
  `id` int(11) NOT NULL,
  `dep_name` varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NULL DEFAULT NULL COMMENT '名称',
  `level` int(11) NULL DEFAULT NULL,
  `parent_id` int(11) NULL DEFAULT NULL COMMENT '父ID',
  PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8mb4 COLLATE = utf8mb4_general_ci ROW_FORMAT = Dynamic;

INSERT INTO `department_info` VALUES (1, '董事会', 1, 0);
INSERT INTO `department_info` VALUES (2, '总经理', 2, 1);
INSERT INTO `department_info` VALUES (3, '董事会秘书', 2, 1);
INSERT INTO `department_info` VALUES (4, '产品部', 3, 2);
INSERT INTO `department_info` VALUES (5, '行政总监', 3, 2);
INSERT INTO `department_info` VALUES (6, '设计部', 4, 4);
INSERT INTO `department_info` VALUES (7, '技术部', 4, 4);
INSERT INTO `department_info` VALUES (8, '财务部', 4, 5);
INSERT INTO `department_info` VALUES (9, '行政部', 4, 5);
INSERT INTO `department_info` VALUES (10, '客户端', 5, 7);
INSERT INTO `department_info` VALUES (11, '服务端', 5, 7);

为了方便查询，可以创建两个递归函数：

• 递归查询子孙节点ID的函数
• 递归查询祖先节点ID的函数

2. 改进后的先序树方案

改进后的先序树方案通过为每个节点增加左值和右值来优化查询性能。这种方案避免了递归查询，但在节点增删改时需要维护左右值，相对复杂。

方案特点

• 优点

• 查询汇总简单高效

• 无需递归查询，性能高

• 缺点

• 结构相对复杂，数据层面理解难度较高

• 不易维护（左右值的存在会影响后续节点）

示例

对应的表数据如下：

SQL语句：

DROP TABLE IF EXISTS `department_info2`;
CREATE TABLE `department_info2`  (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `dep_name` varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NOT NULL COMMENT '名称',
  `lt` int(11) NOT NULL COMMENT '节点左数',
  `rt` int(11) NOT NULL COMMENT '节点右数',
  `lv` int(11) NOT NULL,
  PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 12 CHARACTER SET = utf8mb4 COLLATE = utf8mb4_general_ci ROW_FORMAT = Dynamic;

INSERT INTO `department_info2` VALUES (1, '董事会', 1, 22, 1);
INSERT INTO `department_info2` VALUES (2, '总经理', 2, 19, 2);
INSERT INTO `department_info2` VALUES (3, '董事会秘书', 20, 21, 2);
INSERT INTO `department_info2` VALUES (4, '产品部', 3, 12, 3);
INSERT INTO `department_info2` VALUES (5, '行政总监', 13, 18, 3);
INSERT INTO `department_info2` VALUES (6, '设计部', 4, 5, 4);
INSERT INTO `department_info2` VALUES (7, '技术部', 6, 11, 4);
INSERT INTO `department_info2` VALUES (8, '财务部', 14, 15, 4);
INSERT INTO `department_info2` VALUES (9, '行政部', 16, 17, 4);
INSERT INTO `department_info2` VALUES (10, '客户端', 7, 8, 5);
INSERT INTO `department_info2` VALUES (11, '服务端', 9, 10, 5);

3. 格式化数据

无论是哪种方案，数据层面都是扁平的，需要通过递归或非递归方式将其结构化成树形结构。

递归整理

使用Java 8 Stream新特性简化递归代码：

public static void recursive(List<LrItem> deps) {
    init(deps);
    List<LrItem> collect = deps.stream()
            .filter(m -> m.getParentId() == 0)
            .map(m -> {
                m.setChildItem(getChildrens(m, deps));
                return m;
            })
            .collect(Collectors.toList());
    System.out.println(JSON.toJSON(collect.get(0)));
}

private static List<LrItem> getChildrens(LrItem root, List<LrItem> all) {
    List<LrItem> children = all.stream()
            .filter(m -> Objects.equals(m.getParentId(), root.getId()))
            .map(m -> {
                m.setChildItem(getChildrens(m, all));
                return m;
            })
            .collect(Collectors.toList());
    return children;
}

非递归倒序整理

这是一个以空间换时间的方案：

public static void reverseFormat(List<LrItem> deps) {
    init(deps);
    deps.sort(Comparator.comparing(LrItem::getLevel));
    Map<Integer, List<LrItem>> childCache = new HashMap<>();
    LrItem lrItem = null;
    for (int i = deps.size() - 1; i >= 0; i--) {
        lrItem = deps.get(i);
        Integer parentId = lrItem.getParentId();
        if (parentId != null) {
            List<LrItem> childItems = childCache.get(parentId);
            if (childItems == null) {
                childCache.put(parentId, childItems = new ArrayList<>());
            }
            childItems.add(lrItem);
            if (!lrItem.getIsLeaf()) {
                childItems = childCache.get(lrItem.getId());
                childItems.sort(Comparator.comparing(LrItem::getId));
                lrItem.setChildItem(childItems);
                childCache.remove(lrItem.getId());
            }
        }
    }
    System.out.println(JSON.toJSONString(lrItem));
}

4. 比较

5. 总结

• 父子关系方案适合结构简单、层级少的需求。
• 先序数方案适合结构复杂、改动少、层级深、需要频繁汇总统计的需求。

没有绝对好的方案，只有合不合适的场景。选择方案时，需要根据具体业务需求来决定。