B+ Tree
A B+ tree is a variant of the B-tree that stores all data in the leaf nodes and maintains a linked list between these leaves. This structure is optimized for systems that read sequential data and is commonly used in databases and file systems.
B+ Tree Properties:
- All leaves are at the same level
- Internal nodes only store keys for routing, not data
- All data records are stored in leaf nodes
- Leaf nodes are linked together in sequential order
- Each node (except root) must be at least half full
Advantages over B-Tree:
- Range queries are more efficient due to leaf-level linking
- Leaf nodes can store more entries as they don't store child pointers
- Better support for sequential access patterns
- More efficient space utilization for data storage
Time Complexity:
- Search: O(log n)
- Insert: O(log n)
- Delete: O(log n)
- Sequential Access: O(1) per element
Use the controls above to perform operations on the B+ tree. Notice how the tree maintains both its hierarchical structure and the sequential links between leaf nodes.