Watch how B+ Tree stores data in leaves with linked list
B+ Tree is a variant of B-Tree where all data is stored in leaf nodes, and leaves are linked together. This structure is ideal for range queries and is the foundation of database indexes like MySQL InnoDB.
| Feature | B树 | B+树 |
|---|---|---|
| Data storage | All nodes | Leaf nodes only |
| Leaf linkage | None | Linked list |
| Range query | Complex | Efficient |
| Operation | Time | Description |
|---|---|---|
| Search | O(log n) | Must reach leaf node |
| Insert | O(log n) | Insert in leaf, may split |
| Range Query | O(log n + k) | k = number of results |
| Delete | O(log n) | May trigger merge |
Space Complexity: O(n)
B+ Tree typically has higher fanout than B-Tree, resulting in lower tree height
Primary key uses clustered B+ Tree index, secondary indexes point to primary key
Default index type is B-Tree (actually B+ Tree implementation)
NTFS, ReiserFS, XFS use B+ Tree for directory structure
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; }
}