Arsitektur Storage Modern: B-Tree, LSM-Tree & Open Table Formats

Setiap sistem basis data transaksional (OLTP), mesin pencari log berskala petabyte, hingga gudang data analitik (OLAP) berdiri di atas satu komponen penentu performa yang sama: mesin penyimpanan (storage engine). Di balik abstraksi kueri SQL atau antarmuka API Key-Value, mesin penyimpanan bertugas mengatur bagaimana byte ditempatkan pada blok NVMe SSD atau objek penyimpanan awan (object storage), bagaimana konkurensi ditangani tanpa merusak integritas data, serta bagaimana meminimalkan amplifikasi operasi I/O.

Dalam rekayasa sistem penyimpanan, tidak ada satu struktur data tunggal yang mampu mengoptimalkan kecepatan baca, kecepatan tulis, dan efisiensi ruang penyimpanan secara bersamaan. Prinsip ini diformulasikan melalui Konjektur RUM (Read, Update, Memory/Space Overhead): sebuah mesin penyimpanan hanya dapat mengoptimalkan dua dari tiga dimensi tersebut dengan mengorbankan dimensi ketiga. Panduan arsitektur evergreen ini membedah secara komprehensif tiga paradigma utama mesin penyimpanan modern—B+Tree untuk pembaruan di tempat (in-place update), Log-Structured Merge-Tree (LSM-Tree) untuk throughput tulis ekstrem, serta arsitektur Columnar Lakehouse berbasis Apache Iceberg dan Parquet untuk analitik skala masif.

1. Konjektur RUM dan Matematika Amplifikasi I/O pada Media NVMe

Untuk menilai keunggulan arsitektural antara B+Tree dan LSM-Tree, insinyur sistem menggunakan tiga metrik kuantitatif utama: Write Amplification Factor (WAF), Read Amplification Factor (RAF), dan Space Amplification Factor (SAF). Write Amplification mengukur rasio antara jumlah byte yang ditulis secara fisik ke perangkat penyimpanan (NVMe SSD) terhadap jumlah byte logis yang dikirimkan oleh aplikasi ke basis data.

Pada perangkat NVMe SSD modern berbasis NAND Flash, operasi baca dan tulis dilakukan pada satuan halaman (page, umumnya 4 KB atau 16 KB), namun operasi penghapusan (erase) hanya dapat dilakukan pada tingkat blok (erase block, berukuran beberapa Megabyte) melalui proses Flash Translation Layer (FTL) Garbage Collection. Jika mesin penyimpanan terus-menerus memodifikasi halaman berukuran 8 KB secara acak (random in-place writes), FTL internal SSD harus menyalin halaman valid lainnya sebelum menghapus blok, yang melipatgandakan keausan sel NAND dan menurunkan throughput tulis berkelanjutan.

2. Arsitektur B+Tree: Slotted Pages, Buffer Pool, dan Protokol Pemulihan ARIES

Mesin penyimpanan relasional klasik seperti PostgreSQL (Heap + B-Tree), InnoDB pada MySQL (Clustered B+Tree), dan SQLite menggunakan variasi B+Tree dengan ukuran halaman tetap (fixed-size page, misalnya 8 KB di PostgreSQL dan 16 KB di InnoDB). Berbeda dari B-Tree akademik yang menyimpan payload data di node internal maupun daun, B+Tree modern hanya menyimpan kunci pemandu (separator keys) dan pointer halaman anak di node internal, sementara seluruh rekaman data aktual (atau tuple pointer) disimpan secara berurutan pada node daun (leaf pages) yang saling terhubung melalui daftar berantai ganda (doubly-linked sibling pointers).

Di dalam satu halaman berukuran 8 KB, data diorganisasikan menggunakan tata letak Slotted Page. Bagian atas halaman berisi Page Header (menyimpan Log Sequence Number/LSN terakhir, checksum CRC32C, dan batas ruang bebas) diikuti oleh larik Line Pointer (atau Slot Array) yang tumbuh dari atas ke bawah. Sebaliknya, isi rekaman aktual (tuples) disisipkan dari batas bawah halaman tumbuh ke arah atas. Desain Slotted Page ini memungkinkan mesin penyimpanan memindahkan posisi fisik tuple di dalam halaman (defragmentasi lokal) atau menghapus tuple cukup dengan menandai slot pointer terkait tanpa mengubah referensi Row ID (TID/RID) dari indeks eksternal.

+-----------------------------------------------------------------------+
| Page Header (24B): pd_lsn (8B) | pd_checksum | pd_lower | pd_upper    |
+-----------------------------------------------------------------------+
| Line Pointers / Slot Array (tumbuh ke bawah -->)                      |
| [Slot 0: offset 7920, len 180] [Slot 1: offset 7710, len 210] [Slot 2]|
+-----------------------------------------------------------------------+
|                       <--- Ruang Bebas (Free Space) --->              |
+-----------------------------------------------------------------------+
|                      (<-- tumbuh ke atas) Data Tuples Aktual          |
| ... [Tuple 2 (xmin, xmax, data)] [Tuple 1] [Tuple 0: offset 7920]     |
+-----------------------------------------------------------------------+

