Memahami Indexing pada Database: Cara Kerja B-Tree vs Hash Index

Ketika aplikasi web atau mobile berkembang dan jumlah data dalam basis data (database) mencapai ratusan ribu hingga jutaan baris, masalah performa pencarian data sering kali menjadi kendala utama. Query yang dulunya selesai dalam hitungan milidetik tiba-tiba membutuhkan waktu beberapa detik.

Solusi paling mendasar dan ampuh untuk masalah ini adalah Database Indexing. Namun, tahukah Anda bahwa index di database memiliki berbagai tipe struktur data? Dua tipe index yang paling umum digunakan adalah B-Tree Index dan Hash Index.

Artikel ini akan membahas secara mendalam bagaimana indexing bekerja, serta perbedaan mendasar antara B-Tree dan Hash Index.

1. Apa Itu Database Index?

Secara sederhana, Index pada basis data bekerja mirip seperti indeks di bagian belakang buku teks.

Tanpa indeks, jika Anda ingin mencari kata tertentu dalam buku 1000 halaman, Anda harus membaca halaman demi halaman dari awal sampai akhir. Proses ini dalam database dikenal dengan istilah Full Table Scan ($O(N)$ complexity).

Dengan indeks, database menyimpan daftar kata kunci beserta penunjuk (pointer) ke lokasi baris fisik data di mana informasi tersebut disimpan. Hasilnya, database dapat menemukan lokasi data dengan sangat cepat tanpa perlu membaca seluruh isi tabel.

2. B-Tree Index (Balanced Tree)

B-Tree (atau variannya seperti B+ Tree) adalah jenis indeks default yang digunakan oleh hampir semua RDBMS modern, seperti PostgreSQL, MySQL (InnoDB), Oracle, dan SQL Server.

Cara Kerja B-Tree

B-Tree menyimpan data dalam struktur pohon seimbang (balanced tree). Struktur ini terdiri dari:

Root Node: Titik masuk utama query.
Internal Nodes: Node perantara yang mengarahkan pencarian ke cabang yang sesuai.
Leaf Nodes: Node paling bawah yang menyimpan nilai kunci aktual dan pointer ke baris tabel.

Pohon ini selalu seimbang, artinya jarak dari Root Node ke seluruh Leaf Node selalu sama. Kompleksitas pencarian pada B-Tree adalah $O(\log N)$.

               [ 50 ]
             /        \
      [ 20 | 35 ]     [ 70 | 85 ]
      /    |    \     /    |    \
   10,15 22,30 40,48 55,60 75,80 90,99

Keunggulan B-Tree Index

Mendukung Operasi Pencarian Rentang (Range Queries): Sangat efektif untuk query yang menggunakan operator >, <, BETWEEN, LIKE 'abc%'.
Mendukung Pengurutan Data (ORDER BY): Karena data di Leaf Node tersimpan secara terurut, operasi ORDER BY pada kolom berindeks B-Tree sangat cepat.
Mendukung Prefix Matching: Dapat digunakan untuk pencarian partial match pada indeks komposit (kombinasi beberapa kolom).

3. Hash Index

Hash Index menggunakan struktur data Hash Table dan fungsi hashing (Hash Function) untuk memetakan nilai kolom langsung ke lokasi alamat data.

Cara Kerja Hash Index

Ketika baris baru dimasukkan, nilai kolom yang diindeks dimasukkan ke dalam fungsi hash.
Fungsi hash menghasilkan nilai numerik (hash code) yang menunjuk ke lokasi memori atau bucket.
Saat query dilakukan, database cukup menghitung hash code dari kata kunci pencarian dan langsung menuju lokasi data tersebut.

Kompleksitas rata-rata untuk pencarian ekualitas pada Hash Index adalah $O(1)$ (konstan).

Input Key ("Budi") ---> [ Hash Function ] ---> Hash Code (0x0F) ---> Pointer ke Row #42

Keunggulan & Keterbatasan Hash Index

Keunggulan:

Sangat Cepat untuk Exact Match: Pencarian dengan operator sama dengan (WHERE email = 'user@example.com') berjalan dalam waktu konstan.

Keterbatasan:

Tidak Mendukung Range Query: Karena nilai hash dihasilkan secara acak/teracak (pseudo-random), urutan fisik data tidak mencerminkan nilai data. Query seperti WHERE umur > 25 tidak bisa memanfaatkan Hash Index.
Tidak Mendukung Pengurutan (ORDER BY): Hash index tidak menyimpan data secara terurut.
Tidak Bisa Partial Index: Pada composite index, Anda harus menggunakan seluruh kolom dalam pencarian; pencarian sebagian kolom tidak akan bekerja.

4. Tabel Perbandingan B-Tree vs Hash Index

Fitur / Karakteristik	B-Tree Index	Hash Index
Struktur Data	Self-balancing Tree	Hash Table
Kompleksitas Pencarian	$O(\log N)$	$O(1)$ (Rata-rata)
Exact Match (`=`)	Sangat Baik	Sangat Cepat
Range Query (`>`, `<`, `BETWEEN`)	✅ Ya	❌ Tidak
Pengurutan (`ORDER BY`)	✅ Ya	❌ Tidak
Pencarian Prefix (`LIKE 'abc%'`)	✅ Ya	❌ Tidak
Penggunaan Default	PostgreSQL, MySQL (InnoDB)	Memory Engine, Redis (In-Memory)

5. Best Practices Pembuatan Index

Meskipun index mempercepat pencarian data (SELECT), setiap index menambah beban saat proses penulisan data (INSERT, UPDATE, DELETE) karena index harus diperbarui secara otomatis.

Berikut beberapa praktik terbaik dalam mengelola index:

Jangan Indeks Semua Kolom: Indeks hanya kolom yang sering digunakan dalam klausa WHERE, JOIN, ORDER BY, dan GROUP BY.
Perhatikan Kardinalitas Kolom: Indeks sangat efektif pada kolom dengan kardinalitas tinggi (banyak nilai unik, seperti email, user_id). Hindari membuat indeks pada kolom kardinalitas rendah seperti jenis_kelamin (P/L).
Gunakan Composite Index dengan Urutan yang Benar: Letakkan kolom yang paling sering difilter atau paling spesifik di posisi paling depan pada indeks gabungan.
Hapus Index yang Tidak Terpakai: Lakukan audit index secara berkala untuk menghapus unused index yang membebani performa penulisan.

Kesimpulan

Memahami perbedaan antara B-Tree dan Hash Index sangat penting dalam mendesain skema database yang efisien. Gunakan B-Tree untuk kebutuhan pencarian umum, rentang nilai, dan pengurutan. Gunakan Hash Index jika Anda hanya membutuhkan pencarian nilai persis (exact key-value lookup) yang ultra-cepat.