Bagaimana indeks B-tree, komposit, dan covering berfungsi, dan apakah peraturan leftmost-prefix?

Question

IT Interview Practice · Accepted Answer

Indeks InnoDB ialah **B+tree**: pokok seimbang di mana setiap daun berada pada kedalaman yang sama dan daun-daun berpaut untuk imbasan julat yang pantas. Satu carian ialah O(log n) — hanya segelintir bacaan halaman walaupun pada jadual yang sangat besar.

## Indeks komposit dan leftmost prefix

Indeks komposit `(a, b, c)` mengisih baris mengikut `a`, kemudian `b`, kemudian `c`. Anda hanya boleh menggunakannya untuk **awalan paling kiri (leftmost prefix)** bagi lajur-lajur tersebut: `a`, `(a, b)`, atau `(a, b, c)` — tetapi **bukan** `b` sahaja atau `(b, c)`, kerana lajur-lajur itu tidak tersusun sehingga `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';
```

Susun lajur mengikut paling selektif / kesamaan (equality) dahulu, lajur julat (range) terakhir: sebaik sahaja anda menemui julat (`>`, `BETWEEN`), lajur selepasnya tidak boleh digunakan untuk mencari (seeking).

## Covering index

Jika satu indeks mengandungi **setiap lajur yang dibaca oleh pertanyaan**, InnoDB menjawab daripada indeks sahaja — tiada perjalanan kembali ke clustered index. EXPLAIN menunjukkan `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 ia penting

Indeks komposit dan covering ialah cara anda menukar pertanyaan berbilang syarat yang perlahan menjadi satu carian indeks (index seek) tunggal. Menyalahkan susunan lajur — atau mengharapkan pertanyaan pada lajur kedua untuk menggunakan indeks — ialah sebab paling biasa mengapa indeks yang "wujud" masih tidak digunakan.

Indeks komposit dan leftmost prefix

Covering index

Mengapa ia penting

Soalan berkaitan