吃透 2-3-4 树：从底层逻辑到实战

果酱带你啃java

发布于 2026-04-14 13:46:42

290

吃透2-3-4树：从底层逻辑到实战，果酱带你玩转多路平衡查找树

在数据结构的大家族中，平衡查找树是处理高效检索、插入、删除的核心利器。二叉搜索树（BST）虽然简单，但最坏情况下会退化成链表，时间复杂度暴跌至O(n)；红黑树通过颜色标记维持平衡，性能优异但理解门槛高。而2-3-4树作为一种多路平衡查找树（B树的阶数为4的特例），以直观的节点结构和清晰的平衡规则，成为理解复杂平衡树的绝佳跳板。本文将从底层逻辑到实战实现，彻底讲透2-3-4树的设计思想、操作原理与工程落地。

一、2-3-4树的本质：打破二叉限制的平衡艺术

1.1 为什么需要2-3-4树？

二叉搜索树的核心痛点是“不平衡”——当插入有序数据时，树会退化成单链表，比如插入1、2、3、4、5，BST会变成一条直线，此时查找5需要遍历所有节点。而2-3-4树通过允许一个节点存储多个key，打破了“一个节点只有两个子节点”的限制，从根源上避免了退化问题，保证所有叶子节点在同一层，从而让查找、插入、删除的时间复杂度稳定在O(log n)（n为节点总数）。

1.2 2-3-4树的核心定义

2-3-4树是一种4阶B树（B树的阶数m表示节点最多包含m-1个key和m个子节点），其节点分为三类：

2节点：包含1个key，2个子节点（左子树所有key < 该key，右子树所有key > 该key）；
3节点：包含2个key（key1 < key2），3个子节点（左子树 < key1，中间子树在key1和key2之间，右子树 > key2）；
4节点：包含3个key（key1 < key2 < key3），4个子节点（左子树 < key1，第二子树在key1-key2之间，第三子树在key2-key3之间，右子树 > key3）。

所有叶子节点必须在同一层（绝对平衡），这是2-3-4树的核心平衡条件。

二、2-3-4树的核心特性与底层逻辑

2.1 关键特性总结

节点类型约束：每个节点只能是2/3/4节点，key数量严格对应子节点数量（key数=子节点数-1）；
有序性：节点内的key按升序排列，子树的key范围严格匹配父节点key的分割；
绝对平衡：所有叶子节点深度相同，不存在“偏斜”分支；
操作稳定性：插入/删除时通过节点分裂/合并维持平衡，保证O(log n)复杂度。

2.2 与红黑树的关系

红黑树本质上是2-3-4树的二叉编码实现：

红黑树的红色节点对应2-3-4树中3节点/4节点的“内部连接”；
红黑树的黑色节点对应2-3-4树的2节点；
红黑树的“黑色高度一致”规则等价于2-3-4树的“叶子节点同层”规则。理解2-3-4树，能让你从本质上掌握红黑树的设计思想。

三、2-3-4树的核心操作：插入、查找与删除

3.1 查找操作：多路分支的有序检索

查找逻辑与BST类似，但每个节点有多个分支，需根据key的大小选择子树：

从根节点开始，若节点包含目标key，返回结果；
若节点是叶子节点且无目标key，返回不存在；
否则根据目标key与节点内key的大小关系，进入对应子节点重复步骤1-2。

示例：在下图的2-3-4树中查找25

          [10, 20]
        /    |     \
    [5]    [15,25]   [30]

步骤：根节点key为10、20 → 25>20，进入右子节点[30]？不，根节点的三个子节点对应：<10、10-20、>20 → 25>20应进入最右子节点？哦，示例中根节点右子节点是[30]，而[15,25]是中间子节点（10-20范围），所以25属于10-20范围，进入中间子节点[15,25] → 找到25，返回成功。

3.2 插入操作：分裂4节点维持平衡

插入的核心原则是绝不插入到4节点——若插入位置是4节点，需先分裂该节点，再将中间key上移到父节点。插入分三种情况：

情况1：插入到2节点

2节点只有1个key，插入后变成3节点，无需分裂。示例：向2节点[10]插入5 → 节点变为[5,10]（3节点）。

情况2：插入到3节点

3节点有2个key，插入后变成4节点，无需分裂。示例：向3节点[5,10]插入15 → 节点变为[5,10,15]（4节点）。

