Database Indexing: B-Tree vs Hash

66%

Quảng cáo • Advertisement

📢 Sponsor Ad

Google AdSense

🎯 Mục tiêu bài học

Hiểu sâu về B-Tree để tối ưu câu truy vấn (Query Optimization). Tại sao đánh Index lại làm chậm ghi?

1. Cấu trúc dữ liệu: B+Tree (Mặc định của MySQL InnoDB)

Khác với Binary Tree (mỗi nút 2 con), B-Tree là cây đa nhánh (N con).

Root/Internal Nodes: Chỉ chứa Key (để dẫn đường). Không chứa Data. -> Chứa được rất nhiều Key trong 1 Page 4KB. Cây thường rất thấp (chiều cao 3-4 lớp).
Leaf Nodes (Lá): Chứa toàn bộ Data thật. Các lá nối với nhau thành Danh sách liên kết (Linked List). -> Cực tốt cho việc quét theo dải (Range Scan: WHERE age > 20).

🖼️ Cấu trúc B+Tree (Bậc 3)

           [ 15  |  30 ]  <-- Root (Chỉ chứa Key)
          /      |         [ 5 | 10 ] [ 20 | 25 ] [ 35 | 40 ]  <-- Internal
   /   |     /   |      /   |    [D1] [D2]... (Data thật nằm ở đây, nối với nhau) --> [D3] --> [D4]

2. Clustered Index vs Non-Clustered Index

Đặc điểm	Clustered Index (Primary Key)	Non-Clustered Index (Secondary Key)
Số lượng	Duy nhất 1 cái mỗi bảng.	Thoải mái (nhưng tốn chỗ).
Lưu trữ	Sắp xếp lại dữ liệu vật lý trên đĩa theo thứ tự Index.	Tạo ra mục lục riêng, trỏ về Clustered Index (Look-up).
Hiệu năng	Nhanh nhất (Tìm thấy là có Data ngay).	Chậm hơn chút (Tìm thấy Index -> Phải nhảy về PK để lấy Data).

3. Hash Index (Dùng trong Memory Storage)

Dùng hàm băm (Hash Function). Key -> $O(1)$.

Ưu điểm: Cực nhanh cho so sánh bằng (=).
Nhược điểm: Không thể so sánh lớn/nhỏ (> <) hoặc tìm kiếm theo dải. Không thể dùng cho mệnh đề ORDER BY.

4. Composite Index (Index kẹp) & "Leftmost Prefix"

Tạo Index trên (Ho, Ten, NamSinh).

Query 1: WHERE Ho='Nguyen' AND Ten='An' -> ✅ Dùng Index (ngon).
Query 2: WHERE Ho='Nguyen' -> ✅ Dùng Index.
Query 3: WHERE Ten='An' -> ❌ KHÔNG dùng Index (Full Scan). Tại sao?

💡 Quy tắc cuốn danh bạ

Danh bạ xếp theo Họ, rồi đến Tên. Nếu bạn chỉ tìm người tên "An" mà không biết Họ, bạn phải lật từng trang danh bạ để tìm (Full Scan). Phải tìm từ trái sang phải!

📝 Lab 14: Explain Analyze

Tạo bảng 1 triệu dòng và chạy lệnh:

EXPLAIN SELECT * FROM users WHERE email='test@gmail.com';

type: ALL -> Toang. Quét 1 triệu dòng.
type: ref/const -> Tốt. Dùng Index.
rows: 1 -> Tuyệt vời.

DAY 66🇯🇵 データベース索引 (B-Tree)