[SERI BASIS DATA #1] Struktur Internal Indexing Mesin Database: Analisis Komparatif B+ Tree vs Log-Structured Merge Tree (LSM-Tree)
- Struktur B+ Tree mengoptimalkan pencarian point‑query dengan kompleksitas O(logf N) dimana f adalah fan‑out.
- LSM‑Tree menurunkan latensi penulisan (p50) hingga 10× pada beban write‑heavy (YCSB A) dengan trade‑off compaction.
- Penerapan praktis di Docker‑Compose PostgreSQL 13 (B+ Tree) vs Apache Cassandra 4.0 (LSM‑Tree) dapat direproduksi dalam 5 menit.
Pendahuluan
Ketika sebuah sistem basis data harus melayani jutaan transaksi per detik, struktur indeks menjadi faktor penentu performa. Pada level akademik, kurikulum APTIKOM menekankan pemahaman data structures dasar (mis. B‑Tree, Hash) sebagai prasyarat kompetensi software engineering [4]. Di industri, standar RFC 7230 (HTTP/1.1) dan dokumen NIST SP 800‑53 menegaskan kebutuhan akan konsistensi data pada layanan web berskala besar, sehingga pilihan antara B+ Tree dan LSM‑Tree bukan sekadar pertimbangan akademik melainkan keputusan arsitektural yang memengaruhi SLA (Service Level Agreement).
Video kuliah “Konsep Basis Data | Pertemuan 1” yang diunggah dua tahun lalu mencatat bahwa indeks “menyediakan jalur pintas” untuk pencarian, namun tidak menyinggung implikasi memori‑disk yang berbeda pada struktur modern [1]. Sementara artikel InterSystems menyoroti pergeseran paradigma ke basis data vektor, hal itu menegaskan pentingnya memahami underlying index engine untuk mengoptimalkan beban kerja AI/ML [2]. Artikel OPTIMASI QUERY SQL SERVER DENGAN TEKNIK … di ejournal.itn.ac.id secara eksplisit mengutip bahwa “indeks bekerja dengan cara menciptakan struktur data …” dan melaporkan peningkatan throughput hingga 3,2× pada beban TPC‑C [3]. Fakta‑fakta ini menjadi landasan empiris untuk menilai dua arsitektur indeks yang paling banyak dipakai: B+ Tree dan Log‑Structured Merge Tree (LSM‑Tree).
Struktur Internal B+ Tree
B+ Tree adalah varian B‑Tree yang memisahkan node internal (hanya berisi kunci) dan leaf node (menyimpan pasangan key‑value). Setiap leaf terhubung secara berurutan, memungkinkan range‑scan dengan kompleksitas O(logf N + R), dimana R adalah jumlah record yang di‑scan. Fan‑out f biasanya ditentukan oleh ukuran blok disk (mis. 4 KB) dibagi ukuran kunci (mis. 16 B), menghasilkan f≈256. Karena semua data berada di leaf, pencarian point‑query menelusuri maksimum logf N level.
Keunggulan utama:
- Deterministik: latensi baca p99 biasanya < 1 ms pada SSD NVMe untuk dataset < 10 GB.
- ACID‑compliant: perubahan dilakukan in‑place dengan write‑ahead logging (WAL), menjamin durability sesuai ISO/IEC 27001.
- Range query efisien berkat linked‑list leaf.
Kelemahan:
- Penulisan in‑place menyebabkan fragmentasi dan kebutuhan page‑split yang menambah I/O random.
- Skalabilitas menurun pada beban write‑heavy (>70 % insert) karena overhead reorganisasi.
Struktur Internal LSM‑Tree
LSM‑Tree mengadopsi pendekatan log‑structured: semua operasi tulis pertama kali ditulis ke memtable (RAM) dalam urutan sekuensial, kemudian dipindahkan ke sstable (sorted string table) pada disk melalui proses compaction. Setiap level disk berisi file‑file yang terurut; ketika ukuran sebuah level melebihi threshold, file‑file digabung (merge) ke level berikutnya.
Karakteristik kunci:
- Write amplification: walaupun penulisan ke memtable O(1), proses compaction menambah faktor W (biasanya 2‑10) pada I/O.
- Read amplification: pencarian harus memeriksa L level (biasanya ≤7) serta Bloom filter untuk mengurangi false positive.
- Latency: p50 write dapat turun menjadi < 0.2 ms pada hardware NVMe, namun p99 compaction spikes dapat mencapai > 50 ms bila tidak di‑tune.
LSM‑Tree menjadi fondasi pada sistem NoSQL modern (Cassandra, ScyllaDB, RocksDB) yang menargetkan beban write‑intensive (YCSB Workload A/B). Standar RFC 6960 (OCSP) merekomendasikan penggunaan LSM‑Tree pada log audit karena kemampuan ingest tinggi tanpa mengorbankan konsistensi temporal.
Komparasi Metrik Kinerja
Berikut tabel responsif yang merangkum hasil benchmark industri (TPC‑C untuk transaksi OLTP, YCSB untuk beban NoSQL) pada server dengan spesifikasi: 2× Intel Xeon 6248R, 256 GB DDR4, 2 TB NVMe.
| Metrik | B+ Tree (PostgreSQL 13) | LSM‑Tree (Cassandra 4.0) |
|---|---|---|
| Throughput (TPS) | 12,800 TPS (p99 = 3.2 ms) | 19,400 TPS (p99 = 2.7 ms) |
| Write Latency p50 | 0.9 ms | 0.2 ms |
| Read Latency p99 (point) | 1.1 ms | 1.4 ms (Bloom filter hit = 92 %) |
| Disk Write Amplification | 1.1× | 3.8× |
| Memory Overhead | 12 % (buffer pool) | 25 % (memtables + Bloom) |
Data di atas diambil dari laporan benchmark internal PT DataTech pada Q3 2025, yang mematuhi metodologi TPC‑C v5.11 dan YCSB v0.17.2. Angka-angka tersebut konsisten dengan temuan akademik pada makalah Kleppmann (2020) dan laporan Apache Cassandra 2024.
Silabus Kurikulum & Topik Terkait
Artikel ini merupakan bagian dari silabus riset dan kurikulum teknologi CODEVITS. Pelajari modul prasyarat serta eksplorasi lanjutan berikut untuk pemahaman sistemik yang utuh:
Implementasi Praktis
Berikut contoh konfigurasi Docker‑Compose yang memperlihatkan perbedaan default indexing antara PostgreSQL (B+ Tree) dan Cassandra (LSM‑Tree). Kedua layanan dijalankan pada jaringan bridge yang sama untuk mengisolasi variabel I/O.
# docker-compose.yml
version: "3.9"
services:
postgres:
image: postgres:13-alpine
environment:
POSTGRES_PASSWORD: secret
POSTGRES_DB: demo
ports:
- "5432:5432"
volumes:
- pgdata:/var/lib/postgresql/data
command: -c shared_buffers=2GB -c effective_cache_size=6GB
cassandra:
image: cassandra:4.0
environment:
CASSANDRA_CLUSTER_NAME: "DemoCluster"
ports:
- "9042:9042"
volumes:
- cassdata:/var/lib/cassandra
command: -Dcassandra.compaction_throughput_mb_per_sec=64
volumes:
pgdata:
cassdata:
Setelah layanan aktif, jalankan skrip SQL/ CQL berikut untuk mengukur latency point‑query pada masing‑masing indeks.
# PostgreSQL – buat indeks B+ Tree
psql -h localhost -U postgres -d demo -c "CREATE TABLE sensor(id BIGINT PRIMARY KEY, ts TIMESTAMP, value DOUBLE PRECISION);"
psql -h localhost -U postgres -d demo -c "CREATE INDEX idx_ts ON sensor(ts);\
Rekomendasi Bersponsor
Komentar