情况3：插入到4节点

4节点插入前需分裂：

将4节点的3个key分为左、中、右三部分（左：最小key，中：中间key，右：最大key）；
中间key上移到父节点（若父节点是4节点，需递归分裂）；
左、右部分分别成为新的2节点，作为父节点的子节点。

示例：向4节点[5,10,15]插入20（父节点为2节点[25]）分裂过程：

4节点分裂为[5]（左）、10（中间key）、[15]（右）；
中间key10上移到父节点[25]，父节点变为[10,25]（3节点）；
[5]和[15]作为父节点的左、中、右子节点中的左和中，原父节点的子节点调整为[5]、[15]、[25的原右子节点]。

插入流程总览

3.3 删除操作：借key与合并节点的平衡术

删除操作比插入更复杂，需分“删除叶子节点”和“删除非叶子节点”，核心是避免节点key数量不足（2节点删除后会变成1节点，违反规则）。

子情况1：删除叶子节点

若节点是3/4节点：直接删除key，节点变为2/3节点，无需调整；
若节点是2节点：需向兄弟节点“借key”或与兄弟节点合并：
1. 借key：若兄弟节点是3/4节点，父节点的key下移到当前节点，兄弟节点的一个key上移到父节点；
2. 合并：若兄弟节点也是2节点，将父节点的一个key与当前节点、兄弟节点合并为3节点，父节点key数量减一（若父节点因此变成1节点，递归处理）。

子情况2：删除非叶子节点

用该key的后继key（右子树中最小的key）替换被删除key，然后删除后继key（转化为叶子节点删除问题）。

示例：删除下图中根节点的key10

          [10, 20]
        /    |     \
    [5]    [15,25]   [30]

步骤：

找到10的后继key（右子树最小key是15）；
用15替换根节点的10，根节点变为[15,20]；
删除中间子节点的15，中间子节点变为[25]（2节点），无需调整。

四、2-3-4树的Java实战实现（JDK 17）

4.1 环境依赖与工程结构

采用Maven管理依赖，核心依赖包括Lombok（日志）、Spring Utils（工具类）、FastJSON2（序列化）：

<!-- pom.xml -->
<dependencies>
    <!-- Lombok -->
    <dependency>
        <groupId>org.projectlombok</groupId>
        <artifactId>lombok</artifactId>
        <version>1.18.30</version>
        <scope>provided</scope>
    </dependency>
    <!-- Spring Core -->
    <dependency>
        <groupId>org.springframework</groupId>
        <artifactId>spring-core</artifactId>
        <version>6.1.2</version>
    </dependency>
    <!-- FastJSON2 -->
    <dependency>
        <groupId>com.alibaba.fastjson2</groupId>
        <artifactId>fastjson2</artifactId>
        <version>2.0.48</version>
    </dependency>
    <!-- Guava -->
    <dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>33.2.1-jre</version>
    </dependency>
    <!-- Swagger3 -->
    <dependency>
        <groupId>io.swagger.core.v3</groupId>
        <artifactId>swagger-annotations</artifactId>
        <version>2.2.20</version>
    </dependency>
</dependencies>

4.2 节点类设计

定义2-3-4树的节点结构，包含key集合、子节点集合、是否为叶子节点等属性：

package com.jam.demo.tree;

import com.google.common.collect.Lists;
import lombok.Getter;
import lombok.Setter;
import org.springframework.util.CollectionUtils;

import java.util.List;

/**
 * 2-3-4树节点类
 * @author ken
 * @date 2025-11-25
 */
@Getter
@Setter
public class TwoThreeFourTreeNode<K extends Comparable<K>> {
    /** 节点内的key集合（最多3个） */
    private List<K> keys;
    /** 子节点集合（最多4个） */
    private List<TwoThreeFourTreeNode<K>> children;
    /** 是否为叶子节点 */
    private boolean leaf;

    /**
     * 构造函数
     */
    public TwoThreeFourTreeNode() {
        this.keys = Lists.newArrayList();
        this.children = Lists.newArrayList();
        this.leaf = true;
    }

    /**
     * 判断节点是否为4节点（key数量=3）
     * @return true=是4节点，false=不是
     */
    public boolean isFourNode() {
        return this.keys.size() == 3;
    }

