1. Các cấu trúc dữ liệu phổ biến

Ngăn xếp (Stack)

Đặc điểm: Vào sau ra trước (LIFO - Last In First Out).

Hàng đợi (Queue)

Đặc điểm: Vào trước ra trước (FIFO - First In First Out).

Mảng (Array)

• Tìm kiếm nhanh nhờ địa chỉ bộ nhớ và chỉ số.
• Xóa chậm do phải dịch chuyển các phần tử phía sau.
• Thêm chậm vì cần dịch tất cả phần tử sau vị trí thêm.

Danh sách liên kết (Linked List)

• Mỗi nút chứa giá trị và con trỏ tới nút kế tiếp.
• Tìm kiếm chậm do phải duyệt từ đầu danh sách.
• Thêm/xóa nhanh nhờ thay đổi liên kết mà không di chuyển dữ liệu.

Cây nhị phân (Binary Tree)

Còn gọi là cây tìm kiếm nhị phân. Dữ liệu được chèn vào dựa trên quy tắc: nhỏ hơn thì sang trái, lớn hơn thì sang phải.

• Mỗi nút có tối đa hai nút con.
• Chiều sâu của nút là số bước từ gốc đến nó.
• Chiều cao là khoảng cách dài nhất từ nút đó đến lá.

Nhược điểm:

• Khi dữ liệu được chèn theo thứ tự, cây dễ bị suy biến thành danh sách liên kết, làm giảm hiệu suất tìm kiếm.

Cây nhị phân cân bằng (AVL Tree)

Là cây nhị phân với điều kiện: độ chênh lệch chiều cao giữa hai nhánh con không quá 1.

• Sử dụng phép quay trái/phải để duy trì tính cân bằng khi thêm/xóa.
• Quay trái: nút con bên trái lên làm cha.
• Quay phải: nút con bên phải lên làm cha.

Nhược điểm:

• Vẫn có thể chậm nếu cây quá sâu.
• Không giải quyết tốt bài toán tìm kiếm vòng.
• Hiệu suất thêm nút thấp do ảnh hưởng lan rộng khi quay cây.

Cây đỏ đen (Red-Black Tree)

Là dạng cây nhị phân tự cân bằng dựa trên các quy tắc màu:

• Mỗi nút có màu đỏ hoặc đen.
• Gốc luôn đen.
• Hai nút đỏ không được liền nhau.
• Tất cả đường đi từ gốc đến lá đều có cùng số lượng nút đen.

Ưu điểm:

• Hiệu suất ổn định hơn AVL do ít thao tác quay hơn.
• Thích hợp cho hệ thống thường xuyên thêm/sửa/xóa dữ liệu.

Nhược điểm:

• Vẫn gặp khó khăn với dữ liệu lớn và bài toán tìm kiếm vòng.

Cây B (B-Tree)

Là cây đa nhánh cân bằng, mỗi nút có thể chứa nhiều khóa:

• Khóa và dữ liệu được lưu tại từng nút.
• Tất cả lá nằm cùng cấp.
• Tìm kiếm có thể dừng ở nút giữa nếu tìm thấy.

Quy tắc:

• Mỗi nút có tối đa m con.
• Ngoại trừ gốc, mỗi nút có ít nhất ⌈m/2⌉ con.
• Nút có j con sẽ có j-1 khóa.

Cây B+ (B+ Tree)

Là biến thể của B-tree, khác biệt chính:

• Chỉ lá chứa dữ liệu, nút nội chỉ dùng làm chỉ mục.
• Lá được nối với nhau bằng con trỏ.
• Tìm kiếm luôn phải đi đến lá mới kết thúc.

Quy trình chèn:

1. Luôn chèn vào lá.
2. Nếu lá chưa đầy, chèn trực tiếp.
3. Nếu đầy, tách thành hai nút, đưa khóa giữa lên nút cha.
4. Nếu nút cha cũng đầy, tiếp tục tách lên trên.

2. Chỉ mục (Index)

Vai trò

Tăng tốc độ truy vấn dữ liệu.

