KAL
Menu

Dasar Indeks

Model B-tree, clustered index InnoDB, dan perbedaan indeks clustered dengan secondary.

Daftar isi

Indeks adalah struktur terurut yang dibuat terpisah dari isi tabel, sehingga server dapat menemukan baris tertentu tanpa membaca seluruh tabel. Topik ini membahas model B-tree yang menjadi bentuk indeks InnoDB, peran clustered index sebagai wujud penyimpanan tabel itu sendiri, dan perbedaan pencarian melalui secondary index dengan pencarian melalui clustered index. Latihan memakai basis data perpustakaan dengan 100000 baris peminjaman, dan setiap perilaku dibuktikan dengan keluaran nyata dari server MySQL 8.0. Setelah topik ini, sebuah query dapat dinilai dari jumlah pohon indeks yang harus dikunjunginya.

Data latihan#

Berkas berikut membuat ulang basis data perpustakaan_indeks dari nol. Tabel anggota berisi 2500 baris, tabel buku berisi 500 baris, dan tabel peminjaman berisi 100000 baris dengan pembagian yang rapi, yaitu setiap anggota memiliki tepat 40 peminjaman. Kolom anggota_id menerima nilai (n MOD 2500) + 1, sehingga peminjaman satu anggota tersebar di seluruh tabel dan tidak berderet pada baris yang berdekatan. Indeks secondary idx_anggota dibuat setelah data dimuat, lalu ANALYZE TABLE memperbarui statistik setiap tabel.

sql skema-indeks-dasar.sql 
-- tidak-dijalankan
-- Skema basis data latihan "perpustakaan_indeks" untuk topik dasar indeks.
-- Menjalankan ulang berkas ini selalu menghasilkan isi yang sama.

DROP DATABASE IF EXISTS perpustakaan_indeks;
CREATE DATABASE perpustakaan_indeks;
USE perpustakaan_indeks;

SET SESSION cte_max_recursion_depth = 1000000;

CREATE TABLE anggota (
  anggota_id INT UNSIGNED PRIMARY KEY AUTO_INCREMENT,
  nama VARCHAR(30) NOT NULL
);

CREATE TABLE buku (
  buku_id INT UNSIGNED PRIMARY KEY AUTO_INCREMENT,
  judul VARCHAR(60) NOT NULL
);

CREATE TABLE peminjaman (
  peminjaman_id INT UNSIGNED PRIMARY KEY AUTO_INCREMENT,
  anggota_id INT UNSIGNED NOT NULL,
  buku_id INT UNSIGNED NOT NULL,
  tanggal_pinjam DATE NOT NULL,
  status VARCHAR(10) NOT NULL
);

INSERT INTO anggota (nama)
WITH RECURSIVE urut AS (
  SELECT 1 AS n
  UNION ALL
  SELECT n + 1 FROM urut WHERE n < 2500
)
SELECT CONCAT('Anggota ', n) FROM urut;

INSERT INTO buku (judul)
WITH RECURSIVE urut AS (
  SELECT 1 AS n
  UNION ALL
  SELECT n + 1 FROM urut WHERE n < 500
)
SELECT CONCAT('Buku ', n) FROM urut;

INSERT INTO peminjaman (anggota_id, buku_id, tanggal_pinjam, status)
WITH RECURSIVE urut AS (
  SELECT 1 AS n
  UNION ALL
  SELECT n + 1 FROM urut WHERE n < 100000
)
SELECT
  (n MOD 2500) + 1,
  (n MOD 500) + 1,
  DATE_ADD('2024-01-01', INTERVAL (n MOD 730) DAY),
  ELT((n MOD 3) + 1, 'dipinjam', 'kembali', 'terlambat')
FROM urut;

CREATE INDEX idx_anggota ON peminjaman (anggota_id);

ANALYZE TABLE anggota;
ANALYZE TABLE buku;
ANALYZE TABLE peminjaman;
bash 
# membuat ulang basis data latihan beserta statistiknya
mysql -t -u root < skema-indeks-dasar.sql
text Keluaran 
+-----------------------------+---------+----------+----------+
| Table                       | Op      | Msg_type | Msg_text |
+-----------------------------+---------+----------+----------+
| perpustakaan_indeks.anggota | analyze | status   | OK       |
+-----------------------------+---------+----------+----------+
+--------------------------+---------+----------+----------+
| Table                    | Op      | Msg_type | Msg_text |
+--------------------------+---------+----------+----------+
| perpustakaan_indeks.buku | analyze | status   | OK       |
+--------------------------+---------+----------+----------+
+--------------------------------+---------+----------+----------+
| Table                          | Op      | Msg_type | Msg_text |
+--------------------------------+---------+----------+----------+
| perpustakaan_indeks.peminjaman | analyze | status   | OK       |
+--------------------------------+---------+----------+----------+

