---
title: "Database Indexing: Mô hình tư duy 'Tủ Danh mục Thư viện'"
description: "Tại sao thêm index lại làm query nhanh gấp 100 lần? Hướng dẫn chuyên sâu về B-Tree, compound index, covering index và các câu truy vấn giết chết database."
pubDate: "2023-05-25"
lang: "vi"
slug: "database-indexing-b-tree"
url: "https://hoangyell.com/vi/database-indexing-b-tree/"
author: "HoangYell"
translation_en: "https://hoangyell.com/database-indexing-b-tree/"
categories: ["System Design"]
tags: ["databases", "sql", "performance", "postgresql"]
heroImage: "https://raw.githubusercontent.com/HoangGeek/store/main/webp/photo-1502082553048-f009c37129b9.webp"
---

Một câu query mất 30 giây trở thành 50 mili giây sau khi thêm một index.

Không thay đổi code. Không thêm phần cứng. Một dòng SQL.

Hiểu được *tại sao* điều đó xảy ra - và khi nào nó không hiệu quả - phân biệt những kỹ sư "thêm index khi chậm" với những kỹ sư thiết kế data model không bao giờ chậm.

Đây là **Hướng dẫn chuyên sâu** về Database Indexing.

***

## Phần 1: Nền tảng (Mô hình tư duy)

### Không có Index = Đọc từng trang một

Tưởng tượng một thư viện có 1,000,000 cuốn sách. Bạn muốn tìm "Truyện Kiều."

**Không có danh mục**: Bạn đi qua từng kệ sách, đọc gáy từng cuốn, cho đến khi tìm thấy. Trường hợp tồi nhất, bạn kiểm tra cả 1,000,000 cuốn. (**Full Table Scan**).

**Có Tủ Danh mục (Index)**: Bạn đến ngăn "T" → tìm "Truyện Kiều" → nó ghi "Kệ 42, Hàng 7". Bạn đi thẳng đến đó. **3 bước thay vì 1,000,000.**

Trong database, index là **Tủ Danh mục**. Nó lưu các giá trị cột trong cấu trúc được sắp xếp (một **B-Tree**) với con trỏ trỏ đến dòng thực tế trên đĩa.

### B-Tree (Index được lưu như thế nào bên trong)

B-Tree là cây cân bằng, được sắp xếp. Hãy nghĩ như tìm kiếm nhị phân nhưng mạnh hơn nhiều.

```markdy
scene type=tree width=1100 height=650
theme: light=doodle dark=nebula

database RootPage "Trang Gốc [1, 5, 10, 50]"
database InternalPage "Trang Nhánh [5, 6, 7, 8]"
database LeafPage "Block Lá [ID: 7 -> Ptr 482]" focal=true
storage DiskRow "Dữ liệu Hàng Disk Block 482"

beat tree_traversal "1. Duyệt Cây B-Tree Cân bằng O(log N)" {
  show $nodes stagger=50ms
  RootPage -> InternalPage "đánh giá 5 <= 7 < 10"
  InternalPage -> LeafPage "tìm nhị phân chính xác khóa 7"
  LeafPage -> DiskRow "tra cứu trực tiếp con trỏ đĩa (0.1ms)"
  glow LeafPage color=#22c55e
}

player:
    playback:
      loop true
    controls:
      speed true
      speeds "0.25"
      fullscreen true
      gif true
      theme true
    interaction:
      zoom true
      pan true
      click_to_play true
      double_click_to_reset true
      keyboard false
    chrome:
      badge true
      progress none
```

*   **Đọc**: O(log N). Tìm một bản ghi trong 1 tỉ hàng: ~30 phép so sánh.
*   **Ghi**: Chậm hơn. Mỗi INSERT/UPDATE phải cập nhật cả cây index.

***

## Phần 2: Điều tra (Các loại Index)

### 1. Index Đơn cột

```sql
-- Chậm: Full Table Scan. Kiểm tra 1 triệu hàng.
SELECT * FROM orders WHERE customer_id = 42;

-- Thêm index:
CREATE INDEX idx_orders_customer ON orders (customer_id);

-- Giờ nhanh: B-Tree lookup. ~30 phép so sánh.
SELECT * FROM orders WHERE customer_id = 42;
```

### 2. Compound Index (Nhiều cột): Thứ tự rất quan trọng!

Compound index trên `(a, b, c)` giống như danh bạ điện thoại sắp xếp theo: Họ → Tên → Thành phố.

```sql
CREATE INDEX idx_orders_status_date ON orders (status, created_at);

-- ✅ Dùng được index (quy tắc tiền tố trái nhất)
SELECT * FROM orders WHERE status = 'paid';
SELECT * FROM orders WHERE status = 'paid' AND created_at > '2024-01-01';

-- ❌ KHÔNG dùng được index (bỏ qua cột đầu tiên)
SELECT * FROM orders WHERE created_at > '2024-01-01';
```

