Hash index và bức tranh các loại index

TL;DR: Không có một loại index vạn năng — mỗi loại tối ưu cho một kiểu truy vấn. Hash index băm khoá thành vị trí, cho tra cứu equality (= giá trị chính xác) gần như O(1), nhưng mù hoàn toàn với range/prefix vì hàm hash cố tình phá vỡ thứ tự. Ordered index (B-tree) ngược lại: chậm hơn equality một chút nhưng phục vụ được range, prefix, ORDER BY. Ngoài hai họ chính còn các loại chuyên dụng — inverted index (full-text), spatial (không gian), bitmap (cột ít giá trị phân biệt) — mỗi loại sinh ra cho một query pattern mà hai họ chính làm kém. Chọn loại index là chọn theo hình dạng câu hỏi bạn hỏi dữ liệu, không phải theo thói quen.

Bài 02 so sánh hai cách lưu một index sorted xuống đĩa (B-tree vs LSM-tree). Nhưng cả hai đều thuộc họ "ordered" — giữ khoá theo thứ tự. Câu hỏi tiếp theo: nếu bạn không cần thứ tự, chỉ cần tra "có đúng khoá này không", liệu có cấu trúc nào nhanh hơn? Có — hash index. Và một khi đã thấy hash là một họ riêng, bức tranh mở ra: có cả một họ các loại index, mỗi loại sinh ra cho một hình dạng truy vấn khác nhau.

TaskFlow gặp đúng tình huống này. Query thứ nhất: "lấy session theo session token chính xác" — chỉ tra equality một khoá, không bao giờ cần range. Query thứ hai: "task có due_at trong tuần này" — range. Query thứ ba: "task có chữ 'login' trong mô tả" — tìm chữ trong văn bản. Ba câu hỏi, ba hình dạng khác nhau, và không một loại index nào giỏi cả ba. Bài này vẽ bức tranh các loại index ở mức nguyên lý và dạy chọn loại nào theo từng hình dạng câu hỏi.

1. Analogy — Tủ hồ sơ vs bảng tra số nhà

Hình dung hai cách tổ chức để tìm thông tin:

• Tủ hồ sơ xếp theo bảng chữ cái (ordered / B-tree): kẹp hồ sơ theo tên, A đến Z. Tìm "Nam" thì lật tới chữ N — nhanh. Và vì đã sắp xếp, muốn lấy "tất cả tên từ M đến P" thì chỉ cần kéo một dải liên tục — range query dễ dàng.
• Bảng tra số nhà bằng công thức (hash): thay vì xếp theo thứ tự, bạn dùng một công thức biến tên thành số ô tủ: "Nam" → ô 7, "An" → ô 3. Tra một tên: tính công thức, mở thẳng đúng ô — gần như tức thì, không cần lật. Nhưng "tất cả tên từ M đến P" thì chịu: công thức rải các tên đi khắp nơi, "Nam" ở ô 7 còn "Nga" có thể ở ô 200 — không có khái niệm "ô kế tiếp theo thứ tự tên".

2. Hash index — equality O(1), mù với range

Hash index dựa trên một hàm hash: một hàm biến khoá thành một con số (vị trí) trong một mảng các "bucket". Tra cứu khoá K: tính hash(K) ra vị trí, nhảy thẳng tới bucket đó, lấy pointer trỏ về dữ liệu. Không phải duyệt cây, không phải so sánh nhiều lần — về trung bình là O(1), một bước.

Hash index ON sessions(token):

  token "a1b2..."  --hash()-->  bucket 7  --> pointer toi row
  token "9f3c..."  --hash()-->  bucket 2  --> pointer toi row
  token "00de..."  --hash()-->  bucket 7  --> collision: chuoi trong bucket 7

  (vi tri = ham hash; KHONG sap theo gia tri token)

Điểm cốt lõi để hiểu cả ưu lẫn nhược: hàm hash cố tình phân tán khoá đều khắp các bucket để tránh dồn cục. Hệ quả: hai khoá liền kề về giá trị (token = 100 và token = 101) rơi vào hai bucket cách xa nhau. Hash không giữ bất kỳ thứ tự nào.

-- Hash index toa sang: tra dung mot khoa chinh xac
SELECT user_id, expires_at FROM sessions
WHERE token = 'a1b2c3d4e5f6';   -- equality -> hash O(1)

-- Hash index BO TAY: range / so sanh thu tu
SELECT * FROM events WHERE id BETWEEN 1000 AND 2000;  -- hash khong giup
SELECT * FROM tasks ORDER BY due_at;                  -- hash khong giup
SELECT * FROM users WHERE email LIKE 'admin%';        -- prefix -> hash khong giup

Đây chính xác là tấm gương ngược của B-tree: B-tree giữ thứ tự nên làm range tốt nhưng equality chậm hơn hash một chút; hash phá thứ tự để equality cực nhanh nhưng mất sạch khả năng range/prefix/ORDER BY.

2.1 Hai giới hạn thực tế của hash

Ngoài chuyện "không range", hash index có hai ràng buộc thực tế:

• Hash collision — hàm hash có thể ánh hai khoá khác nhau vào cùng một bucket. Engine phải xử lý (thường nối thành chuỗi trong bucket, hoặc dò sang ô kế). Nếu phân bố lệch (nhiều khoá dồn vài bucket), tra cứu suy biến từ O(1) về duyệt chuỗi dài — chậm đi.
• Hợp nhất với bộ nhớ — hash index hiệu quả nhất khi bảng băm vừa trong bộ nhớ (RAM). Khi nó lớn vượt RAM và phải tràn xuống đĩa, mỗi lookup thành một random I/O (vì vị trí rải khắp nơi, không cục bộ như B-tree đi tuần tự xuống leaf) — chi phí tăng nhanh.

