java 数据结构 b树 算法 查找-多路查找详解篇

多路查找树

多路查找树（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树（2-3 Tree）

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树的基础上进行了

一些优化和改进。

Java代码实现

// 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-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 keys; // 节点中存储的关键字

public List 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);

}

}

}

B+树（B+tree）

B+树（B+ tree）是B-树的一种变种，特别适用于范围查询和顺序访问。

结构特点：

B+树与B-树类似，由节点组成，每个节点可以存储多个关键字，这些关键字按升

序排列。

B+树的特点是只有叶子节点存储了真实数据，而内部节点仅用于索引。叶子节点

通过指针连接形成一个链表，方便范围查询和顺序访问。

内部节点特点：

内部节点存储关键字和指向子节点的指针。

内部节点的关键字按升序排列，用于指示范围查询的起点。

内部节点的指针指向比关键字更大的子节点。

叶子节点特点：

叶子节点存储真实数据和指向下一个叶子节点的指针。

叶子节点的关键字按升序排列，支持范围查询和顺序访问。

所有叶子节点通过指针连接成一个链表，便于范围查询和顺序访问。

插入操作：

当要插入一个关键字时，从根节点开始，找到合适的叶子节点。

如果叶子节点已满，则需要进行节点分裂操作。将中间位置的关键字提升到父节

点，并将两个剩余的部分分别创建为新的叶子节点。

如果叶子节点还没有满，则直接将关键字插入到合适的位置。

删除操作：

当要删除一个关键字时，从根节点开始，找到包含该关键字的叶子节点。

直接删除叶子节点中的关键字，并更新链表指针。

删除操作后，如果叶子节点的关键字个数过少，则需要从兄弟节点借用关键字或

进行节点合并。

查询操作：

B+树的查询操作与B-树类似，从根节点开始，根据关键字的大小比较，向左或向

右子节点递归查询，直到找到匹配的关键字或遇到叶子节点。

对于范围查询和顺序访问，可以从叶子节点开始，沿着链表进行遍历。

强调

B+树的特点在于只有叶子节点存储真实数据，这样使得范围查询和顺序访问更加

高效，因为数据在叶子节点上连续存储，读取连续的数据块比随机读取更快。而

内部节点仅存储索引信息，可以容纳更多的索引，提高了查询效率。B+树的实现

适用于需要高效地处理大量数据的数据库和文件系统，能够提供较高的查询性能

和存储效率。

代码实现

import java.util.ArrayList;

import java.util.List;

class BPlusTreeNode {

public boolean isLeaf;

public List keys;

public List