**Quy tắc Tiền tố Trái nhất**: Index trên `(a, b, c)` có thể dùng cho query trên `a`, `a+b`, hoặc `a+b+c`. **Không bao giờ** cho query chỉ bắt đầu với `b` hoặc `c`.

### 3. Covering Index (Index Hoàn hảo)

Covering index chứa TẤT CẢ các cột mà query cần. Database không bao giờ phải đụng đến các hàng thực tế.

```sql
-- Query cần: status, created_at, total_amount
SELECT status, created_at, total_amount FROM orders WHERE status = 'paid';

-- Covering Index: bao gồm cả 3 cột
CREATE INDEX idx_covering ON orders (status, created_at, total_amount);

-- Bản thân index đã có câu trả lời. Không đọc hàng nào của bảng!
```

***

## Phần 3: Chẩn đoán (Những Query Giết Database)

### `EXPLAIN ANALYZE` - Mắt thần của bạn

```sql
EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 42;
```

**Cần chú ý**:
*   `Seq Scan` → **Full Table Scan**. Thiếu index. 🔴
*   `Index Scan` → Dùng index để tìm hàng, rồi mới fetch chúng. 🟡
*   `Index Only Scan` → Dùng covering index. Không đụng đến bảng. 🟢

### Các mẫu Query vô hiệu hóa Index

```sql
-- ❌ Hàm ở vế trái: Index trên `created_at` bị BỎ QUA!
WHERE YEAR(created_at) = 2024
-- ✅ Sửa:
WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31'

-- ❌ Wildcard ở đầu: Index BỊ BỎ QUA (không thể sắp xếp theo tiền tố chưa biết)
WHERE email LIKE '%@gmail.com'
-- ✅ Sửa: Dùng full-text search, hoặc tiền tố:
WHERE email LIKE 'alice%'

-- ❌ Điều kiện OR trên cột khác nhau: Thường gây hai lần quét index
WHERE status = 'paid' OR customer_id = 42
-- ✅ Sửa: UNION
SELECT * FROM orders WHERE status = 'paid'
UNION
SELECT * FROM orders WHERE customer_id = 42
```

***

## Phần 4: Giải pháp (Chiến lược thiết kế Index)

### 1. Quy tắc "ESR" cho Compound Index

Xây Compound Index theo thứ tự: **E**quality (Bằng nhau) → **S**ort (Sắp xếp) → **R**ange (Phạm vi).

```sql
-- Query: Tìm đơn hàng 'paid', sắp xếp theo ngày, trong năm 2024
SELECT * FROM orders
WHERE status = 'paid'           -- Equality
ORDER BY created_at DESC        -- Sort
AND created_at > '2024-01-01'; -- Range

-- Index tốt nhất:
CREATE INDEX idx_esr ON orders (status, created_at);
--                               Equality  Sort+Range
```

### 2. Partial Index

Chỉ index những hàng bạn thực sự cần. Nhỏ hơn, nhanh hơn.

```sql
-- 99% đơn hàng là 'completed'. Bạn chỉ query 'pending'.
CREATE INDEX idx_pending ON orders (created_at)
WHERE status = 'pending';  -- Chỉ index 1% hàng thực sự quan trọng!
```

### 3. Tìm Index đang thiếu (PostgreSQL)

```sql
-- Bảng nào đang bị quét tuần tự nhiều (thiếu index!)
SELECT schemaname, tablename, seq_scan, idx_scan
FROM pg_stat_user_tables
WHERE seq_scan > idx_scan
ORDER BY seq_scan DESC;
```

***

## Mô hình tư duy chốt hạ

```
Full Table Scan -> Đọc từng cuốn sách trong thư viện.
B-Tree Index    -> Tủ Danh mục. Có sắp xếp. O(log N).
Compound Index  -> Danh bạ điện thoại: Họ → Tên → Thành phố.
Covering Index  -> Câu trả lời NẰM NGAY trong danh mục. Không cần ra kệ sách.

Leftmost Prefix -> Index (a,b,c) giúp query bắt đầu với 'a'. Không giúp với 'b' hay 'c'.
Seq Scan        -> 🔴 Thiếu index.
Index Only Scan -> 🟢 Covering index hoàn hảo.
```

**Quy tắc**:
*   Chạy `EXPLAIN ANALYZE` trước và sau khi thêm index.
*   Đừng thêm index bừa bãi - mỗi index làm chậm việc ghi.
*   Thiết kế cho **các query thường xuyên nhất** của bạn, không phải mọi query có thể có.