Cơ chế đánh index của database

Bài viết dựa theo những thông tin thu nhận được từ trang:
http://use-the-index-luke.com/

SQL index là kỹ thuật tuning SQL quan trọng. Index nói chung giúp gia tăng tốc độ query database lên. Mình sẽ nêu từng đặc điểm quan trọng của index và phân tích mỗi đặc điểm.

Index là một cấu trúc riêng biệt được tạo ra và tham chiếu đến dữ liệu thực sự nằm trong table. Như vậy, sử dụng index yêu cầu cần disk space để chứa cấu trúc của nó. Index không làm thay đổi cấu trúc dữ liệu của table. Nó chỉ tham chiếu đến dữ liệu đang nằm trong table. Index rất giống phần index nằm ở những trang cuối của một cuốn sách. Bạn cần thêm giấy cho các trang index, các index đó lại trỏ đến các mục trong cuốn sách. Rất giống nhau phải không nào. 

Lý do index khiến tốc độ query tăng lên vì dữ liệu index được tổ chức sắp xếp hợp lý theo một trình tự còn dữ liệu thực sự trong table là dữ liệu không có thứ tự nên không tiện cho tìm kiếm. Việc tìm kiếm qua index cũng giống như tra số điện thoại trong danh bạ nhưng không hoàn toàn giống. Dữ liệu trong danh bạ không thể cập nhật nhanh chóng được vì không có không gian trống giữa các index. Bạn không thể dễ dàng chèn thêm/xóa bớt một index vào danh bạ được. Với danh bạ điện thoại, index chỉ có thể cập nhật trong lần xuất bản tiếp theo. Đây là điểm khác biệt với index của database. Index của database cần được cập nhật nhanh chóng khi có các sự kiện insert, update, delete trên table. Để đáp ứng yêu cầu này, index của database được tổ chức theo hai cách: doubly linked list - danh sách hai chiều và search tree - cây tìm kiếm.