Cách Index trong Cơ sở dữ liệu Hoạt động
Index là gì?
📚Without Index — Full Table Scan
P1
→P2
→P3
→...
→P6
→P7
Read every page sequentially until you find what you need — like flipping through an entire book page by page.
7 pages checkedO(n)
📖With Index — Direct Lookup
INDEX
→P7
Look up the term in the index at the back of the book, then jump directly to the right page.
1 page checkedO(log n)
🎯
What is an Index?
A separate data structure that stores a sorted copy of selected columns alongside pointers to the actual rows.
⚡
Why use Indexes?
Without an index, the database must scan every row. With one, it traverses a tree — reducing reads from billions to ~5.
⚙️
How does it work?
A B-tree keeps data sorted. Each level narrows the search range by following the correct branch — like a decision tree.
Trực quan hóa
Xem cả hai phương pháp cạnh nhau cho cùng một truy vấn (Query) — so sánh số dòng (Rows) mà quét toàn bảng (Full Table Scan) phải kiểm tra với số nút (Nodes) mà B-tree cần duyệt:
0 / 13
Without Index — Full Table Scan
SELECT * FROM users WHERE email = 'alice@mail.com'
| # | Name | |
|---|---|---|
| 1 | Emma | emma@mail.com |
| 2 | Liam | liam@mail.com |
| 3 | Sophia | sophia@mail.com |
| 4 | Noah | noah@mail.com |
| 5 | Olivia | olivia@mail.com |
| 6 | James | james@mail.com |
| 7 | Alice | alice@mail.com |
| 8 | Bob | bob@mail.com |
| 9 | Carol | carol@mail.com |
| 10 | Dave | dave@mail.com |
With B-tree Index — Tree Traversal
SELECT * FROM users WHERE email = 'alice@mail.com'
[ dave | sophia ]
┌─────────────┼─────────────┐
[ bob ]
[ james ]
[ noah ]
┌────┼────┐
alice, bob
carol, dave
emma, james
Waiting for table scan to progress...
Các loại Index
🌳
B-tree
Default in most databases. Sorted structure supports range queries.
WHERE, ORDER BY, JOIN#️⃣
Hash
O(1) exact match lookup using a hash table.
Equality only (=)📊
Bitmap
Bit arrays for low-cardinality columns.
Data warehousing🔗
Composite
Index on multiple columns — column order matters.
Multi-column WHERE📦
Covering
Includes all queried columns — avoids table lookups entirely.
Index-only scans🔑
Unique
Enforces uniqueness on column values.
Primary keysChiến lược Quét Index (Index Scan Strategies)
Trình tối ưu hóa truy vấn (Query Optimizer) chọn giữa các chiến lược sau dựa trên ước tính chi phí:
Index SeekFastest
B-tree traversal to find specific rows directly.
Index ScanFast
Read the entire index in order. Faster than table scan when index covers the query.
Full Table ScanSlowest
Read every row sequentially. Sometimes faster than index when selecting most rows.
Điểm chính cần nhớ (Key Takeaways)
🐢
Without Index
Every row is checked sequentially — O(n) — painfully slow for large tables.
🚀
With B-tree Index
The tree narrows the search at each level — only a few nodes visited — O(log n).
⚖️
Trade-off
Indexes speed up reads but slow down writes — every INSERT/UPDATE/DELETE must update the index too.
💾
Storage Cost
Indexes consume additional disk space — typically 10-20% of table size.
🌲
B-tree Depth
For 1 billion rows with branching factor 100 → only ~4-5 levels needed.
Khi nào nên tạo Index và Khi nào KHÔNG nên
✅ When to Index
✓🔍Columns frequently used in WHERE clauses
✓🔗Columns used in JOIN conditions
✓📊Columns used in ORDER BY or GROUP BY
✓📈High cardinality columns (many distinct values)
❌ When NOT to Index
✗📭Tables with few rows (scan is fast enough)
✗🔄Low cardinality (e.g. boolean — index won't help)
✗✍️Heavy write workloads (each write updates every index)
✗🔁Frequently updated columns (maintenance cost is high)
B-tree Index hoạt động như thế nào (Tìm hiểu sâu)
Loại Index phổ biến nhất là B-tree (Cây cân bằng - Balanced Tree). Nó giữ dữ liệu được sắp xếp và cho phép tìm kiếm (Search), chèn (Insertion) và xóa (Deletion) trong thời gian O(log n):
- Nút gốc (Root Node) chứa các khóa (Keys) chia dữ liệu thành các khoảng (Ranges)
- Mỗi nút con (Child Node) thu hẹp khoảng tiếp theo
- Các nút lá (Leaf Nodes) chứa giá trị thực tế và con trỏ đến dòng (Row Pointers)
- Cây luôn cân bằng (Balanced) — tất cả các nút lá đều ở cùng độ sâu
Ví dụ, tìm kiếm trong 1 tỷ dòng với hệ số phân nhánh (Branching Factor) 100 chỉ cần ~4-5 tầng (Levels) — tức là 4-5 lần đọc đĩa (Disk Reads) thay vì 1 tỷ lần.
Tìm hiểu thêm
Đọc lý thuyết đầy đủ tại Thiết kế Cơ sở dữ liệu > Index.