B-tree, composite và covering index hoạt động ra sao, và quy tắc leftmost-prefix là gì?

Question

IT Interview Practice · Accepted Answer

Index của InnoDB là **B+tree**: cây cân bằng nơi mọi leaf nằm cùng độ sâu và các leaf được liên kết để range scan nhanh. Một lần tra cứu là O(log n) — chỉ vài lần đọc page ngay cả trên table khổng lồ.

## Composite index và leftmost prefix

Một composite index `(a, b, c)` sắp xếp row theo `a`, rồi `b`, rồi `c`. Bạn chỉ dùng được nó cho một **leftmost prefix** của các cột: `a`, `(a, b)`, hoặc `(a, b, c)` — nhưng **không** dùng được `b` đơn lẻ hay `(b, c)`, vì các cột đó chưa được sắp xếp cho tới khi `a` được cố định.

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

-- DÙNG index (leftmost prefix, range trên cột cuối)
SELECT * FROM events
WHERE user_id = 7 AND status = 'open' AND created_at > '2026-01-01';

-- KHÔNG dùng: bỏ qua cột trái nhất
SELECT * FROM events WHERE status = 'open';
```

Xếp cột theo độ chọn lọc cao / equality trước, cột range để cuối: một khi gặp range (`>`, `BETWEEN`), các cột sau nó không thể dùng để seek.

## Covering index

Nếu một index chứa **mọi cột mà truy vấn đọc**, InnoDB trả lời chỉ từ index — không phải quay lại clustered index. EXPLAIN hiện `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, không tra cứu clustered index
```

## Tại sao điều này quan trọng

Composite và covering index là cách bạn biến một truy vấn nhiều điều kiện chậm thành một lần index seek duy nhất. Xếp sai thứ tự cột — hoặc kỳ vọng một truy vấn trên cột thứ hai dùng được index — là lý do phổ biến nhất khiến một index "đã tồn tại" vẫn không được dùng.

Composite index và leftmost prefix

Covering index

Tại sao điều này quan trọng

Câu hỏi liên quan