多路查找树（Multway Search Tree）是一种高级的树形数据结构，它
允许每个节点有多个子节点（通常大于等于2）。多路查找树的每个节点
可以存储多个关键字和对应的值。

2-3树（2-3 Tree）：
2-3树是一种最简单的多路查找树，每个节点可以存储1个或2个关键字，
并有2个或3个子节点。
2-3树的特点是所有叶子节点都在同一层，且根节点到每个叶子节点的
路径长度相等，保持树的平衡性。
B-树（B-tree）：
B-树是一种平衡的多路查找树，每个节点可以存储多个关键字，并有相
应数量的子节点。
B-树的特点是节点的关键字按照升序排列，具有高度平衡的特性，主要
用于在磁盘等外部存储设备中高效存储和检索数据。
B+树（B+ tree）：
B+树是B-树的一种变种，在B-树的基础上做了一些优化，特别适合于范
围查询和顺序访问。
B+树的特点是只有叶子节点存储了真实数据，而内部节点仅用于索引，
叶子节点通过指针连接形成一个链表，方便范围查询。
B树（B-tree）：
B*树也是B-树的一种变种，与B+树类似，它在B-树的基础上做了一些改
进。
B*树通过在非叶子节点中存储部分关键字，扩大了节点的使用率，减少
了磁盘访问次数，并提高了空间和时间的效率。
Trie树（字典树或前缀树）：
Trie树是一种特殊的多路查找树，在处理字符串和前缀匹配的情况下非
常有用。
Trie树的特点是每个节点代表一个字符，从根节点到叶子节点的路径可
以表示一个完整的字符串。
除此以外，还有如2-3-4树、2-3-4-树、B*+树等。每种多路查找树在
平衡性、存储结构、查询性能等方面可能有所不同，选择合适的多路查
找树取决于应用需求和数据特点。对于大规模的外部存储数据，B-树和
B+树是常见的选择；对于高效的字符串匹配和前缀查询，Trie树是一种
有效的数据结构。

2-3树是一种平衡的多路查找树，每个节点可以存储1个或2个关键字，并有2个
或3个子节点。以下是关于2-3树的详细介绍：

2-3树由节点组成，每个节点可以存储1个或2个关键字，这些关键字按升序排列。
每个节点有2个或3个子节点，对应于存储的关键字个数。
所有叶子节点都在同一层，且根节点到每个叶子节点的路径长度相等，保持树的
平衡性。

1、当要插入一个关键字时，从根节点开始，判断关键字应插入的位置。
2、如果节点已满（即已有两个关键字），则需要进行节点分裂操作。将中间较
  大的关键字移动到上一层的父节点，并将两个剩余的关键字分别创建为新的
  子节点。
3、如果节点还没有满，则直接将关键字插入到正确的位置。

当要删除一个关键字时，从根节点开始，找到包含该关键字的节点。
  如果该节点是叶子节点，直接删除关键字即可。如果该节点是内部节点，有
    几种情况需要处理：
  如果该节点有2个关键字，则可以直接删除关键字，不需要做其他操作。
  如果该节点有1个关键字：
  如果其兄弟节点有2个关键字，则可以借用兄弟节点的一个关键字，并进行
    相关的调整。
  如果其兄弟节点也只有1个关键字，则需要进行合并操作，将关键字和子节
    点合并到一起。

2-3树的查询操作与二叉查找树类似，从根节点开始，根据关键字的大小比较，
向左或向右子节点递归查询，直到找到匹配的关键字或遇到叶子节点。

2-3树的特点在于其每个节点可以存储多个关键字，这样可以减少树的高度，提
供更高效的搜索和插入操作。它保持了树的平衡性，且所有叶子节点都在同一层，
这样可以保证较为平衡的查询性能。然而，2-3树的实现和维护操作较为复杂，
导致其并不常用，更常见的是其变种B-树和B+树，它们在2-3树的基础上进行了
一些优化和改进。