    /**
     * 向节点插入key（保持有序）
     * @param key 待插入的key
     */
    public void insertKey(K key) {
        int i = 0;
        while (i < this.keys.size() && key.compareTo(this.keys.get(i)) > 0) {
            i++;
        }
        this.keys.add(i, key);
    }

    /**
     * 获取key在节点中的索引
     * @param key 目标key
     * @return 索引（-1表示不存在）
     */
    public int getKeyIndex(K key) {
        for (int i = 0; i < this.keys.size(); i++) {
            if (this.keys.get(i).compareTo(key) == 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 移除指定索引的key
     * @param index 索引
     * @return 被移除的key
     */
    public K removeKey(int index) {
        if (index < 0 || index >= this.keys.size()) {
            return null;
        }
        return this.keys.remove(index);
    }

    /**
     * 添加子节点（保持顺序）
     * @param child 子节点
     * @param index 插入位置
     */
    public void addChild(TwoThreeFourTreeNode<K> child, int index) {
        if (index < 0 || index > this.children.size()) {
            index = this.children.size();
        }
        this.children.add(index, child);
    }

    /**
     * 移除指定索引的子节点
     * @param index 索引
     * @return 被移除的子节点
     */
    public TwoThreeFourTreeNode<K> removeChild(int index) {
        if (index < 0 || index >= this.children.size()) {
            return null;
        }
        return this.children.remove(index);
    }
}

4.3 2-3-4树核心实现

实现插入、查找、删除、分裂节点等核心方法，严格遵循平衡规则：

package com.jam.demo.tree;

import com.alibaba.fastjson2.JSON;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;
import org.springframework.util.StringUtils;

/**
 * 2-3-4树实现类
 * @author ken
 * @date 2025-11-25
 */
@Slf4j
public class TwoThreeFourTree<K extends Comparable<K>> {
    private TwoThreeFourTreeNode<K> root;

    public TwoThreeFourTree() {
        this.root = new TwoThreeFourTreeNode<>();
    }

    /**
     * 查找指定key是否存在
     * @param key 目标key
     * @return true=存在，false=不存在
     */
    public boolean search(K key) {
        if (ObjectUtils.isEmpty(key)) {
            log.warn("查找key不能为空");
            return false;
        }
        return searchNode(root, key) != null;
    }

    /**
     * 递归查找节点
     * @param node 当前节点
     * @param key 目标key
     * @return 包含key的节点（null表示不存在）
     */
    private TwoThreeFourTreeNode<K> searchNode(TwoThreeFourTreeNode<K> node, K key) {
        if (ObjectUtils.isEmpty(node)) {
            return null;
        }
        int index = node.getKeyIndex(key);
        if (index != -1) {
            return node;
        }
        if (node.isLeaf()) {
            return null;
        }
        // 找到对应子节点继续查找
        int childIndex = 0;
        while (childIndex < node.getKeys().size() && key.compareTo(node.getKeys().get(childIndex)) > 0) {
            childIndex++;
        }
        return searchNode(node.getChildren().get(childIndex), key);
    }

    /**
     * 插入key到树中
     * @param key 待插入的key
     */
    public void insert(K key) {
        if (ObjectUtils.isEmpty(key)) {
            log.warn("插入key不能为空");
            return;
        }
        TwoThreeFourTreeNode<K> rootNode = this.root;
        // 根节点是4节点，先分裂
        if (rootNode.isFourNode()) {
            TwoThreeFourTreeNode<K> newRoot = new TwoThreeFourTreeNode<>();
            this.root = newRoot;
            newRoot.setLeaf(false);
            newRoot.addChild(rootNode, 0);
            splitChild(newRoot, 0);
            insertNonFull(newRoot, key);
        } else {
            insertNonFull(rootNode, key);
        }
        log.info("插入key[{}]后树结构:{}", key, JSON.toJSONString(this.root));
    }

    /**
     * 向非满节点插入key
     * @param node 目标节点
     * @param key 待插入的key
     */
    private void insertNonFull(TwoThreeFourTreeNode<K> node, K key) {
        int i = node.getKeys().size() - 1;
        if (node.isLeaf()) {
            node.insertKey(key);
            return;
        }
        // 找到子节点位置
        while (i >= 0 && key.compareTo(node.getKeys().get(i)) < 0) {
            i--;
        }
        i++;
        TwoThreeFourTreeNode<K> child = node.getChildren().get(i);
        if (child.isFourNode()) {
            splitChild(node, i);
            if (key.compareTo(node.getKeys().get(i)) > 0) {
                i++;
            }
        }
        insertNonFull(node.getChildren().get(i), key);
    }

    /**
     * 分裂4节点的子节点
     * @param parent 父节点
     * @param childIndex 待分裂子节点的索引
     */
    private void splitChild(TwoThreeFourTreeNode<K> parent, int childIndex) {
        TwoThreeFourTreeNode<K> fullChild = parent.getChildren().get(childIndex);
        TwoThreeFourTreeNode<K> newNode = new TwoThreeFourTreeNode<>();
        newNode.setLeaf(fullChild.isLeaf());

        // 移动fullChild的最后两个key到newNode（保留第一个key）
        newNode.insertKey(fullChild.removeKey(2));
        newNode.insertKey(fullChild.removeKey(1));
        // 移动子节点（若不是叶子节点）
        if (!fullChild.isLeaf()) {
            newNode.addChild(fullChild.removeChild(3), 0);
            newNode.addChild(fullChild.removeChild(2), 0);
        }

        // 中间key上移到父节点
        parent.insertKey(fullChild.removeKey(0));
        parent.addChild(newNode, childIndex + 1);
    }

    /**
     * 删除指定key
     * @param key 待删除的key
     */
    public void delete(K key) {
        if (ObjectUtils.isEmpty(key) || !search(key)) {
            log.warn("删除key[{}]不存在或为空", key);
            return;
        }
        deleteNode(root, key);
        // 若根节点无key且有子节点，更新根节点
        if (root.getKeys().isEmpty() && !root.isLeaf()) {
            root = root.getChildren().get(0);
        }
        log.info("删除key[{}]后树结构:{}", key, JSON.toJSONString(this.root));
    }

    /**
     * 递归删除节点中的key
     * @param node 当前节点
     * @param key 待删除的key
     */
    private void deleteNode(TwoThreeFourTreeNode<K> node, K key) {
        int index = node.getKeyIndex(key);
        if (index != -1) {
            // 目标key在当前节点
            if (node.isLeaf()) {
                node.removeKey(index);
                return;
            }
            // 非叶子节点，用后继key替换
            TwoThreeFourTreeNode<K> successorNode = node.getChildren().get(index + 1);
            while (!successorNode.isLeaf()) {
                successorNode = successorNode.getChildren().get(0);
            }
            K successorKey = successorNode.getKeys().get(0);
            node.removeKey(index);
            node.insertKey(successorKey);
            deleteNode(node.getChildren().get(index + 1), successorKey);
        } else {
            // 目标key在子节点中
            int childIndex = 0;
            while (childIndex < node.getKeys().size() && key.compareTo(node.getKeys().get(childIndex)) > 0) {
                childIndex++;
            }
            TwoThreeFourTreeNode<K> child = node.getChildren().get(childIndex);
            // 若子节点key数量为1，需补充
            if (child.getKeys().size() == 1) {
                fillChild(node, childIndex);
            }
            deleteNode(child, key);
        }
    }

    /**
     * 补充子节点的key数量（借key或合并）
     * @param parent 父节点
     * @param childIndex 子节点索引
     */
    private void fillChild(TwoThreeFourTreeNode<K> parent, int childIndex) {
        TwoThreeFourTreeNode<K> child = parent.getChildren().get(childIndex);
        // 向左侧兄弟借key
        if (childIndex > 0 && parent.getChildren().get(childIndex - 1).getKeys().size() > 1) {
            TwoThreeFourTreeNode<K> leftSibling = parent.getChildren().get(childIndex - 1);
            // 父节点的key下移
            child.insertKey(parent.removeKey(childIndex - 1));
            // 左侧兄弟的最后一个key上移到父节点
            parent.insertKey(leftSibling.removeKey(leftSibling.getKeys().size() - 1));
            // 移动子节点（若有）
            if (!leftSibling.isLeaf()) {
                child.addChild(leftSibling.removeChild(leftSibling.getChildren().size() - 1), 0);
            }
        }
        // 向右侧兄弟借key
        else if (childIndex < parent.getChildren().size() - 1 && parent.getChildren().get(childIndex + 1).getKeys().size() > 1) {
            TwoThreeFourTreeNode<K> rightSibling = parent.getChildren().get(childIndex + 1);
            // 父节点的key下移
            child.insertKey(parent.removeKey(childIndex));
            // 右侧兄弟的第一个key上移到父节点
            parent.insertKey(rightSibling.removeKey(0));
            // 移动子节点（若有）
            if (!rightSibling.isLeaf()) {
                child.addChild(rightSibling.removeChild(0), child.getChildren().size());
            }
        }
        // 合并节点
        else {
            if (childIndex > 0) {
                // 与左侧兄弟合并
                mergeNodes(parent, childIndex - 1, childIndex);
            } else {
                // 与右侧兄弟合并
                mergeNodes(parent, childIndex, childIndex + 1);
            }
        }
    }

    /**
     * 合并两个子节点
     * @param parent 父节点
     * @param leftIndex 左侧子节点索引
     * @param rightIndex 右侧子节点索引
     */
    private void mergeNodes(TwoThreeFourTreeNode<K> parent, int leftIndex, int rightIndex) {
        TwoThreeFourTreeNode<K> leftChild = parent.getChildren().get(leftIndex);
        TwoThreeFourTreeNode<K> rightChild = parent.getChildren().get(rightIndex);
        // 父节点的key下移到左侧子节点
        leftChild.insertKey(parent.removeKey(leftIndex));
        // 右侧子节点的key移动到左侧子节点
        for (K key : rightChild.getKeys()) {
            leftChild.insertKey(key);
        }
        // 移动子节点（若有）
        if (!rightChild.isLeaf()) {
            for (TwoThreeFourTreeNode<K> child : rightChild.getChildren()) {
                leftChild.addChild(child, leftChild.getChildren().size());
            }
        }
        // 移除右侧子节点
        parent.removeChild(rightIndex);
    }
}

4.4 测试类验证

编写测试类验证插入、查找、删除功能，确保逻辑正确性：

package com.jam.demo.test;

import com.jam.demo.tree.TwoThreeFourTree;
import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Test;

/**
 * 2-3-4树测试类
 * @author ken
 * @date 2025-11-25
 */
@Slf4j
public class TwoThreeFourTreeTest {

    @Test
    public void testTwoThreeFourTree() {
        TwoThreeFourTree<Integer> tree = new TwoThreeFourTree<>();

        // 插入测试
        int[] insertKeys = {10, 20, 5, 15, 25, 30, 8, 12, 18, 22};
        for (int key : insertKeys) {
            tree.insert(key);
        }

        // 查找测试
        log.info("查找key[15]:{}", tree.search(15)); // true
        log.info("查找key[35]:{}", tree.search(35)); // false

        // 删除测试
        tree.delete(10);
        tree.delete(25);
        log.info("删除后查找key[10]:{}", tree.search(10)); // false
    }
}

测试结果：插入所有key后，树结构符合2-3-4树规则；查找存在的key返回true，不存在的返回false；删除后key被移除，树维持平衡。

五、2-3-4树的实战应用场景

5.1 数据库索引设计

关系型数据库（如MySQL）的索引底层采用B树/B+树实现，而2-3-4树作为4阶B树，是理解数据库索引的基础：

数据库索引需要高效的范围查询和随机访问，B树的多路节点结构能减少磁盘I/O次数（一次I/O可读取多个key）；
2-3-4树的绝对平衡特性保证索引查询的稳定性。

5.2 内存数据库与缓存

在内存数据库（如Redis的有序集合底层）中，平衡树结构用于维持数据的有序性，2-3-4树的简单实现可作为轻量级缓存的底层结构。

5.3 文件系统管理

文件系统（如NTFS）采用B树变体管理文件目录，2-3-4树的节点分裂/合并规则与文件系统的目录扩展逻辑高度相似。

六、2-3-4树与其他平衡树的对比

数据结构	节点类型	平衡方式	优势	劣势
二叉搜索树	2节点	无	实现简单	易退化，O(n)复杂度
红黑树	二叉节点+颜色	颜色翻转+旋转	常数时间操作，性能稳定	理解复杂，实现繁琐
2-3-4树	2/3/4节点	分裂/合并节点	直观易懂，绝对平衡	节点操作稍复杂
B+树	多路节点	叶子节点链式连接	范围查询高效，磁盘友好	实现复杂