Index pada Database (BTree)
Wed. Dec 28th, 2022 09:13 PM5 mins read
Index pada Database (BTree)
Source: Bing Image Creator - Binary Tree in Programming

Mungkin ketika kuliah kita udah sering mendengar kata index pada database. Harusnya pada saat materi database dasar ada materi tentang index. Index pada database berguna untuk mempercepat pencarian data agar database tidak perlu melakukan full scan data. Awalnya memang ga bakal terasa efeknya. Apalagi ketika jumlah data yang disimpan masih sedikit. Dampaknya baru terasa ketika data yang disimpan sudah mulai besar dan terdapat pencarian menggunakan kolom yang tidak di-index sehingga database melakukan pencarian data dengan membaca keseluruhan data yang banyak dan tentu saja mengakibatkan proses pencariannya jadi sangat lambat. Disinilah index dibutuhkan.

Ada beberapa jenis index pada database, seperti B-tree, B+tree, Hash, Gist, GIN, dan lainnya. B-Tree dan B+Tree cocok untuk untuk pencarian menggunakan range value, Hash cocok untuk pencarian dengan equals, Gist cocok untuk tipe data yang kompleks, dan GIN cocok untuk pencarian dengan full-text. Tapi default type pada beberapa database seperti MySql dan PostgreSql adalah B-tree karena dianggap paling ideal untuk banyak kasus. B-tree ini artinya Balanced Tree, sesuai namanya ini menerapkan data struktur Tree. Kalau struktur data Tree rootnya tetap, sehingga worst case-nya dapat menghasilkan urutan data yang ga seimbang dengan kecepatan O(n). Sedangkan B-tree keseimbangannya dijaga dengan range tertentu agar proses pencarian lebih optimal dengan kecepatan O(log(n)). Penjelasan mengenai O(log(n)) bisa dibaca pada halaman Big O Notation. Oh ya, B-tree (Balanced Tree) dan B+tree (B Plus Tree) adalah 2 hal yang berbeda, walau memiliki nama yang mirip dan sama-sama menerapkan Tree data struktur. Tapi pada tulisan ini fokus gw hanyalah menggunakan index pada database saja. Kalau ingin mempelajari lebih dalam tentang B-tree bisa baca lebih lanjut di wikipedia.

By default, Primary Key dan Unique Key di-index otomatis oleh database (khusus MySql juga mengindex Foreign Key). Selain key itu, kita harus menetapkan Index Key secara terpisah pada kolom yang ingin diindex. Pada kolom yang diindex, pencarian akan lebih cepat karena datanya tersimpan terurut menggunakan Tree data struktur dengan kecepatan O(log(n)) jadi tidak perlu melakukan scan keseluruhan data yang banyak. Seperti melakukan pencarian kata pada kamus, semua kata disimpan secara terurut. Jadi ketika kita ingin mencari kata yang berawalan dengan huruf “F”, maka kita tinggal buka halaman yang berisi awalan “F”, bukan melakukan pencarian semua kata satu-persatu dari awal sampai akhir. Contohnya seperti tabel Person berikut ini:

Table Person

Id Name Gender Birth date Occupation
1 Yudi M 2002-01-01 Teacher
2 Rini F 1990-02-03 Police
3 Andi M 1995-03-03 Police
4 Joni M 2000-12-11 Teacher
5 Dodi M 1977-11-12 Student
CREATE INDEX person_name_index
ON person (name);

Misalkan table di atas memiliki kolom Id sebagai Primary Key, kolom Name sebagai Index Key, dan kolom Gender, Birth date, dan Occupation yang tidak terindex. Untuk mengecek apakah index-nya sudah ter-apply atau belum, bisa tambahkan keyword EXPLAIN di awal query:

EXPLAIN SELECT *
FROM person
WHERE name = 'Dodi';

Behind the scene, database juga menyimpan data Name dengan posisi terurut seperti ilustrasi tabel berikut:

Index Name

Id Name
3 Andi
5 Dodi
4 Joni
2 Rini
1 Yudi

Ketika kita melakukan pencarian menggunakan Name = “Dodi”, database tidak perlu melakukan pencarian semua nama untuk mendapatkan data dengan nama “Dodi”. Karena datanya sudah terurut meggunakan Tree data struktur, database bisa mendapatkan data “Dodi” dengan cepat. Perlu diperhatikan juga, where clause menggunakan LIKE keyword pada kolom yang di-index tidak akan dioptimasi, hanya menggunakan operator =, !=, <, dan > yang dioptimasi. Oh ya, ilustrasi tabel index di atas gw bikin secara abjad untuk mempermudah pemahaman. Behind the scene sebenarnya data disimpan secara Tree yang dicari dari root value, bukan dari abjad A-Z. Ilustrasinya bisa dicobain di link BTree visualization.

Composite Index

Selain single index, kita juga bisa menggunakan index menggunakan lebih dari satu kolom. Ini bagus untuk kasus yang sering melakukan pencarian terhadap lebih dari kolom dalam satu query sehingga lebih cepat daripada single index dengan data yang sangat banyak. Misalkan pada contoh berikut.

Table Person