Setiap tabel menjawab dengan satu baris status OK, yang berarti statistiknya sudah diperbarui. Pembaruan ini penting karena optimizer mengambil keputusan dari statistik indeks, dan statistik yang basi membuat perkiraan pada EXPLAIN menyimpang.

Struktur B-tree pada indeks#

Indeks InnoDB berbentuk B-tree, yaitu pohon seimbang yang menyimpan kunci terurut di dalam halaman berukuran tetap. Pencarian satu nilai dimulai dari akar, lalu menyusuri satu cabang sampai daun, sehingga jumlah halaman yang dibaca tumbuh sebanding dengan logaritma jumlah baris, bukan dengan jumlah barisnya sendiri. Biaya pencariannya dapat dinyatakan sebagai O(log⁡n)O(\log n), sedangkan pemindaian seluruh tabel berbiaya O(n)O(n). Pada tabel seratus ribu baris, pencarian melalui B-tree biasanya hanya menyentuh tiga sampai empat halaman.

Tabel peminjaman pada latihan ini memuat dua B-tree, yaitu clustered index pada PRIMARY dan secondary index idx_anggota. Gambar berikut memperlihatkan isi daun masing-masing pohon secara berdampingan, sehingga keduanya dapat dibandingkan pada kunci yang sama.

Clustered index (PRIMARY)peminjaman_id41 baris lengkap42 baris lengkap43 baris lengkap2541 baris lengkap2542 baris lengkap2543 baris lengkapDaunnya adalah baris tabel itu sendiri.Secondary index idx_anggotaanggota_id42, 4142, 254143, 4244, 145, 2baris dicari lewat peminjaman_idDaunnya berisi kunci plus peminjaman_id.
Dua B-tree pada tabel peminjaman

Kedua pohon menyimpan kunci terurut, tetapi isinya berbeda. Perbedaan itu menentukan berapa banyak langkah yang dibutuhkan untuk mendapatkan satu baris, dan itulah yang dibuktikan pada dua bagian berikutnya.

Clustered index sebagai wujud tabel#

InnoDB menyimpan baris tabel di dalam daun sebuah B-tree yang kuncinya adalah primary key. Struktur inilah yang disebut clustered index, sehingga pada InnoDB istilah tabel dan indeks PRIMARY menunjuk struktur yang sama. Baris yang peminjaman_id-nya berdekatan tersimpan pada halaman yang berdekatan, dan pembacaan tabel mengikuti urutan kuncinya. Perintah berikut membaca lima baris pertama tanpa ORDER BY.

bash 
# lima baris pertama tanpa permintaan urutan
mysql -u root perpustakaan_indeks -t -e "SELECT peminjaman_id, anggota_id, buku_id, tanggal_pinjam, status FROM peminjaman LIMIT 5;"
text Keluaran 
+---------------+------------+---------+----------------+-----------+
| peminjaman_id | anggota_id | buku_id | tanggal_pinjam | status    |
+---------------+------------+---------+----------------+-----------+
|             1 |          2 |       2 | 2024-01-02     | kembali   |
|             2 |          3 |       3 | 2024-01-03     | terlambat |
|             3 |          4 |       4 | 2024-01-04     | dipinjam  |
|             4 |          5 |       5 | 2024-01-05     | kembali   |
|             5 |          6 |       6 | 2024-01-06     | terlambat |
+---------------+------------+---------+----------------+-----------+

Keluaran menunjukkan peminjaman_id 1 sampai 5 dalam keadaan terurut, meskipun query tidak meminta urutan apa pun. InnoDB membaca tabel dengan menyusuri daun clustered index dari awal ke akhir, sehingga urutan keluaran mengikuti urutan penyimpanannya. Pola ini juga menjelaskan kecocokan primary key berurutan seperti AUTO_INCREMENT dengan InnoDB, karena sisipan baru selalu jatuh di ujung kanan pohon. Primary key yang nilainya acak sebaliknya memaksa sisipan mendarat di tengah halaman yang sudah penuh dan memicu pemecahan halaman.

Secondary index dan rute dua pohon#

Secondary index adalah B-tree kedua yang daunnya menyimpan nilai kolom terindeks ditambah primary key dari setiap baris yang memuat nilai tersebut. Pada idx_anggota, satu entri daun adalah pasangan (anggota_id, peminjaman_id), misalnya (42, 41). Karena itu, pencarian melalui secondary index selalu terdiri atas dua langkah, yaitu menemukan peminjaman_id pada secondary index, lalu mencari baris lengkapnya pada clustered index. Inilah sebabnya satu pencarian dapat mengunjungi dua pohon. Alasan yang sama membuat terlalu banyak indeks memberatkan penulisan, karena setiap INSERT harus memperbarui banyak pohon sekaligus.

Query berikut mengambil peminjaman_id milik anggota 42 tanpa ORDER BY.

