B-Tree Data Structure with Animation - Interactive Learning
Master B-Tree - DSA Learning Platform 🌲 Master B-Tree Self-Balancing Database Indexing Learn B-Tree operations with interactive animations and node splitting visualization 📖 Understanding B-Tree Data Structure Introduction Properties Operations Node Splitting Applications What is a B-Tree? A B-Tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. Unlike binary trees, B-Tree nodes can have multiple keys and children. B-Trees are optimized for systems that read and write large blocks of data, making them ideal for databases and file systems. They minimize disk I/O operations by keeping the tree height low. The "B" in B-Tree could stand for Balanced, Broad, or the creators' names (Bayer and McCreight). All leaf nodes are at the same level, ensuring perfect balance. Minimum Degree (t) t ≥ 2 (defines min/max keys) 🔑 Key Characteristics Self-balancing search tree Nodes can have multiple keys All leaves at same level Optimized for disk access Logarithmic time operations Used in databases & file systems 📊 Comparison with BST BST: 1 key, 2 children per node B-Tree: Multiple keys & children B-Tree has lower height Fewer disk reads needed B-Tree Properties For a B-Tree with minimum degree t: Keys Per Node Min: t-1 | Max: 2t-1 Children Per Node Min: t | Max: 2t Root Exception Root can have min 1 key Example: t = 3 Keys per node: 2 to 5 Children per node: 3 to 6 Root: 1 to 5 keys 📍 B-Tree Structure (t=3) [30 | 60] ← Root (2 keys, 3 children) / | \ [10|20] [40|50] [70|80|90] Each internal node: t-1 to 2t-1 keys Each internal node: t to 2t children All leaves at same level B-Tree Operations 🔍 Search Operation Start at root node Search keys in current node If found, return success If key < keys[i], go to child[i] Repeat until found or leaf reached 📥 Insert Operation Find appropriate leaf node Insert key in sorted order If node overflows (> 2t-1 keys): • Split node into two • Move middle key to parent Propagate split upward if needed 🗑️ Delete Operation Find the key to delete If in leaf: remove directly If in internal: replace with predecessor/successor Handle underflow by borrowing or merging ⏱️ Time Complexity Search: O(log n) Insert: O(log n) Delete: O(log n) Space: O(n) 💾 Disk Access Search: O(log_t n) disk reads Height = O(log_t n) Larger t → fewer levels Optimized for block storage Node Splitting in B-Tree When a node becomes full (has 2t-1 keys), it must be split before inserting a new key. This is the core operation that keeps B-Trees balanced. Split Process (t=3, max 5 keys) Node has 5 keys: [10, 20, 30, 40, 50] Middle key (30) moves to parent Left node gets: [10, 20] Right node gets: [40, 50] Parent now has new child pointer Root Split When the root splits, a new root is created with the middle key. This is the only way the tree height increases. 📍 Split Animation Before (overflow): [10|20|30|40|50] ← Full node! Splitting... [10|20] | 30 | [...
Subject: Data Structures with Animation | Chapter: B-Tree Data Structure