Bagaimana cara kerja B-tree, composite, dan covering index, dan apa itu leftmost-prefix rule?

Question

IT Interview Practice · Accepted Answer

Index InnoDB adalah **B+tree**: tree yang seimbang di mana setiap daun berada pada kedalaman yang sama dan daun-daun terhubung untuk range scan yang cepat. Sebuah lookup adalah O(log n) — hanya segelintir pembacaan page bahkan pada tabel yang sangat besar.

## Composite index dan leftmost prefix

Sebuah composite index `(a, b, c)` mengurutkan baris berdasarkan `a`, lalu `b`, lalu `c`. Anda hanya dapat menggunakannya untuk sebuah **leftmost prefix** dari kolom-kolomnya: `a`, `(a, b)`, atau `(a, b, c)` — tetapi **bukan** `b` saja atau `(b, c)`, karena kolom-kolom itu tidak terurut sampai `a` ditetapkan.

```sql
CREATE INDEX idx_abc ON events (user_id, status, created_at);

-- USES the index (leftmost prefix, range on the last column)
SELECT * FROM events
WHERE user_id = 7 AND status = 'open' AND created_at > '2026-01-01';

-- Does NOT use it: skips the leftmost column
SELECT * FROM events WHERE status = 'open';
```

Urutkan kolom dari yang paling selektif / equality dulu, dan kolom range di akhir: begitu Anda mencapai sebuah range (`>`, `BETWEEN`), kolom setelahnya tidak dapat digunakan untuk seeking.

## Covering index

Jika sebuah index berisi **setiap kolom yang dibaca query**, InnoDB menjawab dari index saja — tanpa kembali ke clustered index. EXPLAIN menampilkan `Using index`.

```sql
CREATE INDEX idx_cover ON events (user_id, status, id);

EXPLAIN SELECT id FROM events WHERE user_id = 7 AND status = 'open';
-- Extra: Using index      <- covering, no clustered-index lookup
```

## Mengapa ini penting

Composite dan covering index adalah cara Anda mengubah query multi-kondisi yang lambat menjadi sebuah index seek tunggal. Salah urutan kolom — atau mengharapkan sebuah query pada kolom kedua menggunakan index — adalah alasan paling umum mengapa sebuah index yang "ada" tetap tidak digunakan.

Composite index dan leftmost prefix

Covering index

Mengapa ini penting

Pertanyaan terkait