bash 
# peminjaman milik satu anggota melalui secondary index
mysql -u root perpustakaan_indeks -t -e "SELECT peminjaman_id FROM peminjaman WHERE anggota_id = 42;"
text Keluaran 
+---------------+
| peminjaman_id |
+---------------+
|            41 |
|          2541 |
|          5041 |
|          7541 |
|         10041 |
|         12541 |
|         15041 |
|         17541 |
|         20041 |
|         22541 |
|         25041 |
|         27541 |
|         30041 |
|         32541 |
|         35041 |
|         37541 |
|         40041 |
|         42541 |
|         45041 |
|         47541 |
|         50041 |
|         52541 |
|         55041 |
|         57541 |
|         60041 |
|         62541 |
|         65041 |
|         67541 |
|         70041 |
|         72541 |
|         75041 |
|         77541 |
|         80041 |
|         82541 |
|         85041 |
|         87541 |
|         90041 |
|         92541 |
|         95041 |
|         97541 |
+---------------+

Keluaran berisi 40 baris, sesuai jumlah peminjaman per anggota pada data latihan, dan nilainya naik dengan pola 41, 2541, 5041, dan seterusnya dengan selisih 2500. Pola itu muncul karena entri secondary index diurutkan menurut pasangan (anggota_id, peminjaman_id), sehingga entri milik anggota 42 tersusun berdasarkan peminjaman_id. Server membaca entri-entri itu secara berurutan tanpa pengurutan tambahan. Apabila query juga meminta kolom lain, setiap peminjaman_id yang ditemukan dipakai untuk satu pencarian tambahan pada clustered index.

Melihat indeks yang terpasang#

Daftar indeks sebuah basis data dapat dibaca dari tabel INFORMATION_SCHEMA.STATISTICS. Query berikut menampilkan indeks milik basis data latihan beserta kolom kuncinya.

bash 
# daftar indeks pada basis data latihan
mysql -u root perpustakaan_indeks -t -e "SELECT TABLE_NAME, INDEX_NAME, NON_UNIQUE, SEQ_IN_INDEX, COLUMN_NAME FROM information_schema.STATISTICS WHERE TABLE_SCHEMA = 'perpustakaan_indeks' ORDER BY TABLE_NAME, INDEX_NAME, SEQ_IN_INDEX;"
text Keluaran 
+------------+-------------+------------+--------------+---------------+
| TABLE_NAME | INDEX_NAME  | NON_UNIQUE | SEQ_IN_INDEX | COLUMN_NAME   |
+------------+-------------+------------+--------------+---------------+
| anggota    | PRIMARY     |          0 |            1 | anggota_id    |
| buku       | PRIMARY     |          0 |            1 | buku_id       |
| peminjaman | idx_anggota |          1 |            1 | anggota_id    |
| peminjaman | PRIMARY     |          0 |            1 | peminjaman_id |
+------------+-------------+------------+--------------+---------------+

Kolom NON_UNIQUE bernilai 0 untuk indeks unik seperti PRIMARY, sedangkan nilai 1 menandakan indeks yang mengizinkan duplikasi. Kolom SEQ_IN_INDEX menunjukkan posisi kolom di dalam kunci indeks, yang menjadi penting pada indeks multi-kolom. Klien mysql juga menyediakan pernyataan SHOW INDEX FROM peminjaman yang informasinya setara, tetapi kolom Cardinality pada keluaran pernyataan itu berupa perkiraan sehingga angkanya dapat berubah antar eksekusi.

Kesalahan umum#

Kesalahan pertama adalah menganggap secondary index menyimpan salinan baris. Daun secondary index hanya memuat kolom kunci dan primary key, sehingga kolom lain tetap harus diambil dari clustered index. Kesalahan kedua adalah memakai primary key yang nilainya acak, misalnya UUID, untuk tabel berukuran besar, karena sisipan yang selalu mendarat di posisi acak memecah halaman clustered index dan memperbesar ukurannya. Kesalahan ketiga adalah mengandalkan urutan keluaran tanpa ORDER BY. Urutan pada latihan ini muncul karena InnoDB membaca halaman clustered index secara berurutan, sehingga apabila urutan memang penting bagi aplikasi, ORDER BY tetap wajib ditulis.

Ringkasan#

  • Indeks InnoDB berbentuk B-tree, sehingga pencarian satu nilai berbiaya O(log⁡n)O(\log n) dan tidak lagi sebanding dengan jumlah baris.
  • Clustered index InnoDB adalah tabel itu sendiri, yaitu daun B-tree yang berisi baris lengkap dan terurut menurut primary key.
  • Secondary index menyimpan kunci plus primary key, sehingga pencarian melaluinya melewati dua pohon, yaitu secondary index terlebih dahulu, baru clustered index.
  • Daftar indeks dapat dilihat dari INFORMATION_SCHEMA.STATISTICS, dengan NON_UNIQUE dan SEQ_IN_INDEX sebagai kolom yang menjelaskan sifat dan susunan kuncinya.

Referensi#