Java多路查找树（含面试大厂题和源码）

多路查找树（Multiway Search Tree），也称为B树或B+树，是一种自平衡的树形数据结构，用于存储大量数据，通常用于数据库和文件系统中。它允许在查找、插入和删除操作中保持数据的有序性，同时优化了磁盘I/O性能。

多路查找树的特点：

节点多个子节点：与二叉查找树不同，多路查找树的每个节点可以有多个子节点（超过两个）。
有序节点值：节点内部的值是有序的，通常按照升序或降序排列。
平衡树：树保持平衡，即所有叶子节点在同一层，或者只差一层。
分裂与合并操作：在插入或删除节点时，如果节点的子节点数量超过了预设的最大值，会进行节点分裂或合并操作，以保持树的平衡。
分层索引：多路查找树可以构建分层索引，顶层的节点包含指向下一层节点的指针，这样可以快速定位到数据所在的区域。

多路查找树的应用：

数据库索引：多路查找树是许多数据库系统底层实现索引结构的基础，如B树和B+树。
文件系统：在文件系统中，多路查找树可以用于跟踪文件的位置，优化文件的读取和写入操作。
内存管理：在操作系统中，多路查找树可以用于管理内存的分配和回收。

多路查找树的Java实现（简单示例）：

由于多路查找树的实现相对复杂，以下是一个简化版的多路查找树的插入操作的Java代码示例：

