B+树可视化

特性	B树	B+树
数据存储	所有节点	仅叶子节点
叶子链接	无	链表连接
范围查询	复杂	高效

操作	时间	说明
查找	O(log n)	必须到达叶子节点
插入	O(log n)	在叶子插入，可能分裂
范围查询	O(log n + k)	k = 结果数量
删除	O(log n)	可能触发合并

代码实现

class BPlusTreeNode:
    def __init__(self, leaf=True):
        self.keys = []
        self.children = []  # For internal: child nodes; For leaf: data
        self.leaf = leaf
        self.next = None  # Link to next leaf

class BPlusTree:
    def __init__(self, order=4):
        self.root = BPlusTreeNode()
        self.order = order
    
    def search(self, key):
        """Search must reach leaf node"""
        node = self.root
        while not node.leaf:
            i = 0
            while i < len(node.keys) and key >= node.keys[i]:
                i += 1
            node = node.children[i]
        
        # Search in leaf
        for i, k in enumerate(node.keys):
            if k == key:
                return node.children[i]  # Return data
        return None
    
    def range_query(self, start, end):
        """Efficient range query using leaf links"""
        # Find start leaf
        node = self.root
        while not node.leaf:
            i = 0
            while i < len(node.keys) and start >= node.keys[i]:
                i += 1
            node = node.children[i]
        
        # Traverse leaves
        results = []
        while node:
            for i, key in enumerate(node.keys):
                if start <= key <= end:
                    results.append((key, node.children[i]))
                elif key > end:
                    return results
            node = node.next  # Follow leaf link
        return results

# Usage
tree = BPlusTree(order=4)
# Range query example
results = tree.range_query(10, 50)

import java.util.*;

public class BPlusTree {
    private BPlusNode root;
    private int order;
    
    public BPlusTree(int order) {
        this.order = order;
        this.root = new BPlusNode(true);
    }
    
    public Object search(int key) {
        BPlusNode node = root;
        while (!node.leaf) {
            int i = 0;
            while (i < node.keys.size() && key >= node.keys.get(i)) {
                i++;
            }
            node = node.children.get(i);
        }
        
        for (int i = 0; i < node.keys.size(); i++) {
            if (node.keys.get(i) == key) {
                return node.data.get(i);
            }
        }
        return null;
    }
    
    public List<Object> rangeQuery(int start, int end) {
        List<Object> results = new ArrayList<>();
        BPlusNode node = findLeaf(start);
        
        while (node != null) {
            for (int i = 0; i < node.keys.size(); i++) {
                int key = node.keys.get(i);
                if (key >= start && key <= end) {
                    results.add(node.data.get(i));
                } else if (key > end) {
                    return results;
                }
            }
            node = node.next;
        }
        return results;
    }
}

class BPlusNode {
    List<Integer> keys = new ArrayList<>();
    List<BPlusNode> children = new ArrayList<>();
    List<Object> data = new ArrayList<>();
    boolean leaf;
    BPlusNode next;  // Leaf link
    
    BPlusNode(boolean leaf) { this.leaf = leaf; }
}

B+树 vs B树

关键特性

MySQL InnoDB 索引

PostgreSQL 索引

文件系统

代码实现