Karena modifikasi halaman dilakukan langsung di memori (Buffer Pool) sebelum ditulis ke disk secara asinkron oleh proses latar belakang (checkpointer/page cleaner), mesin B+Tree mengandalkan protokol ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) dengan kebijakan Steal/No-Force. Kebijakan No-Force berarti transaksi yang telah di-commit tidak wajib langsung memaksa (flush) halaman data yang dimodifikasi (dirty pages) ke disk, melainkan cukup memastikan catatan perubahan pada Write-Ahead Log (WAL / Redo Log) telah tersimpan secara sekuensial ke penyimpanan persisten melalui panggilan sistem fsync().

Implementasi Multi-Version Concurrency Control (MVCC) pada B+Tree terbagi menjadi dua aliran arsitektur utama. InnoDB dan Oracle menggunakan pendekatan Rollback Undo Segment: pembaruan baris memodifikasi halaman indeks secara langsung di tempat, sementara versi lama disalin ke ruang Undo Log terpisah untuk melayani pembacaan transaksi lama (snapshot isolation). Sebaliknya, PostgreSQL menggunakan pendekatan Append-Only Tuple Versioning di mana setiap operasi UPDATE menyisipkan tuple versi baru di halaman heap dan memperbarui header visibilitas (xmin dan xmax). Meskipun mempercepat transaksi pembacaan masa kini tanpa perlu merekonstruksi rantai undo, pendekatan PostgreSQL membutuhkan proses VACUUM berkala untuk membebaskan tuple mati (dead tuples) dan mencegah pembengkakan tabel (table bloat) serta pembekuan ID transaksi (Transaction ID Wraparound).

3. Arsitektur LSM-Tree: MemTable, SSTable Immutable, dan Strategi Compaction

Ketika beban kerja didominasi oleh aliran penulisan berkecepatan tinggi—seperti telemetri waktu nyata, pencatatan peristiwa terdistribusi, atau penyimpanan state pada sistem streaming seperti Apache Flink dan CockroachDB—biaya I/O acak pada B+Tree menjadi hambatan utama. Struktur Log-Structured Merge-Tree (LSM-Tree), yang dipopulerkan melalui Google Bigtable, LevelDB, Meta RocksDB, dan Apache Cassandra, menyelesaikan masalah ini dengan menghapus modifikasi di tempat (in-place update) sepenuhnya.

Pada mesin berbasis LSM-Tree seperti RocksDB, setiap operasi PUT, MERGE, maupun DELETE pertama-tama dicatat secara sekuensial ke file Write-Ahead Log di disk untuk ketahanan terhadap kegagalan daya, lalu langsung disisipkan ke dalam struktur data terurut di memori utama yang disebut MemTable (umumnya diimplementasikan sebagai Concurrent SkipList bebas kunci/lock-free). Karena penyisipan ke RAM dan penulisan append-only ke WAL tidak melibatkan pencarian blok disk acak, latensi tulis menjadi sangat rendah dan konsisten.

4. Eksekusi Analitik Kolom (Columnar) & Vektorisasi SIMD pada Parquet dan DuckDB

Baik B+Tree maupun LSM-Tree merupakan mesin berorientasi baris (row-oriented): seluruh atribut dari satu baris disimpan berdampingan. Tata letak baris sangat ideal ketika aplikasi mengambil seluruh kolom dari satu entitas berdasarkan ID pelanggan. Namun, ketika kueri analitik (OLAP) menghitung agregasi atas 2 miliar baris tetapi hanya membutuhkan 3 dari 150 kolom yang tersedia, membaca seluruh baris akan membuang lebih dari 95% bandwidth I/O dan mencemari jalur cache CPU (CPU cache lines) dengan atribut yang tidak relevan.

Format penyimpanan kolom terbuka seperti Apache Parquet dan mesin analitik proses dalam (in-process) seperti DuckDB mengatasi hal ini melalui arsitektur PAX (Partition Attributes Across) atau Hybrid Columnar. Data dibagi secara horizontal menjadi Row Groups (misalnya 128.000 baris atau 64–512 MB per grup), kemudian di dalam setiap Row Group, data disimpan secara vertikal per kolom sebagai Column Chunks dan Data Pages.

-- Contoh eksekusi kueri analitik tervektorisasi di DuckDB langsung di atas berkas Parquet/Iceberg:
EXPLAIN ANALYZE
SELECT
    region_code,
     date_trunc(class="text-[#7ee787]">'day', event_timestamp) AS event_day,
    count(*) AS total_requests,
    approx_quantile(latency_ms, 0.99) AS p99_latency_ms
FROM read_parquet(class="text-[#7ee787]">'s3://prod-telemetry-lake/events/year=2026/month=10/*.parquet')
WHERE status_code >= 500
  AND event_timestamp >= TIMESTAMP class="text-[#7ee787]">'2026-10-14 00:00:00'
GROUP BY ALL
ORDER BY total_requests DESC;