class MultiwayNode {int key;MultiwayNode[] children;boolean isLeaf;public MultiwayNode(int key) {this.key = key;this.isLeaf = true;this.children = new MultiwayNode[2 * order - 1]; // 假设order为树的阶数}
}class MultiwaySearchTree {private MultiwayNode root;private int order; // 树的阶数public MultiwaySearchTree(int order) {this.order = order;}public void insert(int key) {root = insertRec(root, key);}private MultiwayNode insertRec(MultiwayNode node, int key) {if (node == null) {return new MultiwayNode(key);}int i = 0;for (; i < node.children.length - 1; i++) {if (key < node.children[i].key) {break;}}if (node.children[i] == null) {node.children[i] = new MultiwayNode(key);return node;} else if (i < node.children.length - 1 && !node.children[i].isLeaf) {node.children[i] = insertRec(node.children[i], key);return node;} else {// 需要分裂节点MultiwayNode newNode = splitNode(node, i);return fuseNodes(node, newNode);}}private MultiwayNode splitNode(MultiwayNode node, int index) {// 实现节点分裂逻辑// ...return new MultiwayNode(node.children[index].key);}private MultiwayNode fuseNodes(MultiwayNode node1, MultiwayNode node2) {// 实现节点合并逻辑// ...return new MultiwayNode(node1.key);}
}// 使用示例
public class Main {public static void main(String[] args) {MultiwaySearchTree tree = new MultiwaySearchTree(3); // 假设树的阶数为3tree.insert(5);tree.insert(3);tree.insert(7);tree.insert(1);tree.insert(9);// 树的结构现在应该是平衡的}
}

在实际应用中，多路查找树的实现会更加复杂，包括处理节点分裂和合并的详细逻辑，以及维护树的平衡性。在面试中，了解多路查找树的基本概念和操作是非常重要的，它展示了你对数据结构和算法的深入理解。希望这些知识点和示例代码能够帮助你更好地准备面试！

题目 1：实现一个B树的插入操作

描述：
实现一个B树的插入操作，B树是一种自平衡的多路查找树，用于维护排序的数据。给定一个B树和一个新的键值，将该键值插入到B树中，并保持树的平衡。

示例：

假设B树的阶数为3，给定一个空的B树和键值[1, 2, 3, 4, 5, 6, 7]，依次插入这些键值。

Java 源码：

class BTreeNode {int key;BTreeNode[] children;boolean isLeaf;public BTreeNode(int key) {this.key = key;this.isLeaf = true;}
}class BTree {private int order;private BTreeNode root;public BTree(int order) {this.order = order;}public void insert(int key) {if (root == null) {root = new BTreeNode(key);return;}root = insertNonFull(root, key);}private BTreeNode insertNonFull(BTreeNode node, int key) {if (node.isLeaf) {int i = 0;while (i < node.children.length - 1 && key > node.children[i].key) {i++;}if (i < node.children.length) {BTreeNode newNode = new BTreeNode(key);node.children[i] = newNode;return node;}// Split the node and return the new rootreturn splitChild(node, i);} else {int i = 0;while (i < node.children.length && key < node.children[i].key) {i++;}if (i < node.children.length - 1 && !node.children[i].isLeaf) {node.children[i] = insertNonFull(node.children[i], key);} else {// Split the child node and update the parentnode.children[i] = splitChild(node.children[i], i);}}return balance(node);}private BTreeNode splitChild(BTreeNode child, int index) {int newKeys = (child.key > order / 2) ? order / 2 + 1 : order / 2;BTreeNode newChild = new BTreeNode(child.key[newKeys]);System.arraycopy(child.key, index + 1, newChild.key, 0, newKeys);child.key = Arrays.copyOfRange(child.key, 0, index + 1);child.key[newKeys - 1] = child.key[newKeys];child.key = Arrays.copyOf(child.key, newKeys);newChild.isLeaf = child.isLeaf;child.children = Arrays.copyOfRange(child.children, 0, index);child.children[newKeys - 1] = newChild;child.children = Arrays.copyOf(child.children, newKeys);return child;}private BTreeNode balance(BTreeNode node) {// Implement balancing logic if needed// ...return node;}
}// 使用示例
public class Main {public static void main(String[] args) {BTree tree = new BTree(3); // 假设B树的阶数为3for (int i = 1; i <= 7; i++) {tree.insert(i);}// B树现在应该包含所有插入的键值，并且保持平衡}
}

题目 2：实现一个B+树的查找操作

描述：
实现一个B+树的查找操作，B+树是一种特殊的多路平衡查找树，所有的数据都存储在叶子节点中。给定一个B+树和一个键值，查找该键值是否存在于B+树中。

示例：

假设B+树的阶数为4，给定一个B+树和键值[10, 20, 30, 40, 50, 60, 70]，查找键值30是否存在。

Java 源码：

class BPlusLeafNode {int[] keys;BPlusLeafNode next;public BPlusLeafNode(int[] keys) {this.keys = keys;}
}class BPlusNode {BPlusNode[] children;int[] keys;boolean isLeaf;public BPlusNode(int[] keys) {this.keys = keys;this.isLeaf = keys.length == 1;}
}class BPlusTree {private BPlusNode root;private int order;public BPlusTree(int order) {this.order = order;root = new BPlusNode(new int[]{});}public boolean search(int key) {return search(root, key);}private boolean search(BPlusNode node, int key) {if (node.isLeaf) {int i = 0;while (i < node.keys.length && key > node.keys[i]) {i++;}if (i < node.keys.length && node.keys[i] == key) {return true;}return false;} else {int i = 0;while (i < node.keys.length && key < node.keys[i]) {i++;}if (i < node.keys.length) {return search(node.children[i], key);}return search(node.children[node.children.length - 1], key);}}
}// 使用示例
public class Main {public static void main(String[] args) {BPlusTree tree = new BPlusTree(4);// 假设树已经通过插入操作构建好了boolean found = tree.search(30);System.out.println("Key 30 found: " + found);}
}

题目 3：实现一个B+树的范围查询操作

描述：
实现一个B+树的范围查询操作，查询给定范围内的所有键值。B+树的所有数据都存储在叶子节点中，叶子节点之间通过指针相互连接。

示例：

假设B+树的阶数为4，给定一个B+树和键值[10, 20, 30, 40, 50, 60, 70]，查询范围在[20, 50]之间的所有键值。

Java 源码：

public class BPlusTreeRangeSearch {private BPlusLeafNode findFirstLeaf(BPlusNode node, int start) {while (!node.isLeaf) {node = node.children[findFirstKeyIndex(node, start)];}return (BPlusLeafNode) node;}private int findFirstKeyIndex(BPlusNode node, int start) {int i = 0;while (i < node.keys.length - 1 && start > node.keys[i]) {i++;}return i;}public List<Integer> rangeSearch(BPlusNode root, int start, int end) {List<Integer> results = new ArrayList<>();BPlusLeafNode leaf = findFirstLeaf(root, start);if (leaf.keys[0] >= start) {int i = 0;while (leaf != null && i < leaf.keys.length && leaf.keys[i] >= start) {while (leaf.keys[i] <= end) {results.add(leaf.keys[i]);i++;}if (leaf.next != null) {leaf = leaf.next;i = 0;} else {break;}}}return results;}
}// 使用示例
public class Main {public static void main(String[] args) {BPlusTree tree = new BPlusTree(4);// 假设树已经通过插入操作构建好了BPlusTreeRangeSearch search = new BPlusTreeRangeSearch();List<Integer> results = search.rangeSearch(tree.root, 20, 50);System.out.println("Range search results: " + results);}
}