Id Name Gender Birth date Occupation
1 Yudi M 2002-01-01 Teacher
2 Yudi M 1990-02-03 Police
3 Yudi M 1995-03-03 Police
4 Joni M 2000-12-11 Teacher
5 Joni M 1977-11-12 Student

Misalnya yang diindex pada tabel di atas adalah (Name, Birth date). Maka datanya akan diurutkan terlebih dahulu dari kolom Name, lalu kolom Birth date. Seperti ilustrasi index berikut:

CREATE INDEX person_name_birth_date_index
ON person (name, birth_date);

Index (Name, Birth date)

Id Name Birth date
5 Joni 1977-11-12
4 Joni 2000-12-11
2 Yudi 1990-02-03
3 Yudi 1995-03-03
1 Yudi 2002-01-01

Jadi ketika melakukan pencarian dengan Name = “Yudi” dan Birth date = “1995-03-03”, database akan mencari berdasarkan Name terlebih dahulu, lalu akan didapatkan 3 data dengan nama "Yudi". Lalu akan dicari lagi data "Yudi" dengan Birth date “1995-03-3” sehingga akan didapatkan data "Yudi" dengan id 3.

Perlu diperhatikan, ketika kita sudah menggunakan composite index (Name, Birth date), kita tidak perlu lagi menambahkan single index (Name) karena index kolom Name sudah tercover oleh composite index. Misalkan kita ingin melakukan query dengan kolom Name saja, tetap akan terindex lewat composite index di atas karena ditulis paling awal. Sedangkan apabila kita melakukan pencarian pada kolom Birth date saja tanpa menggunakan kolom Name, maka tidak akan tercover composite index di atas, karena Birth date ditulis setelah kolom Name. Sehingga pencarian menggunakan Birth date hanya akan tercover jika pencarian menggunakan query Birth date dan Name. Jika pencarian menggunakan query kolom Birth date saja juga sering dilakukan, maka perlu ditambahkan juga single index (Birth date).

Drawback

Selain mempercepat pencarian pada data besar, Index Key juga bisa berdampak pada performa database. Yaitu ketika sebuah tabel memiliki terlalu banyak Index. Perlu diperhatikan, saat melakukan perubahan data, database juga akan mengurutkan kembali data yang baru dimasukkan pada index. Sehingga jika terlalu banyak index, maka proses insertion, deletion dan update data akan melambat karena selain melakukan perubahan data kolom, database juga akan mengurutkan kembali data pada index. Jadi pastikan kolom yang diindex adalah kolom yang benar-benar sering dilakukan filter data. Oleh karena itu, menggunakan index pada kolom yang sering mengalami perubahan harus dihindari, karena semakin sering data index berubah, urutan data index juga akan sering berubah sehingga ga efisien. Selain itu, penggunaan index juga butuh storage di harddisk untuk menyimpan data index.

PostgreSql vs MySql

PostgreSql dan MySql melakukan pendekatan yang berbeda saat menyimpan index. Pada PostgreSql, setiap index juga menyimpan referensi pada data dari kolom-kolom lainnya. Jadi misalkan kita ingin melakukan query dengan kolom Name di atas, PostgreSql langsung menampilkan data dari kolom-kolom lainnya yang berhubungan dengan index yang kita cari sehingga sedikit lebih cepat. Tapi saat melakukan perubahan, PostgreSql juga akan menginformasikannya pada index-index pada tabel tersebut bahwa ada referensi kolom yang berubah sehingga sedikit lebih lambat. Sedangkan pada MySql, setiap index hanya mereferensikan data dari kolom Primary Key saja. Jadi misalkan saat melakukan pencarian dengan kolom Name di atas, MySql mengambil Primary Key dari data tersebut, lalu dari Primary Key itu akan dicari lagi data kolom-kolom lainnya sehingga sedikit lebih lambat. Pada saat melakukan perubahan data, MySql tidak perlu melakukan perubahan referensi pada semua index pada tabel tersebut karena index pada MySql hanya mereferensikan data lewat Primary Key saja sehingga dalam hal ini MySql sedikit lebih cepat.

Verdict

Index sangat berguna untuk mempercepat pencarian data. Index hanya efisien pada tabel yang datanya banyak, sedangkan jika datanya masih sedikit sebaiknya tidak usah diindex. B-tree adalah jenis index yang umum digunakan pada database karena dianggap paling cocok untuk sebagian besar kasus dengan kecepatan O(log(n)). Selain Single Index, kita juga bisa menerapkan Composite Index untuk kasus dengan lebih dari satu kolom yang sering dicari secara bersamaan. Composite Index hanya efisien jika semua kolom pada Composite Index atau sebagian kolom yang ditulis di awal digunakan sebagai filter pencarian, jadi kolom yang ditulis belakangan tidak akan terindex jika digunakan sendirian. Primary Key dan Unique Key by default akan diindex, jadi tidak perlu dibuatkan index secara eksplisit. Index juga akan mengurangi performa jika terlalu banyak karena setiap ada proses perubahan data pada index juga akan diurutkan ulang. Sehingga kolom yang diindex sebaiknya hanya yang perlu-perlu saja.

© 2024 · Ferry Suhandri