Index B-tree di MySQL: Cara Kerja B+Tree InnoDB dari Root sampai Leaf

Lambatnya satu query bisa bikin seharian penuh debugging. Pengalaman saya: query yang di localhost jalan sepersekian detik, begitu ketemu tabel dengan ratusan ribu baris langsung berubah jadi puluhan detik. Hampir selalu jawabannya sama — kolom yang dipakai di WHERE tidak punya index. Artikel ini adalah catatan saya memahami struktur di balik kata ajaib index itu: B-tree (tepatnya, varian B+Tree yang dipakai InnoDB).

Masalah dasar: mencari jarum di tumpukan jerami

Tanpa index, satu-satunya cara MySQL menjawab SELECT * FROM users WHERE email = 'foo@bar.com' adalah full table scan: membaca tabel dari baris pertama sampai terakhir, memeriksa satu per satu. Kalau email yang dicari kebetulan ada di baris terakhir dari 10 juta baris, ya 10 juta pemeriksaan. Kompleksitasnya O(N) — bertambah linear seiring bertambahnya data.

Menariknya, kita semua sebenarnya sudah paham konsep solusinya sejak membuka buku telepon atau kamus: alih-alih membaca halaman demi halaman, kita melompat. Buka bagian tengah, lihat hurufnya, putuskan maju atau mundur, ulangi. Setiap langkah memangkas ruang pencarian jadi setengahnya (atau lebih). Itulah ide inti B-tree.

B+Tree versi InnoDB: node = page 16 KB

Dokumentasi MySQL menyebut hampir semua index (PRIMARY KEY, UNIQUE, INDEX) disimpan sebagai B-tree. Khusus InnoDB, strukturnya adalah B+Tree: semua data asli ditaruh di leaf pages (daun), sedangkan level di atasnya hanya berisi kunci pemisah dan penunjuk arah. Satu hal yang dulu bikin saya salah paham: tiap “node” di gambar-gambar diagram bukanlah satu angka kecil — ia adalah satu page disk berukuran 16 KB (default innodb_page_size), berisi ratusan kunci sekaligus.

Pencarian berjalan seperti binari search versi disk: mulai dari root page (lokasinya tetap dan tersimpan di data dictionary), bandingkan kunci, ikuti penunjuk ke child page yang tepat, turun sampai leaf. Karena pohon selalu seimbang — semua daun berada di kedalaman yang sama — jumlah bacaan untuk mencari data apa pun selalu sama persis: setinggi pohonnya. Tidak ada kasus sial.

-- Membuat index sekunder di tabel yang sudah ada
CREATE INDEX idx_email ON users (email);

-- Index komposit: urutan kolom PENTING (prinsip leftmost prefix)
CREATE INDEX idx_status_date ON orders (status, created_at);

-- Index ini bisa dipakai query mana?
-- WHERE status = 'paid'                          ✔ pakai (kolom paling kiri)
-- WHERE status = 'paid' AND created_at > '2026-01-01'  ✔ pakai keduanya
-- WHERE created_at > '2026-01-01'                ✘ tidak (melompati kolom kiri)

Kenapa tingginya cuma 3–4 level meski datanya jutaan

Ini bagian favorit saya. Page 16 KB bisa menampung ratusan kunci — misal kunci integer 8 byte + pointer, mudah-mudahan 500–800 entri per page. Anggap 500. Artinya:

• Level 0 (leaf): menyimpan data, jutaan baris tersebar di ribuan page.
• Level 1: 500 leaf page cukup dirangkum oleh satu page internal.
• Level 2: 250.000 leaf dirangkum 500 page level 1, dst.

Hasilnya: tabel dengan ratusan juta baris biasanya cuma butuh pohon setinggi 3–4 level. Karena tiap level = satu pembacaan page, mencari satu baris ≈ 3–4 page read. Bandingkan dengan jutaan pemeriksaan baris pada full scan. Ini yang dimaksud kompleksitas O(log N) dalam praktiknya — dan kenapa fan-out besar membuat pohon tetap pendek.

Clustered vs secondary index: dua pohon untuk satu tabel