Khái niệm

Là cấu trúc phụ được tạo từ một phần dữ liệu bảng nhằm tổ chức lại thông tin giúp truy xuất nhanh hơn.

Phân loại

• Chỉ mục gom cụm (Clustered Index): Thứ tự vật lý của dữ liệu trùng với thứ tự khóa. Mỗi bảng chỉ có một.
• Chỉ mục không gom cụm (NonClustered Index): Không ảnh hưởng đến thứ tự vật lý. Một bảng có thể có nhiều (tối đa 999).

Giới hạn

• Mỗi bảng chỉ có 1 chỉ mục gom cụm.
• Tối đa 999 chỉ mục không gom cụm.
• Mỗi chỉ mục chứa tối đa 16 cột.
• Kích thước tối đa của khóa là 900 byte.

Cấu trúc lưu trữ

Trong SQL Server, chỉ mục sử dụng cấu trúc B+ tree:

• Nút nội: Chỉ chứa khóa và con trỏ tới nút con.
• Nút lá: Chứa khóa và dữ liệu thực tế (đối với clustered) hoặc bookmark (với nonclustered).

Tại sao chọn B+ tree?

1. Giảm chi phí đọc/ghi đĩa nhờ kích thước nút nhỏ gọn.
2. Độ dài đường đi từ gốc đến lá luôn bằng nhau → hiệu suất truy vấn ổn định.
3. Dễ dàng quét toàn bộ dữ liệu nhờ liên kết giữa các lá.

Nguyên tắc thiết kế

Không nên tạo quá nhiều chỉ mục:

• Tốn dung lượng lưu trữ.
• Làm chậm thao tác thêm/sửa/xóa do phải cập nhật chỉ mục.
• Dễ sinh mảnh chỉ mục gây giảm hiệu năng.

Nên tạo chỉ mục cho:

• Khóa chính.
• Khóa ngoại.
• Các cột thường dùng trong WHERE, ORDER BY, GROUP BY.

Không nên tạo chỉ mục cho:

• Cột có nhiều giá trị trùng lặp.
• Trường kiểu text, image, bit.

Thao tác với chỉ mục

-- Tạo chỉ mục gom cụm
CREATE CLUSTERED INDEX idx_user_id ON Users(UserID);

-- Tạo chỉ mục không gom cụm
CREATE NONCLUSTERED INDEX idx_user_email ON Users(Email);

-- Tạo chỉ mục duy nhất
CREATE UNIQUE NONCLUSTERED INDEX idx_user_username ON Users(Username);

-- Xem thông tin chỉ mục
EXEC sp_helpindex 'Users';

-- Đổi tên chỉ mục
EXEC sp_rename 'Users.idx_old_name', 'idx_new_name', 'INDEX';

-- Xóa chỉ mục
DROP INDEX idx_user_id ON Users;

-- Tái tạo chỉ mục
ALTER INDEX idx_user_email ON Users REBUILD;

3. Khung nhìn (View)

Vai trò

• Tăng cường bảo mật.
• Đơn giản hóa câu truy vấn phức tạp.

Bản chất

Là bảng ảo được xây dựng từ một hoặc nhiều bảng thật, bản chất là câu truy vấn đã được lưu sẵn.

Thao tác với khung nhìn

-- Tạo khung nhìn
CREATE VIEW v_student_details AS
SELECT s.Name, c.CourseName, sc.Score
FROM Students s
JOIN Scores sc ON s.StudentID = sc.StudentID
JOIN Courses c ON sc.CourseID = c.CourseID;

-- Sử dụng khung nhìn
SELECT * FROM v_student_details WHERE Name = N'Nguyễn Văn A';

-- Sửa khung nhìn
ALTER VIEW v_student_details AS
SELECT s.Name, c.CourseName, sc.Score
FROM Students s
JOIN Scores sc ON s.StudentID = sc.StudentID
JOIN Courses c ON sc.CourseID = c.CourseID
WHERE sc.Score >= 5;

-- Xóa khung nhìn
DROP VIEW v_student_details;