// 2-3树的节点类
class Node {
    private int[] keys;  // 节点的关键字
    private Node[] children;  // 子节点数组
    private int size;  // 节点包含的关键字数量
    private boolean isLeaf;  // 是否为叶子节点
    public Node(boolean isLeaf) {
        this.keys = new int[3];
        this.children = new Node[4];
        this.size = 0;
        this.isLeaf = isLeaf;
    }
    // 从节点中查找关键字的位置
    public int findKey(int key) {
        for (int i = 0; i < size; i++) {
            if (keys[i] == key) {
                return i;
            } else if (keys[i] > key) {
                return -1;
            }
        }
        return -1;
    }
    // 在节点中插入关键字
    public void insertKey(int key) {
        if (size == 0) {
            keys[0] = key;
            size++;
        } else {
            int i = size - 1;
            while (i >= 0 && keys[i] > key) {
                keys[i + 1] = keys[i];
                i--;
            }
            keys[i + 1] = key;
            size++;
        }
    }
    // 在节点中删除关键字
    public void deleteKey(int key) {
        int index = findKey(key);
        if (index != -1) {
            for (int i = index; i < size - 1; i++) {
                keys[i] = keys[i + 1];
            }
            size--;
        }
    }
    // 获取节点的关键字数量
    public int getSize() {
        return size;
    }
    // 判断节点是否为叶子节点
    public boolean isLeaf() {
        return isLeaf;
    }
    // 获取节点指定位置的子节点
    public Node getChild(int index) {
        return children[index];
    }
    // 设置节点指定位置的子节点
    public void setChild(int index, Node child) {
        children[index] = child;
    }
}
// 2-3树类
class TwoThreeTree {
    private Node root;
    public TwoThreeTree() {
        root = null;
    }
    // 在2-3树中插入关键字
    public void insert(int key) {
        if (root == null) {
            root = new Node(true);
            root.insertKey(key);
        } else {
            Node newNode = insertKey(root, key);
            if (newNode != null) {
                Node oldRoot = root;
                root = new Node(false);
                root.setChild(0, oldRoot);
                root.setChild(1, newNode);
                root.insertKey(newNode.keys[0]);
                root.insertKey(oldRoot.keys[0]);
            }
        }
    }
    // 在给定的节点中插入关键字
    private Node insertKey(Node node, int key) {
        if (node.isLeaf()) {
            node.insertKey(key);
            if (node.getSize() > 2) {
                return splitLeaf(node);
            }
        } else {
            int i = node.getSize() - 1;
            while (i >= 0 && key < node.getChild(i).keys[0]) {
                i--;
            }
            Node newNode = insertKey(node.getChild(i + 1), key);
            if (newNode != null) {
                node.insertKey(newNode.keys[0]);
  }

B-树（B-tree）是一种平衡的多路查找树，广泛应用于在磁盘等外部存储设备中
高效地存储和检索大量数据。以下是关于B-树的详细介绍：

B-树由节点组成，每个节点可以存储多个
关键字，这些关键字按升序排列。
B-树的特点是节点的关键字按升序排列，具有高度平衡的特性。
每个节点通常有多个子节点，最多可以拥有m个子节点，其中m称为B-树的阶数。

1、当要插入一个关键字时，从根节点开始，判断关键字应插入的位置。
2、如果节点已满，则需要进行节点分裂操作。将中间位置的关键字提升为父节
  点，并将节点分裂为两个节点，将剩余的关键字均匀分配到这两个节点中。
3、如果要插入的节点还没有满，则直接将关键字插入到合适的位置。

1、当要删除一个关键字时，从根节点开始，找到包含该关键字的节点。
2、如果该节点是叶子节点，直接删除关键字即可。如果该节点是内部节点，需
  要找到其前驱或后继关键字来替代删除的关键字。
3、在删除操作后，如果节点中的关键字数量过少，则需要进行节点合并或者从
  兄弟节点中借用关键字来保持树的平衡。

B-树的查询操作与二叉查找树类似，从根节点开始，根据关键字的大小比较，
向左或向右子节点递归查询，直到找到匹配的关键字或遇到叶子节点。

B-树适用于大规模数据存储和查询的场景，尤其是需要在外部存储设备上进行操
作的情况。B-树的高度平衡保证了较为均衡的查询性能，因为从根节点到叶子节
点的路径长度相等或差别不大。B-树的阶数m可以根据具体应用和硬件限制来选
择，通常情况下，较大的阶数有助于减少磁盘访问的次数，提高效率。
B-树的变种B+树在B-树的基础上做了一些优化，将所有数据存储在叶子节点中，
使得范围查询和顺序访问更加高效。因此，在现代数据库系统和文件系统中，
B+树更加常见和广泛应用。

import java.util.ArrayList;
import java.util.List;
class BMinusTreeNode {
    public boolean isLeaf; // 是否是叶子节点
    public List<Integer> keys; // 节点中存储的关键字
    public List<BMinusTreeNode> children; // 节点的子节点
    public BMinusTreeNode() {
        keys = new ArrayList<>();
        children = new ArrayList<>();
    }
}
class BMinusTree {
    private BMinusTreeNode root;
    private int t; // B-树的阶数
    public BMinusTree(int degree) {
        root = new BMinusTreeNode();
        root.isLeaf = true;
        t = degree;
    }
    public void insert(int key) {
        // 根节点满了就分裂
        if (root.keys.size() == (2 * t)) {
            BMinusTreeNode newRoot = new BMinusTreeNode();
            newRoot.children.add(root);
            splitChild(newRoot, 0, root);
            root = newRoot;
        }
        insertNonFull(root, key);
    }
    private void insertNonFull(BMinusTreeNode node, int key) {
        int index = node.keys.size() - 1;
        if (node.isLeaf) {
            while (index >= 0 && node.keys.get(index) > key) {
                index--;
            }
            node.keys.add(index + 1, key);
        } else {
            while (index >= 0 && node.keys.get(index) > key) {
                index--;
            }
            index++;
            if (node.children.get(index).keys.size() == (2 * t)) {
                splitChild(node, index, node.children.get(index));
                if (node.keys.get(index) < key) {
                    index++;
                }
            }
            insertNonFull(node.children.get(index), key);
        }
    }
    private void splitChild(BMinusTreeNode parent, int index, BMinusTreeNode node) {
        BMinusTreeNode newNode = new BMinusTreeNode();
        newNode.isLeaf = node.isLeaf;
        parent.keys.add(index, node.keys.get(t - 1));
        parent.children.add(index + 1, newNode);
        for (int i = t; i < 2 * t - 1; i++) {
            newNode.keys.add(node.keys.get(i));
        }
        if (!node.isLeaf) {
            for (int i = t; i < 2 * t; i++) {
                newNode.children.add(node.children.get(i));
            }
        }
        for (int i = 2 * t - 2; i >= t - 1; i--) {
            node.keys.remove(i);
        }
        if (!node.isLeaf) {
            for (int i = 2 * t - 1; i >= t; i--) {
                node.children.remove(i);
            }
        }
    }