Học phần: CẤU TRÚC DỮ LIỆU DẠNG CÂY (TREE DATA STRUCTURES)
1. MÔ HÌNH PHÂN CẤP & CÁC KHÁI NIỆM CỐT LÕI 2. CÁC THUẬT TOÁN DUYỆT CÂY (TREE TRAVERSAL) 3. INDEX (CHỈ MỤC) TRONG CSDL 4. MINH HỌA TỰ XÂY DỰNG INDEX 5. KHÓA CHÍNH (PRIMARY KEY)
Quay lại khóa học

KHÓA CHÍNH (PRIMARY KEY)

Cột số nguyên tự tăng (incremental integer) mà ta thường thấy khi tạo ra các bảng trong cơ sở dữ liệu chính là Khóa chính (Primary Key) hoặc thuộc tính AUTO_INCREMENT / SERIAL / IDENTITY trong các Hệ quản trị Cơ sở Dữ liệu Quan hệ (RDBMS) như MySQL, PostgreSQL, SQL Server, hay Oracle.

Index tự động được tạo ra cho cột này là B-Tree (hoặc biến thể B+Tree).

TẠI SAO DATABASE KHÔNG CHỌN HASH INDEX CHO KHÓA CHÍNH TỰ TĂNG?

Dù Hash Index có tốc độ tìm kiếm chính xác ($=1$) đạt $O(1)$, các CSDL quan hệ vẫn chọn B-Tree làm mặc định cho Khóa chính tự tăng vì 4 lý do kỹ thuật cốt lõi:

1. Phục vụ truy vấn theo khoảng (BETWEEN, >, <)

Số nguyên tự tăng rất hay được sử dụng để phân đoạn hoặc lọc dữ liệu theo khoảng ID:

SQL 
SELECT * FROM Orders WHERE id BETWEEN 1000 AND 2000;
SELECT * FROM Logs WHERE id > 50000;

  • B-Tree: Nhảy tới lá 1000 rồi duyệt ngang trên danh sách liên kết đến 2000 với tốc độ cực nhanh ($O(\log N)$).

  • Hash Index: Bị vô hiệu hóa hoàn toàn với phép so sánh khoảng, buộc CSDL phải quay về Full Table Scan ($O(N)$).

2. Sắp xếp (ORDER BY) và Phân trang (LIMIT / OFFSET)

Dữ liệu tự tăng mang tính thứ tự tự nhiên. Truy vấn phân trang rất phổ biến:

SQL 
SELECT * FROM Orders ORDER BY id DESC LIMIT 20;

  • B-Tree: Dữ liệu trên các nút lá của B-Tree đã được sắp xếp sẵn theo thứ tự. Database chỉ cần đọc ngược 20 phần tử cuối cùng trên nút lá mà không mất chi phí sắp xếp (No Sort needed).

  • Hash Index: Không lưu trữ theo thứ tự, Database buộc phải đọc toàn bộ tập dữ liệu lên RAM và thực hiện thuật toán Sort lại từ đầu.

3. Tổ chức lưu trữ vật lý dữ liệu (Clustered Index / Index-Organized Table)

Trong các Storage Engine hiện đại như MySQL InnoDB:

  • B-Tree của Khóa chính chính là Clustered Index (Chỉ mục cụm).

  • Toàn bộ dòng dữ liệu thực tế trên ổ đĩa được lưu trực tiếp tại các nút lá của Cây B-Tree này.

  • Khi ID mới tự tăng thêm vào (ví dụ: id = 1001), dữ liệu chỉ đơn giản là được ghi nối tiếp vào cuối nút lá cuối cùng của Cây B-Tree, giúp hạn chế tối đa hiện tượng phân mảnh ổ đĩa (Page Split) và tối ưu hóa tốc độ ghi đĩa ($O(\log N)$).

4. Phù hợp cho các thao tác JOIN bảng (Foreign Key)

Khóa chính số nguyên tự tăng thường xuyên được dùng để nối bảng (JOIN):

SQL 
SELECT * FROM Orders o JOIN OrderDetails d ON o.id = d.order_id;

B-Tree giúp các thuật toán Join như Merge Join hay Index Nested Loop Join thực thi tối ưu hơn rất nhiều nhờ tận dụng tính chất có thứ tự của khóa.

TỔNG KẾT MẶC ĐỊNH TRÊN CÁC CSDL PHỔ BIẾN

Cơ sở dữ liệu Cột AUTO_INCREMENT / Khóa chính Loại Index tự động khởi tạo
MySQL (InnoDB) INT AUTO_INCREMENT PRIMARY KEY B+Tree (Clustered Index)
PostgreSQL id SERIAL PRIMARY KEY B-Tree (Mặc định cho mọi Index)
Microsoft SQL Server id INT IDENTITY PRIMARY KEY B-Tree (Clustered Index)
Oracle GENERATED AS IDENTITY PRIMARY KEY B-Tree
SQLite INTEGER PRIMARY KEY AUTOINCREMENT B-Tree

Ghi chú nhỏ: Hash Index thường chỉ được sử dụng tự động trong các hệ thống In-Memory Database (như Redis, MySQL MEMORY Engine) hoặc bộ đệm tạm thời (như Adaptive Hash Index mà InnoDB tự động dựng trên RAM cho các dòng dữ liệu được truy vấn = liên tục).

← Bài trước