- Baru-baru ini, saat membaca Database Internals karya Alex Petrov, saya menemukan penjelasan tentang bagaimana storage engine DBMS diimplementasikan, khususnya terkait optimisasi struktur data B-Tree
- Saat mempelajari B-Tree di universitas, saya hanya memahaminya secara sederhana sebagai “BST yang lebih baik”, sehingga saya tidak benar-benar merasakan mengapa struktur ini digunakan di dunia nyata
- B-Tree cocok untuk menyimpan data berskala besar dan melakukan pencarian cepat dengan mempertimbangkan disk I/O
- Artikel ini memperkenalkan mengapa B-Tree diperlukan, bagaimana cara kerjanya, dan optimisasi apa saja yang mungkin dilakukan dalam implementasi nyata
- Salah satu ciri utamanya adalah mengumpulkan banyak key dalam satu node untuk mengurangi jumlah akses disk
Batasan yang muncul karena disk
- Diasumsikan bahwa seluruh data tidak muat di memori
- Disk memiliki karakteristik dibaca dan ditulis sekaligus dalam satuan halaman
- Akses disk jauh lebih lambat dibanding akses memori
- Karena itu, struktur data perlu menata data dengan berpusat pada halaman dan melakukan sebanyak mungkin perbandingan key dengan akses disk seminimal mungkin
- Jika BST disimpan langsung di disk, node-node akan tersebar, sehingga jumlah akses disk ikut bertambah seiring jumlah langkah pencarian
- B-Tree mengumpulkan banyak key dalam satu node agar satu kali pembacaan disk dapat dipakai untuk membandingkan beberapa key sekaligus
Slot page
- Saat menata data di disk, pengelolaannya dilakukan per unit “halaman”
- Setiap halaman memiliki header, cell yang menyimpan data dengan panjang variabel, dan array pointer offset yang menyimpan informasi posisi cell
- Struktur slot page memiliki keunggulan karena tetap dapat mempertahankan urutan terurut tanpa beban penataan ulang yang besar meskipun ukuran key bervariasi
- Saat key dihapus atau disisipkan, jauh lebih efisien menata ulang pointer dibanding memindahkan data sebenarnya
- Sebagai contoh, SQLite menempatkan free list di dalam struktur halaman seperti ini dan menggunakan kembali ruang cell yang telah dihapus
Pencarian B-Tree
- Algoritma pencarian B-tree sederhana:
- Mulai dari node root
- Lihat separator key pada node saat ini, lalu cari child node yang diperkirakan berisi key yang dicari
- Telusuri tree secara rekursif
- Jika leaf node yang memuat key pencarian ditemukan, proses selesai; jika tidak, key dianggap tidak ada
- Pada internal node, kadang cukup hanya menyimpan separator key alih-alih data sebenarnya, dan umumnya data nyata hanya disimpan di leaf node
- Agar key di dalam node bisa dicari secara efisien dengan binary search, key-key di setiap node dijaga tetap dalam keadaan terurut
Pemendekan separator key
- Separator key pada internal node tidak harus berupa seluruh key asli, asalkan cukup untuk membedakan rentang
- Misalnya, untuk membedakan antara 0xAAAAAA dan 0xBBBBBB, tidak selalu perlu menyimpan seluruh 0xBBBBBB; pemisahan bisa dilakukan dengan prefiks yang lebih pendek
- Pada database dengan panjang key yang besar, pemendekan seperti ini bisa memberikan penghematan ruang penyimpanan yang signifikan
- Selain pemendekan separator key, ada juga strategi untuk mengurangi prefiks (prefix) dan sufiks (suffix) secara efisien
- Karena jumlah leaf node jauh lebih banyak, ada juga pandangan bahwa kompresi prefiks memberi kontribusi yang lebih besar terhadap performa
Overflow page
- Jika sebuah node memiliki terlalu banyak key hingga tidak muat dalam satu halaman, overflow page digunakan
- Alih-alih memindahkan seluruh key apa adanya ke overflow page, node hanya menyisakan prefiks pendek lalu menyimpan sisanya secara terpisah
- Dengan begitu, saat memeriksa keberadaan key atau melakukan pencarian rentang, sistem cukup melihat prefiks di node terlebih dahulu dan hanya membaca overflow page jika benar-benar diperlukan
- Ini adalah cara untuk menurunkan biaya pencarian total meskipun harus mengalokasikan halaman tambahan
Sibling pointer
- Ada pendekatan implementasi yang menyimpan pointer ke sibling node kiri dan kanan antar-node
- Dengan cara ini, saat melakukan range query, sistem bisa langsung berpindah dari satu leaf node ke sibling berikutnya dan menelusuri key yang berurutan dengan cepat
- Jika sibling pointer tidak ada, proses harus berulang kali naik ke parent node lalu turun lagi, sehingga biaya I/O meningkat
- Karena rentang key antar sibling node tidak saling tumpang tindih, berpindah melalui pointer sibling kanan menjamin bahwa kita masuk ke “rentang key berikutnya”
Varian B-Tree
- Selain B⁺-Tree, ada berbagai struktur varian lainnya
- “Lazy B-Tree” seperti di WiredTiger maupun Lazy-Adaptive Tree menggunakan pendekatan buffering pada operasi tulis untuk meningkatkan performa
- FD-Tree adalah struktur yang dirancang sesuai karakteristik SSD, dengan mempertimbangkan batasan fisik seperti penulisan berbasis blok
- Bw-Tree (Buzzword Tree) adalah struktur data yang dioptimalkan untuk konkurensi tinggi dan akses tree di memori
Kesimpulan
- Di antara konsep abstrak “B⁺-Tree” dan implementasi nyata seperti “format DB SQLite”, terdapat banyak optimisasi dan detail implementasi yang berbeda
- Optimisasi tidak mengubah kompleksitas Big-O, tetapi sangat memengaruhi performa dan kegunaan database di lingkungan nyata
- Selain hal-hal yang diperkenalkan di sini, setiap storage system tertentu juga membutuhkan banyak fine-tuning
- Di balik ungkapan “hanya butuh sedikit informasi tambahan”, tersembunyi kompleksitas implementasi dan sulitnya debugging
- Sebagai contoh yang menggambarkan struktur B-Tree dengan cara yang lebih realistis, diagram B-Tree di Designing Data Intensive Applications terasa mengesankan
1 komentar
Opini Hacker News
Struktur halaman terdiri dari header, sel, dan pointer offset, dengan keunggulan dapat menyimpan data berukuran variabel
Artikel yang sangat bagus tentang B-Tree, lengkap dengan animasi
Beberapa tahun lalu saya mengimplementasikan B-link Tree yang dapat dipulihkan secara konkuren berdasarkan penelitian Ibrahim Jaluta
Saya membuat penjelajah halaman disk SQLite dan jadi lebih memahami B-Tree
Pembahasan tentang B-link Tree, konkurensi, dan penguncian memang tidak ada, tetapi itu mungkin sudah lebih dari yang diperlukan
Komentar lama: Hacker News
Artikel yang sangat bagus, dan menjelaskan pentingnya detail dengan sangat baik
Referensi yang bagus untuk implementasi B-Tree menggunakan Golang
Saya sangat menyukai artikel ini, dan sebelumnya juga punya 'pemahaman yang samar' seperti penulisnya