InnoDB punya konsep yang sering membingungkan pemula (termasuk saya dulu): tabel itu sendiri adalah sebuah B+Tree. Clustered index — identik dengan primary key — menyimpan seluruh baris data di leaf pages-nya, terurut berdasarkan primary key. Kalau tabel tidak punya primary key, InnoDB memakai UNIQUE NOT NULL pertama; kalau tidak ada juga, ia membuat kolom row ID tersembunyi 6 byte.

Secondary index (index lain selain primary key) juga B+Tree, tapi leaf-nya hanya menyimpan nilai kolom yang di-index plus primary key baris tersebut. Konsekuensinya penting:

• Mencari lewat secondary index lalu butuh kolom lain → harus baca lagi clustered index pakai primary key tadi (disebut book lookup). Itu perjalanan B+Tree kedua.
• Karena itu primary key pendek itu bagus: nilai PK tersimpan di SEMUA secondary index. PK 36-byte UUID menggandakan ukuran tiap index dibanding INT auto-increment 4 byte.
• Kalau query hanya butuh kolom-kolom yang ada di index itu sendiri, MySQL tidak perlu balik ke tabel — covering index, ditandai Using index di EXPLAIN.

Kapan index DIPAKAI, kapan diabaikan

Index yang ada tidak otomatis dipakai. Optimizer memutuskan berdasarkan statistik, dan beberapa pola query jelas-jelas membuat index tidak terpakai. Cara mengeceknya: taruh EXPLAIN di depan query, lalu baca kolom type (semakin ke atas semakin bagus) dan kolom key (index mana yang benar-benar dipilih):

type di EXPLAIN	Arti	Penilaian
const / eq_ref	Lookup unik via PRIMARY/UNIQUE key	Terbaik
ref	Lookup via index non-unik (=)	Baik
range	Rentang: BETWEEN, >, <, LIKE ‘abc%’	Cukup
index	Scan seluruh index tree	Buruk
ALL	Full table scan	Perbaiki!

Beberapa pembunuh index yang saya pelajari cara keras (atau baca pengalaman orang): fungsi di kolom (WHERE YEAR(created_at) = 2026) membuat index tak terpakai — tulis sebagai rentang saja; leading wildcard LIKE '%abc' tidak bisa memanfaatkan urutan B-tree; implicit conversion (string vs angka) menjatuhkan index; dan index komposit yang tidak diawali kolom paling kiri.

Biaya yang jarang dibicarakan

Index bukan gratis. Tiap INSERT/UPDATE/DELETE harus memelihara semua B+Tree yang menyentuh kolom itu — tulis jadi lebih lambat, disk makin penuh. Insert acak (misal primary key UUID) menyebabkan page split di posisi acak, sementara insert berurutan (auto-increment) mengisi page hingga ±15/16 sesuai dokumentasi InnoDB. Kolom dengan cardinality rendah (misal kolom boolean aktif/tidak) jarang berguna sebagai index tunggal karena selektivitasnya buruk — optimizer bahkan bisa memilih full scan kalau index tidak mempersempit apa-apa.

Aturan main yang saya pegang: index untuk kolom yang sering muncul di WHERE, JOIN, dan ORDER BY; utamakan cardinality tinggi; index komposit disusun dari kolom paling selektif/most-frequently-used ke kanan; dan selalu verifikasi dengan EXPLAIN bahwa index benar-benar dipakai — jangan diasumsikan.

Catatan untuk diri sendiri

Index mempercepat READ dengan membayar mahal pada WRITE dan storage. Memasang index di semua kolom bukan optimasi — itu utang yang jatuh temponya saat trafik naik. Pahami strukturnya dulu (B+Tree, page 16 KB, clustered vs secondary), baru tambahkan index secukupnya dan ukur dengan EXPLAIN.

Sumber

• MySQL Manual — The Physical Structure of an InnoDB Index (page 16 KB, fill factor, merge threshold)
• MySQL Manual — Clustered and Secondary Indexes
• MySQL Manual — How MySQL Uses Indexes (leftmost prefix, MIN/MAX, covering index)
• MySQL Manual — EXPLAIN Output (Join Types)
• Jeremy Cole — B+Tree index structures in InnoDB (root/leaf/level, linked list antar page)