得物Java面试被问：B+树的分裂合并和范围查询优化
一、B+树核心数据结构
1. 节点结构定义
java
复制
下载
// B+树节点抽象 public abstract class BPlusTreeNode<K extends Comparable<K>, V> { protected boolean isLeaf; // 是否为叶子节点 protected int degree; // 树的度（最大子节点数） protected List<K> keys; // 关键字列表 protected BPlusTreeNode<K, V> parent; // 父节点 // 公共方法 public abstract int size(); public abstract boolean isFull(); public abstract boolean isUnderflow(); public abstract int getMinKeys(); } // 内部节点（索引节点） public class InternalNode<K extends Comparable<K>, V> extends BPlusTreeNode<K, V> { private List<BPlusTreeNode<K, V>> children; // 子节点指针 public InternalNode(int degree) { this.degree = degree; this.isLeaf = false; this.keys = new ArrayList<>(degree); this.children = new ArrayList<>(degree + 1); this.parent = null; } @Override public int size() { return keys.size(); } @Override public boolean isFull() { return keys.size() >= degree - 1; // 内部节点最多degree-1个key } @Override public boolean isUnderflow() { return keys.size() < Math.ceil(degree / 2.0) - 1; } @Override public int getMinKeys() { return (int) Math.ceil(degree / 2.0) - 1; } } // 叶子节点（数据节点） public class LeafNode<K extends Comparable<K>, V> extends BPlusTreeNode<K, V> { private List<V> values; // 数据值 private LeafNode<K, V> next; // 下一个叶子节点（用于范围查询） private LeafNode<K, V> prev; // 上一个叶子节点 public LeafNode(int degree) { this.degree = degree; this.isLeaf = true; this.keys = new ArrayList<>(degree - 1); this.values = new ArrayList<>(degree - 1); this.next = null; this.prev = null; } @Override public int size() { return keys.size(); } @Override public boolean isFull() { return keys.size() >= degree - 1; // 叶子节点最多degree-1个key-value对 } @Override public boolean isUnderflow() { return keys.size() < Math.ceil((degree - 1) / 2.0); } @Override public int getMinKeys() { return (int) Math.ceil((degree - 1) / 2.0); } // 在叶子节点中查找键的位置 public int findKeyIndex(K key) { int left = 0; int right = keys.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; int cmp = keys.get(mid).compareTo(key); if (cmp == 0) { return mid; // 找到 } else if (cmp < 0) { left = mid + 1; } else { right = mid - 1; } } return -left - 1; // 未找到，返回插入位置 } }
二、节点分裂策略
1. 叶子节点分裂
java
复制
下载
public class BPlusTree<K extends Comparable<K>, V> { private BPlusTreeNode<K, V> root; private int degree; private LeafNode<K, V> head; // 叶子节点链表头 /** * 叶子节点分裂 */ private void splitLeafNode(LeafNode<K, V> leafNode) { // 1. 创建新叶子节点 LeafNode<K, V> newLeaf = new LeafNode<>(degree); // 2. 计算分裂点（通常是中间位置） int splitIndex = leafNode.size() / 2; // 3. 移动后半部分数据到新节点 for (int i = splitIndex; i < leafNode.size(); i++) { newLeaf.keys.add(leafNode.keys.get(i)); newLeaf.values.add(leafNode.values.get(i)); } // 移除原节点中已移动的数据 for (int i = leafNode.size() - 1; i >= splitIndex; i--) { leafNode.keys.remove(i); leafNode.values.remove(i); } // 4. 更新叶子节点链表 newLeaf.next = leafNode.next; if (leafNode.next != null) { leafNode.next.prev = newLeaf; } leafNode.next = newLeaf; newLeaf.prev = leafNode; // 5. 获取新节点的第一个key（用于向上传递） K newKey = newLeaf.keys.get(0); // 6. 插入新key到父节点 insertIntoParent(leafNode, newKey, newLeaf); } /** * 插入到父节点 */ private void insertIntoParent(BPlusTreeNode<K, V> leftChild, K key, BPlusTreeNode<K, V> rightChild) { if (leftChild.parent == null) { // 需要创建新的根节点 createNewRoot(leftChild, key, rightChild); return; } InternalNode<K, V> parent = (InternalNode<K, V>) leftChild.parent; // 1. 找到插入位置 int insertIndex = findInsertIndex(parent.keys, key); // 2. 插入key和右孩子 parent.keys.add(insertIndex, key); parent.children.add(insertIndex + 1, rightChild); rightChild.parent = parent; // 3. 如果父节点满了，继续分裂 if (parent.isFull()) { splitInternalNode(parent); } } /** * 创建新根节点 */ private void createNewRoot(BPlusTreeNode<K, V> leftChild, K key, BPlusTreeNode<K, V> rightChild) { InternalNode<K, V> newRoot = new InternalNode<>(degree); newRoot.keys.add(key); newRoot.children.add(leftChild); newRoot.children.add(rightChild); leftChild.parent = newRoot; rightChild.parent = newRoot; this.root = newRoot; } }
2. 内部节点分裂
java
复制
下载
public class BPlusTree<K extends Comparable<K>, V> { /** * 内部节点分裂 */ private void splitInternalNode(InternalNode<K, V> node) { // 1. 创建新的内部节点 InternalNode<K, V> newNode = new InternalNode<>(degree); // 2. 计算分裂点（中间key的索引） int splitIndex = node.size() / 2; K promoteKey = node.keys.get(splitIndex); // 中间key要提升到父节点 // 3. 移动后半部分key和children到新节点 for (int i = splitIndex + 1; i < node.size(); i++) { newNode.keys.add(node.keys.get(i)); } for (int i = splitIndex + 1; i < node.children.size(); i++) { BPlusTreeNode<K, V> child = node.children.get(i); newNode.children.add(child); child.parent = newNode; } // 4. 移除原节点中已移动的数据 for (int i = node.size() - 1; i >= splitIndex; i--) { node.keys.remove(i); } for (int i = node.children.size() - 1; i >= splitIndex + 1; i--) { node.children.remove(i); } // 5. 提升中间key到父节点 if (node.parent == null) { // 需要创建新的根节点 createNewRoot(node, promoteKey, newNode); } else { InternalNode<K, V> parent = (InternalNode<K, V>) node.parent; int insertIndex = findInsertIndex(parent.keys, promoteKey); parent.keys.add(insertIndex, promoteKey); parent.children.add(insertIndex + 1, newNode); newNode.parent = parent; // 递归检查父节点 if (parent.isFull()) { splitInternalNode(parent); } } } /** * 找到插入位置的辅助方法（二分查找） */ private int findInsertIndex(List<K> keys, K key) { int left = 0; int right = keys.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; int cmp = keys.get(mid).compareTo(key); if (cmp < 0) { left = mid + 1; } else { right = mid - 1; } } return left; } }
篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc
需要全套面试笔记及答案
【点击此处即可/免费获取】
三、节点合并策略
1. 叶子节点合并
java
复制
下载
public class BPlusTree<K extends Comparable<K>, V> { /** * 叶子节点合并 * @param node 需要合并的节点（关键字不足） */ private void mergeLeafNodes(LeafNode<K, V> node) { // 尝试从左兄弟借一个元素 if (node.prev != null && node.prev.parent == node.parent) { LeafNode<K, V> leftSibling = node.prev; if (leftSibling.size() > leftSibling.getMinKeys()) { // 可以从左兄弟借 borrowFromLeftSibling(node, leftSibling); return; } } // 尝试从右兄弟借一个元素 if (node.next != null && node.next.parent == node.parent) { LeafNode<K, V> rightSibling = node.next; if (rightSibling.size() > rightSibling.getMinKeys()) { // 可以从右兄弟借 borrowFromRightSibling(node, rightSibling); return; } } // 无法借用，需要合并 if (node.prev != null && node.prev.parent == node.parent) { // 与左兄弟合并 mergeWithLeftSibling(node); } else if (node.next != null && node.next.parent == node.parent) { // 与右兄弟合并 mergeWithRightSibling(node); } } /** * 从左兄弟借用元素 */ private void borrowFromLeftSibling(LeafNode<K, V> node, LeafNode<K, V> leftSibling) { // 1. 获取左兄弟的最后一个元素 int lastIndex = leftSibling.size() - 1; K borrowedKey = leftSibling.keys.get(lastIndex); V borrowedValue = leftSibling.values.get(lastIndex); // 2. 从左兄弟移除 leftSibling.keys.remove(lastIndex); leftSibling.values.remove(lastIndex); // 3. 插入到当前节点开头 node.keys.add(0, borrowedKey); node.values.add(0, borrowedValue); // 4. 更新父节点的分隔key updateParentSeparator(node, borrowedKey); } /** * 从右兄弟借用元素 */ private void borrowFromRightSibling(LeafNode<K, V> node, LeafNode<K, V> rightSibling) { // 1. 获取右兄弟的第一个元素 K borrowedKey = rightSibling.keys.get(0); V borrowedValue = rightSibling.values.get(0); // 2. 从右兄弟移除 rightSibling.keys.remove(0); rightSibling.values.remove(0); // 3. 插入到当前节点末尾 node.keys.add(borrowedKey); node.values.add(borrowedValue); // 4. 更新父节点的分隔key updateParentSeparator(rightSibling, rightSibling.keys.get(0)); } /** * 与左兄弟合并 */ private void mergeWithLeftSibling(LeafNode<K, V> node) { LeafNode<K, V> leftSibling = node.prev; // 1. 将所有元素移动到左兄弟 for (int i = 0; i < node.size(); i++) { leftSibling.keys.add(node.keys.get(i)); leftSibling.values.add(node.values.get(i)); } // 2. 更新叶子节点链表 leftSibling.next = node.next; if (node.next != null) { node.next.prev = leftSibling; } // 3. 从父节点中删除对应的key和指针 InternalNode<K, V> parent = (InternalNode<K, V>) node.parent; int indexInParent = findChildIndex(parent, node); // 删除指向当前节点的指针和对应的key parent.keys.remove(indexInParent - 1); parent.children.remove(indexInParent); // 4. 检查父节点是否下溢 if (parent.isUnderflow()) { if (parent == root && parent.size() == 0) { // 根节点为空，降低树的高度 root = leftSibling; leftSibling.parent = null; } else { mergeInternalNodes(parent); } } } }
2. 内部节点合并
java
复制
下载
public class BPlusTree<K extends Comparable<K>, V> { /** * 内部节点合并 */ private void mergeInternalNodes(InternalNode<K, V> node) { // 查找兄弟节点 InternalNode<K, V> parent = (InternalNode<K, V>) node.parent; int nodeIndex = findChildIndex(parent, node); // 尝试从左兄弟借用 if (nodeIndex > 0) { InternalNode<K, V> leftSibling = (InternalNode<K, V>) parent.children.get(nodeIndex - 1); if (leftSibling.size() > leftSibling.getMinKeys()) { borrowFromLeftInternalSibling(node, leftSibling, parent, nodeIndex); return; } } // 尝试从右兄弟借用 if (nodeIndex < parent.children.size() - 1) { InternalNode<K, V> rightSibling = (InternalNode<K, V>) parent.children.get(nodeIndex + 1); if (rightSibling.size() > rightSibling.getMinKeys()) { borrowFromRightInternalSibling(node, rightSibling, parent, nodeIndex); return; } } // 需要合并 if (nodeIndex > 0) { // 与左兄弟合并 mergeWithLeftInternalSibling(node, parent, nodeIndex); } else { // 与右兄弟合并 mergeWithRightInternalSibling(node, parent, nodeIndex); } } /** * 从左兄弟内部节点借用 */ private void borrowFromLeftInternalSibling(InternalNode<K, V> node, InternalNode<K, V> leftSibling, InternalNode<K, V> parent, int nodeIndex) { // 1. 从父节点借一个key K parentKey = parent.keys.get(nodeIndex - 1); // 2. 从左兄弟获取最后一个child BPlusTreeNode<K, V> borrowedChild = leftSibling.children.remove( leftSibling.children.size() - 1); K borrowedKey = leftSibling.keys.remove(leftSibling.keys.size() - 1); // 3. 父节点的key下移到当前节点开头 node.keys.add(0, parentKey); node.children.add(0, borrowedChild); borrowedChild.parent = node; // 4. 借来的key上移到父节点 parent.keys.set(nodeIndex - 1, borrowedKey); } /** * 合并内部节点 */ private void mergeWithLeftInternalSibling(InternalNode<K, V> node, InternalNode<K, V> parent, int nodeIndex) { InternalNode<K, V> leftSibling = (InternalNode<K, V>) parent.children.get(nodeIndex - 1); // 1. 将父节点的分隔key下移 K parentKey = parent.keys.get(nodeIndex - 1); leftSibling.keys.add(parentKey); // 2. 将当前节点的所有key和children移到左兄弟 for (K key : node.keys) { leftSibling.keys.add(key); } for (BPlusTreeNode<K, V> child : node.children) { leftSibling.children.add(child); child.parent = leftSibling; } // 3. 从父节点中删除 parent.keys.remove(nodeIndex - 1); parent.children.remove(nodeIndex); // 4. 递归检查父节点 if (parent.isUnderflow()) { if (parent == root && parent.size() == 0) { root = leftSibling; leftSibling.parent = null; } else { mergeInternalNodes(parent); } } } }
四、范围查询优化
1. 叶子节点链表遍历
java
复制
下载
public class BPlusTree<K extends Comparable<K>, V> { /** * 范围查询 * @param startKey 起始key（包含） * @param endKey 结束key（包含） * @return 范围内的所有值 */ public List<V> rangeQuery(K startKey, K endKey) { List<V> results = new ArrayList<>(); // 1. 找到起始key所在的叶子节点 LeafNode<K, V> startNode = findLeafNode(startKey); if (startNode == null) { return results; } // 2. 在起始节点中找到起始位置 int startIndex = startNode.findKeyIndex(startKey); if (startIndex < 0) { startIndex = -startIndex - 1; // 转换为插入位置 } // 3. 遍历叶子节点链表 LeafNode<K, V> currentNode = startNode; int currentIndex = startIndex; while (currentNode != null) { while (currentIndex < currentNode.size()) { K currentKey = currentNode.keys.get(currentIndex); // 检查是否超出范围 if (currentKey.compareTo(endKey) > 0) { return results; } results.add(currentNode.values.get(currentIndex)); currentIndex++; } // 移动到下一个叶子节点 currentNode = currentNode.next; currentIndex = 0; } return results; } /** * 批量范围查询优化（预取） */ public List<V> rangeQueryWithPrefetch(K startKey, K endKey, int batchSize) { List<V> results = new ArrayList<>(); // 1. 找到起始节点 LeafNode<K, V> currentNode = findLeafNode(startKey); int currentIndex = 0; // 预取下一批节点 List<LeafNode<K, V>> prefetchedNodes = prefetchNodes(currentNode, batchSize); while (!prefetchedNodes.isEmpty()) { for (LeafNode<K, V> node : prefetchedNodes) { // 2. 对每个节点进行二分查找，快速定位范围 int start = binarySearchInNode(node, startKey); int end = binarySearchInNode(node, endKey); if (start < 0) start = -start - 1; if (end < 0) end = -end - 2; // end是最后一个<=endKey的位置 // 3. 批量添加结果 for (int i = start; i <= end && i < node.size(); i++) { results.add(node.values.get(i)); } // 如果已经超过endKey，提前结束 if (end < node.size() - 1 && node.keys.get(end + 1).compareTo(endKey) > 0) { return results; } } // 4. 预取下一批节点 currentNode = prefetchedNodes.get(prefetchedNodes.size() - 1).next; prefetchedNodes = prefetchNodes(currentNode, batchSize); } return results; } /** * 预取节点（减少磁盘IO） */ private List<LeafNode<K, V>> prefetchNodes(LeafNode<K, V> startNode, int count) { List<LeafNode<K, V>> nodes = new ArrayList<>(); LeafNode<K, V> current = startNode; for (int i = 0; i < count && current != null; i++) { nodes.add(current); current = current.next; } return nodes; } }
2. 并行范围查询
java
复制
下载
public class ParallelBPlusTree<K extends Comparable<K>, V> extends BPlusTree<K, V> { private ExecutorService executor; /** * 并行范围查询 */ public List<V> parallelRangeQuery(K startKey, K endKey, int numThreads) { // 1. 估算范围内的大致数据量 long estimatedSize = estimateRangeSize(startKey, endKey); // 2. 根据数据量决定是否并行 if (estimatedSize < 1000) { return super.rangeQuery(startKey, endKey); } // 3. 分割查询范围 List<RangeTask> tasks = splitRange(startKey, endKey, numThreads); // 4. 提交任务并行执行 List<Future<List<V>>> futures = new ArrayList<>(); for (RangeTask task : tasks) { futures.add(executor.submit(() -> executeRangeQuery(task.startKey, task.endKey))); } // 5. 收集结果 List<V> results = new ArrayList<>(); for (Future<List<V>> future : futures) { try { results.addAll(future.get()); } catch (Exception e) { // 处理异常，继续执行其他任务 } } return results; } /** * 分割查询范围 */ private List<RangeTask> splitRange(K startKey, K endKey, int numSplits) { List<RangeTask> tasks = new ArrayList<>(); // 1. 找到范围内的所有叶子节点 List<LeafNode<K, V>> leafNodes = getLeafNodesInRange(startKey, endKey); // 2. 计算每个任务应该处理的节点数 int nodesPerTask = Math.max(1, leafNodes.size() / numSplits); // 3. 创建任务 for (int i = 0; i < leafNodes.size(); i += nodesPerTask) { int endIndex = Math.min(i + nodesPerTask, leafNodes.size()); List<LeafNode<K, V>> taskNodes = leafNodes.subList(i, endIndex); K taskStartKey = taskNodes.get(0).keys.get(0); K taskEndKey = taskNodes.get(taskNodes.size() - 1) .keys.get(taskNodes.get(taskNodes.size() - 1).size() - 1); tasks.add(new RangeTask(taskStartKey, taskEndKey, taskNodes)); } return tasks; } private static class RangeTask { K startKey; K endKey; List<LeafNode<K, V>> nodes; RangeTask(K startKey, K endKey, List<LeafNode<K, V>> nodes) { this.startKey = startKey; this.endKey = endKey; this.nodes = nodes; } } }
3. 缓存优化策略
java
复制
下载
public class CachedBPlusTree<K extends Comparable<K>, V> extends BPlusTree<K, V> { // LRU缓存，缓存最近访问的节点 private LinkedHashMap<K, CacheEntry> cache; private final int cacheSize; public CachedBPlusTree(int degree, int cacheSize) { super(degree); this.cacheSize = cacheSize; this.cache = new LinkedHashMap<K, CacheEntry>( cacheSize, 0.75f, true) { @Override protected boolean removeEldestEntry( Map.Entry<K, CacheEntry> eldest) { return size() > cacheSize; } }; } @Override public V get(K key) { // 1. 检查缓存 CacheEntry entry = cache.get(key); if (entry != null) { return entry.value; } // 2. 从磁盘读取 V value = super.get(key); // 3. 放入缓存 if (value != null) { cache.put(key, new CacheEntry(value, System.currentTimeMillis())); } return value; } @Override public List<V> rangeQuery(K startKey, K endKey) { List<V> results = new ArrayList<>(); // 1. 预热缓存：预先加载范围内的部分数据 preloadCache(startKey, endKey); // 2. 执行范围查询，优先使用缓存 LeafNode<K, V> currentNode = findLeafNode(startKey); while (currentNode != null) { for (int i = 0; i < currentNode.size(); i++) { K currentKey = currentNode.keys.get(i); if (currentKey.compareTo(endKey) > 0) { return results; } // 检查缓存 CacheEntry cached = cache.get(currentKey); if (cached != null) { results.add(cached.value); } else { V value = currentNode.values.get(i); results.add(value); // 放入缓存 cache.put(currentKey, new CacheEntry(value, System.currentTimeMillis())); } } currentNode = currentNode.next; } return results; } /** * 缓存预热 */ private void preloadCache(K startKey, K endKey) { // 采样范围内的部分key进行预热 List<K> sampleKeys = sampleKeysInRange(startKey, endKey, 100); for (K key : sampleKeys) { V value = super.get(key); if (value != null) { cache.put(key, new CacheEntry(value, System.currentTimeMillis())); } } } private static class CacheEntry { V value; long timestamp; CacheEntry(V value, long timestamp) { this.value = value; this.timestamp = timestamp; } } }
五、性能优化策略
1. 批量插入优化
java
复制
下载
public class OptimizedBPlusTree<K extends Comparable<K>, V> extends BPlusTree<K, V> { /** * 批量插入优化 */ public void bulkInsert(List<Pair<K, V>> data) { if (data.isEmpty()) return; // 1. 按key排序 data.sort(Comparator.comparing(Pair::getKey)); // 2. 批量构建叶子节点 List<LeafNode<K, V>> leafNodes = buildLeafNodesInBatch(data); // 3. 批量构建索引 buildIndexInBatch(leafNodes); // 4. 更新根节点 updateRootFromLeaves(leafNodes); } /** * 批量构建叶子节点 */ private List<LeafNode<K, V>> buildLeafNodesInBatch(List<Pair<K, V>> data) { List<LeafNode<K, V>> leafNodes = new ArrayList<>(); LeafNode<K, V> currentLeaf = new LeafNode<>(degree); for (Pair<K, V> entry : data) { currentLeaf.keys.add(entry.getKey()); currentLeaf.values.add(entry.getValue()); if (currentLeaf.isFull()) { leafNodes.add(currentLeaf); currentLeaf = new LeafNode<>(degree); } } if (!currentLeaf.keys.isEmpty()) { leafNodes.add(currentLeaf); } // 连接叶子节点链表 for (int i = 0; i < leafNodes.size() - 1; i++) { leafNodes.get(i).next = leafNodes.get(i + 1); leafNodes.get(i + 1).prev = leafNodes.get(i); } return leafNodes; } /** * 批量构建索引（自底向上） */ private void buildIndexInBatch(List<LeafNode<K, V>> leafNodes) { List<InternalNode<K, V>> currentLevel = new ArrayList<>(); // 第一层：叶子节点的父节点 for (int i = 0; i < leafNodes.size(); i += degree) { InternalNode<K, V> parent = new InternalNode<>(degree); int end = Math.min(i + degree, leafNodes.size()); for (int j = i; j < end; j++) { LeafNode<K, V> leaf = leafNodes.get(j); parent.children.add(leaf); leaf.parent = parent; if (j > i) { parent.keys.add(leaf.keys.get(0)); } } currentLevel.add(parent); } // 递归构建更高层 while (currentLevel.size() > 1) { currentLevel = buildNextLevel(currentLevel); } // 更新根节点 if (!currentLevel.isEmpty()) { root = currentLevel.get(0); } } }
2. 并发控制
java
复制
下载
public class ConcurrentBPlusTree<K extends Comparable<K>, V> extends BPlusTree<K, V> { private final ReadWriteLock globalLock = new ReentrantReadWriteLock(); private final Map<BPlusTreeNode<K, V>, ReadWriteLock> nodeLocks = new ConcurrentHashMap<>(); /** * 细粒度并发插入 */ @Override public void insert(K key, V value) { // 1. 查找插入位置（读锁） globalLock.readLock().lock(); try { LeafNode<K, V> leaf = findLeafNode(key); lockNode(leaf, false); // 写锁叶子节点 // 2. 插入到叶子节点 if (!leaf.isFull()) { insertIntoLeaf(leaf, key, value); unlockNode(leaf); return; } // 3. 需要分裂，获取父节点锁 lockNode(leaf.parent, false); // 4. 执行分裂（可能需要递归向上） splitAndInsert(leaf, key, value); unlockNode(leaf.parent); unlockNode(leaf); } finally { globalLock.readLock().unlock(); } } /** * 乐观并发范围查询 */ public List<V> optimisticRangeQuery(K startKey, K endKey) { List<V> results = new ArrayList<>(); int retries = 3; while (retries-- > 0) { try { // 1. 记录版本号（或修改时间） long startVersion = getTreeVersion(); // 2. 执行范围查询 results = doRangeQuery(startKey, endKey); // 3. 验证版本是否变化 long endVersion = getTreeVersion(); if (startVersion == endVersion) { return results; // 没有并发修改，结果有效 } // 4. 版本变化，重试 results.clear(); } catch (ConcurrentModificationException e) { // 重试 } } // 重试失败，使用悲观锁 return pessimisticRangeQuery(startKey, endKey); } private void lockNode(BPlusTreeNode<K, V> node, boolean readOnly) { ReadWriteLock lock = nodeLocks.computeIfAbsent(node, n -> new ReentrantReadWriteLock()); if (readOnly) { lock.readLock().lock(); } else { lock.writeLock().lock(); } } private void unlockNode(BPlusTreeNode<K, V> node) { ReadWriteLock lock = nodeLocks.get(node); if (lock != null) { if (lock.writeLock().isHeldByCurrentThread()) { lock.writeLock().unlock(); } else { lock.readLock().unlock(); } } } }
篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc
需要全套面试笔记及答案
【点击此处即可/免费获取】
六、应用场景与配置建议
1. 数据库索引配置
sql
复制
下载
-- MySQL InnoDB B+树索引配置示例 CREATE TABLE users ( id INT PRIMARY KEY, name VARCHAR(100), email VARCHAR(100), created_at TIMESTAMP, INDEX idx_name (name), INDEX idx_email (email) ) ENGINE=InnoDB -- B+树相关参数 ROW_FORMAT=DYNAMIC -- 行格式 KEY_BLOCK_SIZE=16 -- 索引页大小（KB） -- InnoDB参数 innodb_page_size=16K -- 页大小 innodb_buffer_pool_size=1G -- 缓冲池大小 innodb_purge_threads=4 -- 清理线程
2. 文件系统实现
java
复制
下载
// 基于B+树的简单文件系统 public class BPlusTreeFileSystem { private BPlusTree<String, FileMetadata> index; // 文件名->文件元数据 private BlockManager blockManager; // 块管理器 /** * 范围查询文件（按文件名排序） */ public List<FileMetadata> listFiles(String prefix) { // 使用B+树的范围查询特性 return index.rangeQuery(prefix, prefix + Character.MAX_VALUE); } /** * 分页查询优化 */ public PageResult<FileMetadata> listFilesPaged( String prefix, int page, int pageSize) { // 1. 找到起始位置 LeafNode<String, FileMetadata> startNode = index.findLeafNode(prefix); // 2. 使用游标遍历，避免全量读取 Cursor cursor = new Cursor(startNode, prefix); // 3. 读取指定页的数据 List<FileMetadata> pageData = new ArrayList<>(); for (int i = 0; i < pageSize && cursor.hasNext(); i++) { pageData.add(cursor.next()); } // 4. 记录下一次的起始位置 String nextStartKey = cursor.hasNext() ? cursor.peek().getKey() : null; return new PageResult<>(pageData, page, pageSize, nextStartKey); } }
3. 性能测试与监控
java
复制
下载
public class BPlusTreeBenchmark { public void benchmark() { int[] degrees = {16, 32, 64, 128}; int[] dataSizes = {1000, 10000, 100000, 1000000}; for (int degree : degrees) { for (int size : dataSizes) { // 测试插入性能 testInsertPerformance(degree, size); // 测试查询性能 testQueryPerformance(degree, size); // 测试范围查询性能 testRangeQueryPerformance(degree, size); // 测试分裂合并开销 testSplitMergeOverhead(degree, size); } } } private void testRangeQueryPerformance(int degree, int size) { BPlusTree<Integer, String> tree = new BPlusTree<>(degree); // 插入测试数据 for (int i = 0; i < size; i++) { tree.insert(i, "value" + i); } // 测试不同范围大小的查询 int[] rangeSizes = {10, 100, 1000, 10000}; for (int rangeSize : rangeSizes) { long startTime = System.nanoTime(); for (int i = 0; i < 1000; i++) { int start = i % (size - rangeSize); int end = start + rangeSize; tree.rangeQuery(start, end); } long duration = System.nanoTime() - startTime; System.out.printf("Degree=%d, Size=%d, Range=%d: %.2f ops/ms\n", degree, size, rangeSize, 1000.0 / (duration / 1_000_000.0)); } } }
七、总结
B+树的核心优势：
- 分裂合并策略：
- 分裂：当节点满时，将其分成两个节点并提升中间key
- 合并：当节点元素过少时，与兄弟节点合并或借用元素
- 保证树的高度平衡和空间利用率
- 范围查询优化：
- 叶子节点链表支持顺序遍历
- 缓存和预取减少磁盘IO
- 并行查询充分利用多核CPU
- 游标支持分页查询
- 性能优化技术：
- 批量操作减少树的重组
- 细粒度并发控制
- 缓存热点数据
- 自适应分裂阈值
实际应用建议：
- 选择合适的度（degree）：
- 内存数据库：较小的度（16-64）
- 磁盘数据库：较大的度（64-256），匹配页大小
- SSD：中等度（32-128）
- 监控与调优：
- 监控树的高度和节点填充率
- 定期重组优化空间利用率
- 根据负载模式调整缓存策略
- 现代改进：
- 考虑B*树（减少分裂频率）
- 支持SSD的B+树变种
- 结合LSM树处理写入密集型负载
B+树作为经典的数据结构，通过精心设计的分裂合并策略和范围查询优化，在数据库索引和文件系统中仍然发挥着重要作用。
