Belajar Data Structure - B-Tree & B+ Tree
B-Tree dan B+ Tree dirancang untuk meminimalkan disk I/O dengan branching factor tinggi. Di episode ini kalian memahami motivasi disk I/O yang mahal, B-Tree dengan sorted keys dan split/merge node, B+ Tree dengan data hanya di leaf dan leaf linked untuk range query efisien.
#Pendahuluan
Setelah di episode 12 kita memahami AVL dan Red-Black tree — self-balancing binary tree yang menjamin O(log n) — pada episode ini kita melihat masalah nyata yang dihadapi binary tree di production: disk I/O yang mahal. Binary tree dengan height log2(n) mungkin terdengar efisien, tetapi ketika data berada di disk (bukan di RAM), setiap traversals membutuhkan disk read yang lambat. Inilah motivasi untuk B-Tree dan B+ Tree — tree dengan branching factor tinggi yang meminimalkan jumlah disk access.
B-Tree dan B+ Tree bukan hanya konsep akademis — mereka adalah backbone dari hampir semua database relasional (MySQL InnoDB, PostgreSQL) dan file system (ext4, NTFS). Memahami mereka berarti memahami bagaimana data benar-benar disimpan dan diakses di production systems.
#Motivasi: Disk I/O yang Mahal
#Mengapa Disk I/O Mahal?
| Operasi | Waktu |
|---|---|
| RAM access | ~100 ns |
| SSD random read | ~100 μs (1000x lebih lambat dari RAM) |
| HDD random read | ~10 ms (100.000x lebih lambat dari RAM) |
Ketika binary tree berada di disk, setiap node traversal = satu disk read. Dengan n = 1 juta node, binary tree butuh ~20 traversals = 20 disk reads. Dengan B-Tree branching factor 500, hanya butuh ~4 traversals.
#Solusi: Branching Factor Tinggi
B-Tree dan B+ Tree memiliki branching factor tinggi (misal: 500 atau 1000), yang berarti setiap node memiliki banyak children. Ini meminimalkan tinggi tree dan mengurangi jumlah disk read.
#B-Tree
#Konsep Dasar
B-Tree adalah balanced tree di mana setiap node bisa memiliki banyak children (bukan hanya 2 seperti binary tree). Setiap node berisi:
- Sorted keys
- Child pointers (satu lebih banyak dari jumlah keys)
- Semua data tersimpan di internal nodes
#Properti B-Tree (Order m)
- Setiap node memiliki maksimal m children
- Setiap internal node (kecuali root) memiliki minimal ceil(m/2) children
- Setiap node memiliki maksimal m-1 keys
- Root memiliki minimal 2 children (kecuali tree hanya punya satu node)
- Semua leaf berada di level yang sama
#Insert dan Split
Ketika node penuh (m-1 keys), ia split menjadi dua node, dan key tengah naik ke parent. Jika parent juga penuh, split lagi sampai ke root. Jika root split, height tree bertambah satu.
#Search
Search di B-Tree seperti binary search di dalam node: cari key yang tepat dengan binary search, lalu ikuti child pointer ke level berikutnya. Kompleksitas: O(log_m n).
#B+ Tree
#Perbedaan dengan B-Tree
B+ Tree memiliki perbedaan penting:
- Data hanya tersimpan di leaf nodes (internal nodes hanya berisi key untuk navigasi)
- Leaf nodes di-link (satu linked list dari leaf pertama ke leaf terakhir)
#Keunggulan B+ Tree
| Aspek | B-Tree | B+ Tree |
|---|---|---|
| Data location | Semua node | Hanya leaf |
| Internal node size | Lebih besar (ada data) | Lebih kecil (hanya key) |
| Range query | Tidak efisien | Sangat efisien (traverse linked list) |
| Iteration | Harus traverse tree | Leaf linked, langsung traverse |
#Range Query Efisien
B+ Tree unggul untuk range query karena leaf di-linked. Untuk query SELECT * FROM users WHERE age BETWEEN 20 AND 30, B+ Tree bisa:
- Cari leaf pertama (age = 20) via tree traversal
- Traverse linked list sampai age = 30
- Kumpulkan semua record di jalur ini
B-Tree harus traverse bolak-balik ke tree untuk setiap record.
#Aplikasi di Production
#Database Index
- MySQL InnoDB: menggunakan B+ Tree untuk clustered index
- PostgreSQL: menggunakan B-Tree (B+ Tree variant) untuk index
- MongoDB: menggunakan B-Tree untuk WiredTiger index
#File System
- ext4: menggunakan HTree (B-Tree variant) untuk directory index
- NTFS: menggunakan B+ Tree untuk MFT (Master File Table)
- ZFS: menggunakan B-Tree untuk block allocation
#Perbandingan Disk I/O
import math
for n in [1000, 100000, 1000000, 10000000]:
binary_height = math.floor(math.log2(n))
btree_height_500 = math.floor(math.log(500) * math.log(n) / math.log(500)) if n > 0 else 0
btree_height = math.ceil(math.log(n) / math.log(500))
print(f"n={n:>10}: binary={binary_height:>3} reads, B-Tree(500)={btree_height:>1} read")Note
B+ Tree digunakan di hampir semua database relasional karena unggul untuk range query. Ketika kalian membuat index di MySQL atau PostgreSQL, kalian sebenarnya sedang membuat B+ Tree. Memahami B+ Tree membantu kalian menulis query yang eficient.
#Penutup
Inti yang harus dibawa pulang:
- Disk I/O 1000-100.000x lebih lambat dari RAM → branching factor tinggi diperlukan.
- B-Tree: sorted keys + child pointers, data di semua node, split/merge saat insert/delete.
- B+ Tree: data hanya di leaf, leaf di-linked → range query efisien.
- Aplikasi: MySQL InnoDB, PostgreSQL, ext4, NTFS.
- B-Tree/B+ Tree = backbone storage engine database modern.
Di episode 14 selanjutnya kita akan membahas Trie (prefix tree) — tree di mana setiap node merepresentasikan satu karakter, shared prefix menghemat ruang. Trie digunakan untuk autocomplete, spell checker, dan IP routing. Ini adalah episode terakhir di Fase 3: Trees sebelum kita masuk ke Graphs!