[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":86,"_73":87,"_35":88},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",92,"title","B-Tree","slug","dsa-cheatsheet-part-21-btree","excerpt","Visual guide to B-Tree: self-balancing tree for databases and file systems. Watch node splits and merges maintain balance.","# B-Tree\n\n## 📋 Quick Reference\n\n| Property | Value |\n|----------|-------|\n| **Type** | Self-balancing multi-way search tree |\n| **Search** | O(log n) |\n| **Insert** | O(log n) |\n| **Delete** | O(log n) |\n| **Disk Reads** | O(log_B n) where B = branching factor |\n| **Best For** | Database indexes, file systems, disk-based storage |\n\n**One-liner**: *Self-balancing tree optimized for systems that read/write large blocks of data, like databases and file systems.*\n\n---\n\n## 🎮 Interactive Visualizer\n\nWatch how B-Tree maintains balance through splits and merges:\n\n```visualizer-btree\nshowControls: true\nshowCode: true\n```\n\n**Try these operations:**\n1. Insert elements and watch node splits\n2. Observe how tree grows from root\n3. Search for elements (see path traversal)\n4. Notice all leaves at same depth\n\n---\n\n## 🔧 How It Works\n\n### B-Tree Properties (Order m)\n\n```\n1. Every node has at most m children\n2. Every non-leaf node (except root) has at least ⌈m/2⌉ children\n3. Root has at least 2 children (if not a leaf)\n4. All leaves appear at the same level\n5. A node with k children contains k-1 keys\n\nExample B-Tree of order 3 (2-3 tree):\n [17]\n / \\\n [8] [25, 32]\n / \\ / | \\\n [3,5] [12] [20] [27] [35,40]\n```\n\n### Node Structure\n\n```java\nclass BTreeNode, V> {\n K[] keys; // Keys stored in node\n V[] values; // Associated values\n BTreeNode[] children; // Child pointers\n int numKeys; // Current number of keys\n boolean isLeaf; // Is this a leaf node?\n}\n```\n\n### Search Operation\n\n```\nSearch for key 20 in tree:\n1. Start at root [17]\n2. 20 > 17 → go right child [25, 32]\n3. 20 < 25 → go left child [20]\n4. Found!\n\nTime: O(log n) comparisons × O(m) per node = O(m log n)\nWith m constant: O(log n)\n```\n\n### Insert with Split\n\n```\nInsert 15 into node [10, 12, 14] (order 4, max 3 keys):\n\nBefore split: [10, 12, 14, 15] ← overflow!\n ↓\nAfter split: [12] ← middle key goes up\n / \\\n [10] [14, 15]\n\nIf parent overflows → split propagates up (may create new root)\n```\n\n---\n\n## 📊 Complexity Analysis\n\n| Operation | Time | Disk I/O |\n|-----------|------|----------|\n| Search | O(log n) | O(log_B n) |\n| Insert | O(log n) | O(log_B n) |\n| Delete | O(log n) | O(log_B n) |\n| Range query | O(log n + k) | O(log_B n + k/B) |\n\n### Why B-Trees for Databases?\n\n```\nBinary tree depth for 1M records: log₂(1,000,000) ≈ 20 levels\nB-tree depth (order 100): log₁₀₀(1,000,000) ≈ 3 levels\n\nEach level = 1 disk read\nB-tree: 3 disk reads vs BST: 20 disk reads\n```\n\n---\n\n## 🔄 B-Tree vs B+ Tree\n\n| Feature | B-Tree | B+ Tree |\n|---------|--------|---------|\n| Data location | All nodes | Leaves only |\n| Leaf linking | No | Linked list |\n| Range queries | Slower | Faster (follow links) |\n| Space usage | Keys duplicate | Better utilization |\n| Used in | General | Most databases (MySQL, PostgreSQL) |\n\n### B+ Tree Structure\n\n```\nB+ Tree (keys in internal nodes are guides only):\n\n [30] ← internal nodes have keys only\n / \\\n [10,20] [40,50] ← internal nodes\n / | \\ / | \\\n[5,8][12,15][25,28][35,38][45,48][55,60] ← leaves have all data\n ↔ ↔ ↔ ↔ ↔ ← linked for range scan\n```\n\n---\n\n## ✅ When to Use B-Tree\n\n### Good Use Cases\n\n- **Database indexes** - optimized for disk access patterns\n- **File systems** - NTFS, HFS+, ext4 use B-trees\n- **Key-value stores** - efficient ordered storage\n- **Range queries** - find all keys between A and B\n- **Sorted data access** - in-order traversal\n\n### Avoid When\n\n- **All data fits in memory** - BST or hash table may be faster\n- **Only point queries** - hash table is O(1)\n- **Frequent updates, rare reads** - LSM tree may be better\n- **Small datasets** - overhead not worth it\n\n---\n\n## 🧩 Real-World Implementations\n\n### Database Indexes (SQL)\n\n```sql\n-- B-tree index (default in most databases)\nCREATE INDEX idx_users_email ON users(email);\n\n-- B-tree is used for:\nSELECT * FROM users WHERE email = 'test@example.com'; -- point lookup\nSELECT * FROM users WHERE email > 'a' AND email < 'm'; -- range query\nSELECT * FROM users ORDER BY email; -- sorted access\n\n-- Hash index (only point lookups)\nCREATE INDEX idx_users_id ON users USING HASH (id);\n```\n\n### Java TreeMap (Red-Black Tree, not B-Tree)\n\n```java\n// Java's TreeMap uses Red-Black tree (binary)\n// For B-tree in Java, use libraries like:\n// - Apache Commons BTree\n// - MapDB\n// - Chronicle Map\n\nTreeMap map = new TreeMap<>();\nmap.put(\"key\", 100);\n\n// Range operations (similar to B-tree benefits)\nSortedMap range = map.subMap(\"a\", \"m\");\n```\n\n### File System (conceptual)\n\n```\nDirectory structure as B-tree:\n [etc, home, var]\n / | \\\n[apt,dpkg] [user1,user2] [log,tmp]\n | | |\n [...] [docs,...] [...]\n\nEach node = disk block\nMinimize disk reads to find file\n```\n\n---\n\n## ⚠️ Common Pitfalls\n\n### 1. Confusing B-Tree Order Definitions\n\n```java\n// Different sources use different definitions!\n// \"Order m\" can mean:\n// - Maximum children per node = m (Knuth definition)\n// - Maximum keys per node = m\n// - Minimum keys per node = m\n\n// Always clarify which definition is being used\n```\n\n### 2. Wrong Data Structure Choice\n\n```java\n// ❌ Using B-tree for in-memory, point-only lookups\nBTree users = new BTree<>();\nusers.get(\"specific-id\"); // HashMap would be O(1)\n\n// ✅ Use B-tree when you need\n// - Range queries\n// - Sorted iteration\n// - Disk-based storage\n```\n\n### 3. Ignoring Node Size Optimization\n\n```java\n// B-tree node size should match disk block size\n// Typical disk block: 4KB or 8KB\n// Choose order m so node fits in one block\n\n// Too small m = more levels = more disk reads\n// Too large m = wasted space, slower node search\n```\n\n### 4. Not Considering B+ Tree for Databases\n\n```java\n// ❌ Standard B-tree for database with range queries\n// - Data scattered across all nodes\n// - Range scan requires tree traversal\n\n// ✅ B+ tree for databases\n// - All data in leaves\n// - Leaves linked for efficient range scans\n// - Internal nodes smaller (more fit in memory)\n```\n\n---\n\n## 🎤 Interview Tips\n\n**Q: Why are B-trees used in databases instead of binary search trees?**\n\n> B-trees are optimized for disk I/O. They have high branching factor (many children per node), which minimizes tree height and thus disk reads. A B-tree with order 100 might have depth 3 for millions of records, while a BST would need depth 20+.\n\n**Q: What's the difference between B-tree and B+ tree?**\n\n> In B-tree, data is stored in all nodes. In B+ tree, data is only in leaf nodes, and leaves are linked together. B+ trees are better for range queries and are used by most databases (MySQL InnoDB, PostgreSQL).\n\n**Q: How does B-tree maintain balance?**\n\n> B-trees grow from the root, not leaves. When a node overflows during insert, it splits and pushes the middle key up. If the root splits, a new root is created. This ensures all leaves stay at the same level.\n\n**Q: What is the minimum fill factor of a B-tree node?**\n\n> Non-root nodes must be at least half full. For order m B-tree, each node has at least ⌈m/2⌉ children (except root). This ensures good space utilization and bounds tree height.\n\n**Q: How do B-tree deletions work?**\n\n> If removing a key causes underflow (< minimum keys), the node borrows from a sibling or merges with a sibling. Merging may propagate up the tree, potentially reducing tree height.\n\n---\n\n## 📚 Series Navigation\n\n**Previous**: [Part 20: Bloom Filter](dsa-cheatsheet-part-20-bloom-filter)\n\n**Next**: [Part 22: Consistent Hashing](dsa-cheatsheet-part-22-consistent-hashing)\n\n---\n\n**Visualizer**: `BTreeVisualizer` from `@tomaszjarosz/react-visualizers`\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.773447Z","createdAt","2026-06-10T07:19:25.773664Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",5,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",4,"seriesOrder",21,"author",{"_31":55,"_99":57,"_100":101,"_102":103,"_104":-5,"_105":-5,"_106":-5,"_107":-5,"_108":-5},"category",{"_31":95,"_73":59,"_35":96,"_76":97,"_98":-5},"tags",[79,80,81,82],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Interactive Data Structures & Algorithms","dsa-visualized-cheatsheet","description","A concise, visual reference for essential data structures and algorithms. Each article features an interactive visualizer showing how the structure/algorithm works step-by-step, along with complexity analysis, use cases, and quick reference code. Perfect for interview prep, quick review, or learning by visualization.","isActive",{"_31":92,"_73":93,"_35":94},{"_31":89,"_73":90,"_35":91},{"_31":86,"_73":87,"_35":88},{"_31":83,"_73":84,"_35":85},304,"Index","index",305,"Disk-optimized","disk-optimized",299,"Database","database",303,"B-tree","b-tree",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]