Tối ưu câu truy vấn có thể hiểu là cải thiện tốc độ truy vấn tới DB bằng cách thay đổi câu truy vấn, có thể là bỏ truy vấn trong vòng lặp, hay sử dụng bảng tạm thời,… Nhưng có 1 cái còn quen thuộc và phổ biến hơn là đánh index (hay chỉ mục) cho các cột. Và hôm nay em về cái nhìn khái quát về index trong cơ sở dữ liệu (Database – DB)Đầu tiên, ta có thể nhận thấy rằng việc sử dụng chỉ mục sẽ không ảnh hưởng tới dữ liệu ban đầu. Mọi hành động xóa hay tạo chỉ đơn giản là thực hiện trên một bản dữ liệu khác tham chiếu tới dữ liệu của bảng, mà nó chỉ liên quan đến bộ nhớ. Do đó, ta không phải lo lắng đến việc mất hay hỏng dữ liệu..
Khái quát
1. Cấu trúc của 1 index
Index (Chỉ mục) là 1 cấu trúc riêng trong DB, được tạo bằng câu CREATE INDEX. Nó cần không gian lưu trữ riêng trên thiết bị lưu trữ (Ổ cứng) và có 1 phần là data của bảng đã được đánh index. Nhìn qua có thể thấy nó khá thừa về data, cũng như không thay đổi data của bảng mà chỉ tạo 1 cấu trúc dữ liệu mới và trỏ tới bảng gốc. Điểm mấu chốt là index được sắp xếp theo 1 thứ tự được định trước, do đó có thể truy xuất data nhanh và dễ hơn bởi đã có thứ hạng sắp xếp cho các phần tử rồi. Và vì data được sắp xếp lại như thế nên việc UPDATE, INSERT hay DELETE trong các bảng sẽ tốn thời gian hơn vì phải xây lại cấu trúc index, nhưng cũng phải xem xét về tần suất sử dụng các hành động này cho bảng để quyết định có nên đánh index không. 2 cấu trúc dữ liệu để làm nên 1 index trong DB thường là danh sách liên kết đôi (double linked list) và cây tìm kiếm (search tree). Trong đó cần xem xét 2 khía cạnh của 1 index, là nút lá chỉ mục (The index leaf node) và cây tìm kiếm cân bằng (B-Tree).
Hình 1. Cấu trúc của 1 index
1.1. Nút lá chỉ mục (The index leaf node)
Cái này sử dụng danh sách liên kết đôi để tối ưu các câu truy vấn thay đổi data bảng (insert, delete, update) dẫn đến thay đổi cấu trúc index. Mỗi nút được lưu trữ trong 1 đơn vị gọi là block hay page, những block này có cùng kích thước (thường là 4KB). DB sẽ sử dụng không gian của mỗi block này để lưu trữ nhiều phần tử index nhất có thể. Thế nên trật tự sắp xếp index luôn được duy trì ở 2 mức: giữa các phần tử của mỗi nút và giữa các nút với nhau. Mỗi phần tử index bao gồm 1 cột được đánh index và 1 tham chiếu tới bảng gốc.
Hình 2. Nút lá chỉ mục (the index leaf node)
1.2. Cây tìm kiếm cân bằng (B-Tree)
Các nút khi được lưu trữ thì vẫn chỉ theo 1 thứ tự tuỳ ý trên ổ cứng. Vì vậy DB cần 1 cấu trúc dữ liệu thứ 2 để tìm được 1 mục trong các trang bị xáo trộn 1 cách nhanh nhất, và đó là 1 cây tìm kiếm cân bằng (B-Tree).
Hình 3. Cấu trúc của B-Tree
Hình 3 là ví dụ về một index với 30 phần tử. Danh sách liên kết đôi thiết lập các thứ tự logic giữa các nút lá. Các nút gốc (root nodes) và các nút nhánh (branh nodes) hỗ trợ tìm kiếm nhanh chóng các nút lá.
Sau khi được tạo, cơ sở dữ liệu phải duy trì index một cách tự động. Mọi thao tác insert, delete, update đều phải cập nhật index và giữ cho cây luôn ở trạng thái cân bằng.
Hình 4. Quá trình duyệt B-tree
Hình 4 mô tả quá trình tìm kiếm cho từ khoá là “57”. Quá trình duyệt cây bắt đầu từ nút gốc phía bên trái. Khoá sẽ được so sánh lần lượt với các phần tử trong nút theo thứ tự tăng dần cho đến khi có phần tử lớn hơn hoặc bằng (>=) với khoá (57). Như trong hình thì phần tử đó chính là 83. Từ đó cơ sở dữ liệu sẽ được trỏ tới nút nhánh tương ứng và lặp lại quá trình như trên cho đến khi tới nút lá.
2. Ưu điểm của việc sử dụng chỉ mục
Đầu tiên, ta có thể nhận thấy rằng việc sử dụng chỉ mục sẽ không ảnh hưởng tới dữ liệu ban đầu. Mọi hành động xóa hay tạo chỉ đơn giản là thực hiện trên một bản dữ liệu khác tham chiếu tới dữ liệu của bảng, mà nó chỉ liên quan đến bộ nhớ. Do đó, ta không phải lo lắng đến việc mất hay hỏng dữ liệu.
Hình 5. Index không ảnh hưởng data gốc
Việc sử dụng chỉ mục giúp cải thiện tốc độ cho các câu lệnh SELECT hay JOIN có các mệnh đề WHERE. Có được điều đó là bởi chỉ mục sử dụng cấu trúc cây cân bằng. Duyệt cây là một thao tác khá hiệu quả, nó thể hiện sức mạnh của cấu trúc đánh chỉ mục. Sử dụng chỉ mục trả về kết quả rất nhanh ngay cả khi với một tập dữ liệu rất lớn. Điều này bởi vì cây cân bằng cho phép truy cập tất cả các phần tử với số lượng các bước như nhau và độ sâu của cây chỉ tăng theo hàm logarit. Độ sâu của cây tăng rât chậm so với số lượng các nút lá. Trong thực tế quá trình đánh chỉ mục thực hiện trên hàng triệu bản ghi thì độ sâu của cây cũng chỉ là 4 hoặc 5.
Hình 6. Index giúp cải thiện tốc độ truy vấn với JOIN và WHERE
3. Một số vấn đề gặp phải khiến sử dụng chỉ mục bị chậm
Như đã nói thì chỉ mục sẽ làm tốn chi phí thời gian cho các hoạt động như UPDATE, DELETE, INSERT. Tuy nhiên, ở đây sẽ tập trung nói về việc sử dụng chỉ mục cho các hoạt động khác (như SELECT, JOIN) mà tưởng chừng như là cải thiện tốc độ nhưng vô tình làm giảm tốc độ của câu truy vấn.
Một quá trình tra cứu chỉ mục gồm 3 bước: (1) quá trình duyệt cây; (2) duyệt các nút lá kế tiếp; (3) lấy dữ liệu từ bảng. Quá trình duyệt cây là bước duy nhất có giới hạn trên cho số lần truy cập các block – độ sâu của cây. Hai bước còn lại có thể truy cập nhiều block – chúng là nguyên nhân tại sao quá trình tra cứu chỉ mục chậm đi.
Hình 7. Một số vấn đề khiến sử mục chỉ mục bị chậm
Điều đầu tiên khiến cho một tra cứu chỉ mục chậm đi là do chuỗi các nút lá. Ta xem xét lại ví dụ trong Hình 4 với quá trình tìm kiếm “57”. Rõ ràng ta thấy có hai phần tử khớp trong chỉ mục. Có ít nhất 2 phần tử giống nhau hay nói chính xác hơn là: có thể có nhiều phần tử ở các nút là tiếp theo cũng có giá trị là “57”. Cơ sở dữ liệu phải đọc các nút lá tiếp theo để xem nếu có bất kỳ phần tử nào khớp với giá trị cần tìm kiếm. Điều này có nghĩa rằng một quá trình tra cứu chỉ mục không chỉ cần thực hiện việc duyệt cây mà cũng cần thực hiện việc duyệt trên chuỗi các nút lá.
Điều thứ hai có thể làm một tra cứu chỉ mục chậm đi là quá trình truy cập bảng. Một nút lá bao gồm nhiều nút chỉ mục, thường hàng trăm, mỗi nút chỉ mục trỏ tới một dòng dữ liệu trong bảng ở những vị trí lưu trữ khác nhau. Bảng dữ liệu tương ứng thường nằm rải rác trên nhiều block (Hình 2).
Kết luận: Từ những vấn đề trên, một số cách sử dụng chỉ mục hiệu quả sẽ được đề xuất trong phần tiếp theo của bài viết.