[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_33":98,"_75":99,"_37":100},"articles",{"_11":12,"_13":14,"_15":16,"_17":18,"_19":20,"_21":22,"_23":24,"_25":24,"_26":16,"_27":28},"content",[31,32],"pageable",{"_29":22,"_30":20},"totalElements",2,"totalPages",1,"size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_33":114,"_35":115,"_37":116,"_39":117,"_11":118,"_42":-5,"_43":24,"_44":28,"_45":46,"_47":119,"_49":120,"_51":52,"_53":121,"_55":121,"_56":57,"_58":59,"_60":61,"_62":121,"_63":64,"_65":122,"_67":123,"_69":124,"_71":125,"_73":126},{"_33":34,"_35":36,"_37":38,"_39":40,"_11":41,"_42":-5,"_43":24,"_44":28,"_45":46,"_47":48,"_49":50,"_51":52,"_53":54,"_55":54,"_56":57,"_58":59,"_60":61,"_62":54,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72,"_73":74},"id",90,"title","SQL Joins","slug","dsa-cheatsheet-part-19-sql-joins","excerpt","Visual guide to SQL JOINs: INNER, LEFT, RIGHT, FULL. See exactly which rows match and which don't.","# SQL Joins\n\n## 📋 Quick Reference\n\n| Join Type | Returns | Nulls For |\n|-----------|---------|-----------|\n| INNER JOIN | Matching rows only | N/A |\n| LEFT JOIN | All left + matching right | Non-matching right |\n| RIGHT JOIN | All right + matching left | Non-matching left |\n| FULL JOIN | All rows from both | Non-matching from either |\n| CROSS JOIN | Cartesian product | N/A |\n\n**One-liner**: *SQL joins combine rows from multiple tables based on related columns.*\n\n---\n\n## 🎮 Interactive Visualizer\n\nWatch how different joins combine data from two tables:\n\n```visualizer-sqljoin\nshowControls: true\nshowCode: true\n```\n\n**Try these operations:**\n1. See INNER JOIN - only matching rows\n2. Watch LEFT JOIN - all from left, nulls for unmatched right\n3. Compare with RIGHT JOIN - all from right\n4. Try FULL JOIN - all rows, nulls on both sides\n\n---\n\n## 🔧 Join Implementations\n\n### INNER JOIN\n\n```sql\n-- Only rows that match in BOTH tables\nSELECT employees.name, departments.name\nFROM employees\nINNER JOIN departments\nON employees.dept_id = departments.id;\n\n-- Equivalent older syntax\nSELECT e.name, d.name\nFROM employees e, departments d\nWHERE e.dept_id = d.id;\n```\n\n```\nemployees departments Result\n┌────┬───────┬────┐ ┌────┬─────────┐ ┌───────┬─────────┐\n│ id │ name │dept│ │ id │ name │ │ e.name│ d.name │\n├────┼───────┼────┤ ├────┼─────────┤ ├───────┼─────────┤\n│ 1 │ Alice │ 1 │ │ 1 │ Sales │ → │ Alice │ Sales │\n│ 2 │ Bob │ 2 │ │ 2 │ IT │ │ Bob │ IT │\n│ 3 │ Carol │ 3 │ │ 4 │ HR │ │ Carol │ Marketing│\n│ 4 │ Dave │ 5 │ └────┴─────────┘ └───────┴─────────┘\n└────┴───────┴────┘ Dave excluded (dept 5 not found)\n HR excluded (no employees)\n```\n\n### LEFT JOIN (LEFT OUTER JOIN)\n\n```sql\n-- All rows from LEFT table, matching from RIGHT\n-- NULL for non-matching right rows\nSELECT e.name, d.name\nFROM employees e\nLEFT JOIN departments d\nON e.dept_id = d.id;\n```\n\n```\nResult:\n┌───────┬─────────┐\n│ e.name│ d.name │\n├───────┼─────────┤\n│ Alice │ Sales │\n│ Bob │ IT │\n│ Carol │ Marketing│\n│ Dave │ NULL │ ← Dave included, no matching dept\n└───────┴─────────┘\n```\n\n### RIGHT JOIN (RIGHT OUTER JOIN)\n\n```sql\n-- All rows from RIGHT table, matching from LEFT\n-- NULL for non-matching left rows\nSELECT e.name, d.name\nFROM employees e\nRIGHT JOIN departments d\nON e.dept_id = d.id;\n```\n\n```\nResult:\n┌───────┬─────────┐\n│ e.name│ d.name │\n├───────┼─────────┤\n│ Alice │ Sales │\n│ Bob │ IT │\n│ Carol │ Marketing│\n│ NULL │ HR │ ← HR included, no matching employee\n└───────┴─────────┘\n```\n\n### FULL JOIN (FULL OUTER JOIN)\n\n```sql\n-- All rows from BOTH tables\n-- NULL for non-matching on either side\nSELECT e.name, d.name\nFROM employees e\nFULL JOIN departments d\nON e.dept_id = d.id;\n```\n\n```\nResult:\n┌───────┬─────────┐\n│ e.name│ d.name │\n├───────┼─────────┤\n│ Alice │ Sales │\n│ Bob │ IT │\n│ Carol │ Marketing│\n│ Dave │ NULL │ ← Unmatched left\n│ NULL │ HR │ ← Unmatched right\n└───────┴─────────┘\n```\n\n### CROSS JOIN\n\n```sql\n-- Cartesian product: every row with every row\nSELECT e.name, d.name\nFROM employees e\nCROSS JOIN departments d;\n-- Or: FROM employees e, departments d (no WHERE)\n```\n\n```\nResult (4 employees × 3 departments = 12 rows):\n┌───────┬─────────┐\n│ e.name│ d.name │\n├───────┼─────────┤\n│ Alice │ Sales │\n│ Alice │ IT │\n│ Alice │ HR │\n│ Bob │ Sales │\n│ Bob │ IT │\n│ ... │ ... │\n└───────┴─────────┘\n```\n\n---\n\n## 📊 Join Complexity\n\n| Scenario | Complexity | Notes |\n|----------|------------|-------|\n| Nested Loop | O(n × m) | Simple, for small tables |\n| Hash Join | O(n + m) | Build hash table, probe |\n| Merge Join | O(n log n + m log m) | Sort both, merge |\n\nThe query optimizer chooses based on:\n- Table sizes\n- Available indexes\n- Statistics\n\n---\n\n## ✅ When to Use Each Join\n\n### INNER JOIN\n\n- **Default choice** when you only want matching data\n- **Foreign key relationships** that must exist\n- **Filtering** - exclude rows without matches\n\n### LEFT JOIN\n\n- **Optional relationships** - show all from main table\n- **Finding orphans** - WHERE right.id IS NULL\n- **Aggregations** - include items with zero count\n\n### RIGHT JOIN\n\n- **Rarely used** - usually rewrite as LEFT JOIN\n- **Legacy queries** - maintaining existing code\n- **Specific ordering** - when right table is primary\n\n### FULL JOIN\n\n- **Reconciliation** - find mismatches between tables\n- **Merging data** - combine from both sources\n- **Finding orphans on both sides**\n\n---\n\n## 🧩 Common Patterns\n\n### Finding Orphan Records\n\n```sql\n-- Employees without a department\nSELECT e.*\nFROM employees e\nLEFT JOIN departments d ON e.dept_id = d.id\nWHERE d.id IS NULL;\n\n-- Departments without employees\nSELECT d.*\nFROM departments d\nLEFT JOIN employees e ON e.dept_id = d.id\nWHERE e.id IS NULL;\n```\n\n### Counting with Zero\n\n```sql\n-- Include departments with zero employees\nSELECT d.name, COUNT(e.id) as emp_count\nFROM departments d\nLEFT JOIN employees e ON e.dept_id = d.id\nGROUP BY d.id, d.name;\n\n-- Without LEFT JOIN, empty departments excluded!\n```\n\n### Self Join\n\n```sql\n-- Employees and their managers\nSELECT e.name as employee, m.name as manager\nFROM employees e\nLEFT JOIN employees m ON e.manager_id = m.id;\n```\n\n### Multiple Joins\n\n```sql\nSELECT e.name, d.name, l.city\nFROM employees e\nJOIN departments d ON e.dept_id = d.id\nJOIN locations l ON d.location_id = l.id;\n\n-- Order matters for LEFT/RIGHT\nSELECT e.name, d.name, p.name\nFROM employees e\nLEFT JOIN departments d ON e.dept_id = d.id\nLEFT JOIN projects p ON e.id = p.lead_id;\n```\n\n---\n\n## ⚠️ Common Pitfalls\n\n### 1. Forgetting NULL in LEFT/RIGHT JOIN\n\n```sql\n-- ❌ This filters out the NULL rows from LEFT JOIN!\nSELECT e.name, d.name\nFROM employees e\nLEFT JOIN departments d ON e.dept_id = d.id\nWHERE d.status = 'active'; -- NULL status excluded!\n\n-- ✅ Handle NULL explicitly\nWHERE d.status = 'active' OR d.id IS NULL;\n-- Or move to JOIN condition\nLEFT JOIN departments d ON e.dept_id = d.id AND d.status = 'active';\n```\n\n### 2. Accidental Cross Join\n\n```sql\n-- ❌ Missing ON clause creates cross join!\nSELECT e.name, d.name\nFROM employees e\nJOIN departments d; -- Returns n × m rows!\n\n-- ✅ Always specify join condition\nJOIN departments d ON e.dept_id = d.id;\n```\n\n### 3. Ambiguous Columns\n\n```sql\n-- ❌ Both tables have 'id' column\nSELECT id, name -- Which id? Which name?\nFROM employees\nJOIN departments ON dept_id = departments.id;\n\n-- ✅ Use table aliases\nSELECT e.id, e.name, d.name as dept_name\nFROM employees e\nJOIN departments d ON e.dept_id = d.id;\n```\n\n### 4. Joining on Non-Indexed Columns\n\n```sql\n-- ❌ Slow without index\nSELECT * FROM orders o\nJOIN customers c ON o.customer_email = c.email;\n\n-- ✅ Join on indexed columns (usually IDs)\nSELECT * FROM orders o\nJOIN customers c ON o.customer_id = c.id;\n\n-- Or add index on join column\nCREATE INDEX idx_customer_email ON customers(email);\n```\n\n### 5. Duplicating Rows Unexpectedly\n\n```sql\n-- ❌ One-to-many creates duplicates\nSELECT c.name, c.total, p.amount\nFROM customers c\nJOIN payments p ON c.id = p.customer_id;\n-- Customer appears once per payment!\n\n-- ✅ Aggregate if needed\nSELECT c.name, c.total, SUM(p.amount)\nFROM customers c\nJOIN payments p ON c.id = p.customer_id\nGROUP BY c.id, c.name, c.total;\n```\n\n---\n\n## 🎯 Interview Practice\n\nTest your SQL JOIN knowledge with 10 curated interview questions:\n\n```visualizer-sqljoin-interview\nshowControls: true\nshowCode: true\n```\n\n---\n\n## 🎤 Interview Tips\n\n**Q: What's the difference between INNER and LEFT JOIN?**\n\n> INNER JOIN returns only rows that match in both tables. LEFT JOIN returns all rows from the left table plus matching rows from the right, with NULL for non-matches.\n\n**Q: When would you use FULL OUTER JOIN?**\n\n> To find mismatches between two tables - rows that exist in one but not the other. Useful for data reconciliation, migration validation, or finding orphan records on both sides.\n\n**Q: How would you find customers with no orders?**\n\n> Use LEFT JOIN with NULL check: `SELECT c.* FROM customers c LEFT JOIN orders o ON c.id = o.customer_id WHERE o.id IS NULL`\n\n**Q: What's the performance difference between joins?**\n\n> INNER JOIN is often fastest (fewer rows). JOIN performance depends on indexes, table sizes, and join algorithm (nested loop, hash, merge). Always index foreign key columns.\n\n---\n\n## 📚 Series Navigation\n\n**Previous**: [Part 18: Garbage Collection](dsa-cheatsheet-part-18-gc)\n\n**Next**: [Part 20: Bloom Filter](dsa-cheatsheet-part-20-bloom-filter)\n\n---\n\n**Visualizer**: `SQLJoinVisualizer` from `@tomaszjarosz/react-visualizers`\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.758909Z","createdAt","2026-06-10T07:19:25.759143Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",6,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",4,"seriesOrder",19,"author",{"_33":57,"_104":59,"_105":106,"_107":108,"_109":-5,"_110":-5,"_111":-5,"_112":-5,"_113":-5},"category",{"_33":54,"_75":61,"_37":101,"_78":102,"_103":-5},"tags",[81,82,83,84,85],"series",{"_33":64,"_75":76,"_37":77,"_78":79,"_80":24},"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",{"_33":98,"_75":99,"_37":100},{"_33":95,"_75":96,"_37":97},{"_33":92,"_75":93,"_37":94},{"_33":89,"_75":90,"_37":91},{"_33":86,"_75":87,"_37":88},297,"Sql","sql",301,"Outer","outer",298,"Join","join",300,"Inner","inner",299,"Database","database","algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl",92,"B-Tree","dsa-cheatsheet-part-21-btree","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","2026-06-10T07:19:25.773447Z","2026-06-10T07:19:25.773664Z",5,21,{"_33":57,"_104":59,"_105":106,"_107":108,"_109":-5,"_110":-5,"_111":-5,"_112":-5,"_113":-5},{"_33":54,"_75":61,"_37":101,"_78":102,"_103":-5},[127,128,129,130],{"_33":64,"_75":76,"_37":77,"_78":79,"_80":24},{"_33":137,"_75":138,"_37":139},{"_33":98,"_75":99,"_37":100},{"_33":134,"_75":135,"_37":136},{"_33":131,"_75":132,"_37":133},304,"Index","index",305,"Disk-optimized","disk-optimized",303,"B-tree","b-tree"]