Index (Chỉ mục) trong cơ sở dữ liệu (Database) đóng vai trò tương tự như Mục lục của một cuốn sách.

Nếu cuốn sách 1.000 trang không có mục lục, khi muốn tìm kiến thức về "Thuật toán Dijkstra", ta phải lật từng trang từ 1 đến 1.000 (Full Table Scan - $O(N)$). Nhưng nếu có mục lục, ta chỉ cần tra chữ "Dijkstra" ở mục lục, xem số trang và nhảy thẳng tới trang đó (Index Lookup - $O(\log N)$).

1. BẢN CHẤT CẤU TRÚC DỮ LIỆU BÊN DƯỚI INDEX

Để tìm kiếm với tốc độ cực nhanh, Database không lưu Index dưới dạng danh sách thông thường mà sử dụng hai cấu trúc dữ liệu kinh điển đã học ở các chương trước:

a) B-Tree / B+Tree Index (Phổ biến nhất trong RDBMS: MySQL InnoDB, PostgreSQL)

Cấu trúc cây tìm kiếm nhị phân được mở rộng ra nhiều nhánh (Multi-way Search Tree), tự cân bằng.

                     [ Root: 50 ]
                    /            \
         [ Page 1: 20, 30 ]     [ Page 2: 70, 90 ]
        /        |        \     /        |        \
     [10]       [25]     [40] [60]      [80]      [95]  <-- Leaf Nodes (Chứa Pointer tới ô đĩa RAM/Disk)

• Ưu điểm: Hỗ trợ cực tốt cho các truy vấn tìm kiếm chính xác (=) và tìm kiếm theo khoảng (BETWEEN, >, <, ORDER BY).

• Độ phức tạp: $O(\log N)$ cho cả tìm kiếm, thêm và xóa.

b) Hash Index (Có trong MySQL MEMORY, PostgreSQL Hash)

Sử dụng nguyên lý Bảng băm (Hash Table) đã học ở Chương 4.

• Ưu điểm: Truy vấn so sánh bằng (WHERE id = 100) đạt tốc độ tức thì $O(1)$.

• Nhược điểm: Không dùng được cho tìm kiếm theo khoảng (WHERE age > 30) hoặc sắp xếp (ORDER BY).

2. CƠ CHẾ HOẠT ĐỘNG: TÌM KIẾM TRÊN INDEX KHÁC GÌ CHƯA CÓ INDEX?

Giả sử bảng Orders (Đơn hàng) của xưởng có 1.000.000 dòng:

SELECT * FROM Orders WHERE CustomerID = 8520;

Kết quả :

  KHI CHƯA ĐÁNH INDEX (Full Table Scan):
  Đọc dòng 1 -> Dòng 2 -> Dòng 3 ... -> Dòng 1.000.000  (Mất ~2-5 giây, tốn rất nhiều I/O Ổ cứng)

  KHI ĐÃ ĐÁNH INDEX trên cột CustomerID (Index Scan):
  Tra B-Tree (3-4 bước truy vết ô nhớ) -> Trỏ thẳng tới vị trí dòng 8520 trên Disk (Mất ~0.001 giây)

3. TẠI SAO KHÔNG ĐÁNH INDEX CHO TẤT CẢ CÁC CỘT?

Index giúp tăng tốc độ đọc dữ liệu (SELECT), nhưng nó đi kèm với chi phí đánh đổi (Trade-off):

1. Tốn dung lượng bộ nhớ: Index là một bảng phụ phụ thuộc, lưu trữ cấu trúc cây trên Ổ cứng/RAM. Đánh quá nhiều Index sẽ làm phình dung lượng CSDL.

2. Làm chậm thao tác Ghi (INSERT, UPDATE, DELETE): Mỗi khi thêm hoặc xóa 1 dòng dữ liệu, Database vừa phải ghi dòng đó vào mảng chính, vừa phải tính toán lại và chèn/cân bằng lại Cây B-Tree của Index.

4. CÁC LOẠI INDEX THƯỜNG GẶP VÀ KINH NGHIỆM SỬ DỤNG

Các loại Index phổ biến:

• Primary Index (Clustered Index): Tự động tạo khi khai báo Khoá chính (PRIMARY KEY). Dữ liệu thực tế trên đĩa được vật lý sắp xếp theo thứ tự của chỉ mục này. Mỗi bảng chỉ có duy nhất 1 Clustered Index.

• Secondary Index (Non-Clustered Index): Chỉ mục phụ tạo thêm trên các cột khác. Lưu Khóa + Con trỏ trỏ về dòng dữ liệu thực tế.

• Composite Index (Multi-column Index): Chỉ mục kết hợp từ 2 hoặc nhiều cột (CREATE INDEX idx_name ON Orders(Status, CreatedAt)).

Nguyên tắc vàng khi đánh Index cho Dev / Data Architect:

• NÊN đánh Index khi:

  • Cột xuất hiện thường xuyên trong mệnh đề WHERE, JOIN, ORDER BY, GROUP BY.

  • Cột có độ đa dạng dữ liệu cao (High Cardinality) - ví dụ: Số điện thoại, Mã định danh, Email.

• KHÔNG NÊN đánh Index khi:

  • Bảng quá nhỏ (dưới vài trăm dòng, scan thẳng còn nhanh hơn duyệt Index).

  • Cột có độ đa dạng dữ liệu thấp (Low Cardinality) - ví dụ: Giới tính (Nam/Nữ), Trạng thái (Active/Inactive).

  • Bảng thường xuyên có tần suất INSERT/UPDATE cực cao nhưng ít khi SELECT.