Keunggulan kecepatan mesin analitik modern bertumpu pada empat pilar rekayasa tingkat rendah: (1) Kompresi Homogen Spesifik Tipe Data—karena satu halaman hanya berisi nilai dari kolom yang sama, algoritma Dictionary Encoding, Run-Length Encoding (RLE), Delta Encoding, dan Bit-Packing dapat menekan ukuran data 5x hingga 15x lebih kecil dibanding kompresi baris umum; (2) Zone Maps / Min-Max Pruning—setiap Row Group dan Data Page menyimpan metadata nilai minimum, maksimum, dan jumlah null sehingga mesin kueri dapat melompati (skip) pembacaan gigabyte blok data yang tidak memenuhi predikat WHERE; (3) Eksekusi Vektorisasi Berbasis Batch—alih-alih memproses satu baris demi satu baris melalui pemanggilan fungsi virtual (Volcano iterator model) yang menghancurkan pipeline instruksi CPU, DuckDB memproses larik kolom berukuran tetap (misalnya vektor 2.048 elemen) yang muat di dalam L1 cache (32–64 KB) menggunakan instruksi SIMD (AVX-512 atau ARM NEON); serta (4)Eksekusi langsung di atas data terkompresi (Late Materialization) di mana penyaringan dilakukan pada kode integer kamus sebelum string asli didekompresi.

5. Arsitektur Apache Iceberg: Transaksi ACID di Atas Penyimpanan Objek

Selama lebih dari satu dekade, danau data (data lake) yang dibangun di atas penyimpanan objek seperti Amazon S3, Google Cloud Storage, atau MinIO menderita kelemahan arsitektural kronis dari format direktori Apache Hive: ketiadaan transaksi atomik, keharusan melakukan operasi LIST direktori yang lambat serta mahal, ketidakmampuan mengubah skema atau partisi tanpa menulis ulang seluruh tabel, serta risiko pembacaan data korup saat pekerjaan penulisan sedang berlangsung.

Apache Iceberg menyelesaikan masalah ini dengan membawa arsitektur pohon metadata persisten (mirip struktur B-Tree / Git commit graph) ke atas penyimpanan objek yang bersifat immutable. Alih-alih mendefinisikan tabel sebagai daftar berkas di dalam folder direktori fisik, Iceberg melacak setiap berkas data secara eksplisit melalui hierarki empat lapis yang diikat oleh satu penunjuk atomik di tingkat Katalog.

6. Matriks Perbandingan Arsitektur Mesin Penyimpanan

Tabel arsitektur berikut merangkum profil kinerja kuantitatif, struktur fisik, dan kecocokan beban kerja antara ketiga keluarga mesin penyimpanan modern pada infrastruktur produksi:

+--------------------------+------------------------+-------------------------+--------------------------+
| Dimensi Arsitektur       | B+Tree (PostgreSQL /   | LSM-Tree (RocksDB /     | Columnar Lakehouse       |
|                          | InnoDB)                | Cassandra / Pebble)     | (Parquet + Iceberg)      |
+--------------------------+------------------------+-------------------------+--------------------------+
| Satuan Fisik Dasar       | Fixed Slotted Page     | MemTable + Immutable    | Row Group (64-512MB) +   |
|                          | (8 KB - 16 KB)         | SSTable Blocks          | Column Chunks            |
| Pola I/O Penulisan       | Random In-Place +      | Sequential Append-Only  | Immutable File Write +   |
|                          | Sequential WAL         | WAL + Compaction Merge  | Atomic Metadata Swap     |
| Write Amplification (WAF)| Tinggi (10x - 30x)     | Rendah-Sedang (3x - 10x)| Sangat Rendah (1x - 2x)  |
| Latensi Point Lookup     | Sangat Rendah (<0.5ms) | Rendah (1-3ms, dibantu  | Tinggi (Tidak dirancang  |
|                          | O(log_B N) halaman     | Bloom/Ribbon Filter)    | untuk OLTP point lookup) |
| Throughput Scan Analitik | Rendah (Row-oriented)  | Sedang (Key-range scan) | Ekstrem (SIMD + Pruning) |
| Space Amplification      | Sedang (~25-33%        | Sangat Rendah (~10%     | Sangat Rendah (Kompresi  |
|                          | page fragmentation)    | pada Leveled Compaction)| RLE + Dictionary 5x-15x) |
| Beban Kerja Ideal        | Transaksi OLTP latensi | Ingesti tulis masif,    | Gudang data analitik,    |
|                          | rendah & relasi ketat  | state engine, KV store  | AI feature store & log   |
+--------------------------+------------------------+-------------------------+--------------------------+

“Memilih mesin penyimpanan bukan tentang mencari struktur data tercepat secara absolut, melainkan menyelaraskan pola akses aplikasi dengan fisika perangkat keras: B+Tree meminimalkan operasi baca melalui struktur halaman terurut di tempat, LSM-Tree menukarkan pemeliharaan latar belakang demi kecepatan tulis sekuensial, dan format kolom terbuka memaksimalkan bandwidth SIMD serta efisiensi penyimpanan objek.”