搭建网站需要什么语言_中山市企业网站seo哪里好_aso优化app推广_学技术的培训学校

什么是B+树

B+ 树是一种 自平衡的多叉搜索树，常用于 数据库索引（如 MySQL）和文件系统。它是 B-树（B-tree）的变种，具有更高的磁盘读写效率和范围查询性能。
特点：
1 所有数据存储在叶子节点，非叶子节点仅存储索引键，不存数据。
2 叶子节点之间有指针相连，支持高效的区间查询。
3 多路平衡树（非二叉树），每个节点最多有 M 个子节点（M 阶 B+ 树）。
4 根节点到叶子节点的路径长度相同，保持树的平衡性。
5 非叶子节点不会存储数据，只作为索引，提高内存利用率。

B+树的实现

package com.dataStract;import java.util.*;public class BPlusTree<K extends Comparable<K>, V> {private static final int ORDER = 4; // B+树的阶数 (每个节点最多有 ORDER 个子节点)private Node<K, V> root;public BPlusTree() {root = new LeafNode<>();}// 插入键值对public void insert(K key, V value) {root.insert(key, value, this);}// 查找public V search(K key) {return root.search(key);}// 遍历public void traverse() {root.traverse();}// B+树的节点类型（抽象类）abstract static class Node<K extends Comparable<K>, V> {List<K> keys;Node() {keys = new ArrayList<>();}abstract void insert(K key, V value, BPlusTree<K, V> tree);abstract V search(K key);abstract void traverse();}// 内部节点static class InternalNode<K extends Comparable<K>, V> extends Node<K, V> {List<Node<K, V>> children;InternalNode() {children = new ArrayList<>();}@Overridevoid insert(K key, V value, BPlusTree<K, V> tree) {// 找到合适的子节点插入int idx = Collections.binarySearch(keys, key);if (idx < 0) idx = -idx - 1;children.get(idx).insert(key, value, tree);// 处理分裂if (children.size() > ORDER) {split(tree);}}private void split(BPlusTree<K, V> tree) {int midIndex = keys.size() / 2;K midKey = keys.get(midIndex);InternalNode<K, V> sibling = new InternalNode<>();sibling.keys.addAll(keys.subList(midIndex + 1, keys.size()));sibling.children.addAll(children.subList(midIndex + 1, children.size()));keys.subList(midIndex, keys.size()).clear();children.subList(midIndex + 1, children.size()).clear();if (this == tree.root) {InternalNode<K, V> newRoot = new InternalNode<>();newRoot.keys.add(midKey);newRoot.children.add(this);newRoot.children.add(sibling);tree.root = newRoot;}}@OverrideV search(K key) {int idx = Collections.binarySearch(keys, key);if (idx < 0) idx = -idx - 1;return children.get(idx).search(key);}@Overridevoid traverse() {for (Node<K, V> child : children) {child.traverse();}}}// 叶子节点static class LeafNode<K extends Comparable<K>, V> extends Node<K, V> {List<V> values;LeafNode<K, V> next;LeafNode() {values = new ArrayList<>();}@Overridevoid insert(K key, V value, BPlusTree<K, V> tree) {int idx = Collections.binarySearch(keys, key);if (idx >= 0) {values.set(idx, value); // 更新已有值} else {idx = -idx - 1;keys.add(idx, key);values.add(idx, value);}if (keys.size() > ORDER - 1) {split(tree);}}private void split(BPlusTree<K, V> tree) {int midIndex = keys.size() / 2;LeafNode<K, V> sibling = new LeafNode<>();sibling.keys.addAll(keys.subList(midIndex, keys.size()));sibling.values.addAll(values.subList(midIndex, values.size()));keys.subList(midIndex, keys.size()).clear();values.subList(midIndex, values.size()).clear();sibling.next = this.next;this.next = sibling;if (this == tree.root) {InternalNode<K, V> newRoot = new InternalNode<>();newRoot.keys.add(sibling.keys.get(0));newRoot.children.add(this);newRoot.children.add(sibling);tree.root = newRoot;} else {((InternalNode<K, V>) tree.root).children.add(sibling);}}@OverrideV search(K key) {int idx = Collections.binarySearch(keys, key);if (idx >= 0) return values.get(idx);return null;}@Overridevoid traverse() {System.out.println(keys + " -> " + values);if (next != null) next.traverse();}}public static void main(String[] args) {BPlusTree<Integer, String> tree = new BPlusTree<>();tree.insert(10, "A");tree.insert(20, "B");tree.insert(30, "C");tree.insert(40, "D");tree.insert(50, "E");tree.insert(60, "F");tree.traverse();System.out.println("Search 30: " + tree.search(30));System.out.println("Search 70: " + tree.search(70)); // 不存在}
}

(1) 插入
1 插入时，数据始终存储在叶子节点。
2 如果叶子节点满了，就需要分裂。
3 分裂后，非叶子节点需要插入新的索引键，可能导致递归分裂。
4 叶子节点分裂后，索引节点调整。
5 如果索引节点溢出，则需要递归分裂到更高层。
(2) B+ 树的查询
1 B+ 树查询路径始终从根节点到叶子节点（O(log N) 复杂度）。
2 非叶子节点只作为索引，不存数据，每次查询都要到叶子节点获取数据。
3 支持范围查询（因为叶子节点有指针连接）。

B+树叶子结点和非叶子节点分裂

叶子节点分裂触发条件

1 叶子节点存储满了（即存储的索引键值数量超过设定的上限），需要插入新的数据。
2 MySQL 的 InnoDB 存储引擎默认 每个数据页 16KB，叶子节点的键值填满后，新的键值无法插入，触发分裂。
分裂步骤：
叶子节点分裂步骤
1.创建新的叶子节点（右兄弟）。
2.数据拆分：
把一半的键值对 移动到新叶子节点（右节点）。
3.更新双向链表指针：
叶子节点存储着前后节点的指针，需要更新。
4.父节点插入新的索引键：
把 新叶子节点的最小键 插入 父节点，让父节点能够正确索引两个子节点。

非叶子节点（内部节点）分裂

触发条件：
1.叶子节点分裂后，会向 父节点插入一个新的索引键。
2.如果父节点的存储容量超出上限，则 非叶子节点也会分裂。
非叶子节点的分裂步骤:
1.创建新的内部节点（右兄弟）。
2.把父节点的一半键值移动到新内部节点。
3.修改原父节点的指针，使其指向新的内部节点。
4.把分裂点的索引键插入更上层的父节点。
5.如果根节点分裂，则创建新的根节点，使 B+树的高度增加。

叶子节点删除数据的影响

当 叶子节点中的某些数据被删除，其影响取决于当前叶子节点的剩余数据量是否仍然符合 B+ 树的约束条件。
1.删除后，叶子节点仍然超过最小容量（无影响 ）
2.直接删除数据，不影响树结构，不需要任何调整。
3.删除后，叶子节点的数据量低于最小容量（触发合并或借用操作 ）
4.如果兄弟叶子节点有足够多的数据，可以 从兄弟节点借数据（旋转）。
5.如果兄弟叶子节点数据也不足，则 合并叶子节点，并调整父节点的索引键。