3. Bức tranh các loại index — mỗi loại cho một hình dạng câu hỏi

Lùi lại một bước: index không phải một thứ, mà là một họ cấu trúc, mỗi loại sinh ra để trả lời một hình dạng câu hỏi mà các loại khác làm kém. Hai họ chính bạn đã gặp, cộng vài loại chuyên dụng nên biết là tồn tại + dùng cho gì (không cần đi sâu engine):

flowchart TB
  Q["Hinh dang cau hoi tren du lieu?"]
  Q --> EQ["Equality: WHERE k = gia tri"]
  Q --> RG["Range / prefix / ORDER BY"]
  Q --> TX["Tim chu trong van ban"]
  Q --> SP["Truy van khong gian (gan toa do X)"]
  Q --> LC["Cot it gia tri phan biet (low cardinality)"]
  EQ --> H["Hash index (O(1))"]
  RG --> B["Ordered index / B-tree"]
  TX --> IV["Inverted index (full-text)"]
  SP --> ST["Spatial index"]
  LC --> BM["Bitmap index"]

Ba loại cuối chỉ cần nắm tồn tại + dùng cho gì ở mức khái niệm:

• Inverted index (full-text) — để trả lời "document nào chứa từ này", nó lật ngược quan hệ: thay vì "doc → các từ", nó lưu "từ → danh sách doc chứa từ đó". Đây là nền tảng của tìm kiếm văn bản. Nó là lời giải cho LIKE '%từ%' mà B-tree bó tay (xem bài pattern matching).
• Spatial index — để trả lời "điểm nào gần toạ độ này / nằm trong vùng này", nó chia không gian nhiều chiều thành các ô lồng nhau để khoanh vùng nhanh. Dùng cho dữ liệu địa lý, hình học.
• Bitmap index — cho cột ít giá trị phân biệt (low cardinality) như status (chỉ vài giá trị) hay gender: mỗi giá trị ứng một dãy bit "dòng nào mang giá trị này". Kết hợp nhiều điều kiện thành phép AND/OR trên các dãy bit — rất nhanh cho phân tích, nhưng tốn cập nhật nên hợp kho đọc-nhiều hơn là OLTP ghi-nhiều.

4. Chọn loại index theo query pattern

Quy trình thực tế: nhìn vào hình dạng các truy vấn nóng (chạy nhiều, chậm), rồi chọn loại index khớp hình dạng đó.

5. Pitfall — chọn loại index không khớp hình dạng truy vấn

-- SAI 1: ky vong hash index ho tro range
-- Hash phan tan token khap noi -> khong co "khoa ke tiep" -> range bo tay
SELECT * FROM sessions WHERE created_at BETWEEN '2026-06-01' AND '2026-06-07';
-- Hash index tren created_at KHONG giup -> full scan
-- Dung: ordered index (B-tree) tren created_at

-- SAI 2: ky vong B-tree ho tro chu GIUA van ban
SELECT * FROM tasks WHERE description LIKE '%login%';
-- B-tree chi tan dung prefix (LIKE 'login%'), khong tim chu giua chuoi
-- Dung: inverted index (full-text) cho noi dung van ban

6. 📚 Deep Dive

7. Liên hệ các bài khác

• Bài 01 — Tại sao cần index: nền tảng heap vs index sorted, 3 loại scan, và "tạo index không bảo đảm được dùng" — áp thẳng vào việc chọn đúng loại index ở bài này.
• Bài 02 — B-tree vs LSM-tree: cả hai là họ ordered index; bài này thêm hash (equality-only) và các loại chuyên dụng để hoàn thiện bức tranh.
• Module 2 — Pattern matching: vì sao LIKE 'foo%' (prefix) dùng được B-tree còn LIKE '%foo%' (chữ giữa) cần inverted/full-text — minh hoạ trực tiếp việc khớp loại index với hình dạng truy vấn.
• Module 10 — OLTP vs OLAP: bitmap index hợp kho phân tích (đọc-nhiều, cột low-cardinality) hơn DB giao dịch — nối với phân đôi workload.

8. Tóm tắt

• Không có index vạn năng: mỗi loại tối ưu cho một hình dạng câu hỏi.
• Hash index: băm khoá ra vị trí → equality O(1); nhưng mù với range/prefix/ORDER BY vì hàm hash phá vỡ thứ tự. Thêm hai giới hạn: hash collision và hiệu quả nhất khi vừa RAM.
• Ordered index (B-tree): giữ khoá sorted → phục vụ range, prefix, sắp xếp, cả equality — đa năng nên thường là mặc định.
• Các loại chuyên dụng nên biết tồn tại + dùng cho gì: inverted (tìm chữ trong văn bản), spatial (truy vấn không gian), bitmap (cột low-cardinality trong kho phân tích).
• Chọn loại index = nhìn hình dạng truy vấn nóng rồi khớp loại; kiểm tra query plan để xác nhận index được dùng.
• Pitfall: hash cho range, hoặc B-tree cho chữ giữa văn bản — index nằm im, planner vẫn full scan.

9. Tự kiểm tra

Đây là bài cuối trong chuỗi nền tảng storage & indexing của module.

Bài tiếp theo: Tại sao cần index — ôn lại nền tảng module