today-i-learned index database - It costs 8 mins to read

Bài viết được lấy từ nguồn Viblo.asia.

Là một lập trình viên, chắc hẳn không ít thì nhiều, bạn đã từng phải nghe nói đến việc đánh index (chỉ mục) cho table này, table khác trong database. Dù có không hiểu index là gì, thì ắt hẳn bạn cũng phải biết một điều xưa như trái đất, rằng muốn truy vấn cho nhanh, thì phải đánh index. Nhưng do tính chất công việc, liệu rằng trong chúng ta, mấy ai từng được làm việc nhiều với database, để có cơ hội tìm hiểu kĩ về vấn đề này. Tôi tin rằng không ít người, kể cả những lập trình viên vài năm kinh nghiệm, khi được hỏi : index là gì, index hoạt động như thế nào, tại sao đánh index lại khiến tăng tốc độ truy vấn … ? cũng chưa chắc đã có thể trả lời cặn kẽ. Bài viết này, vốn được tìm hiểu vội vàng trong một khoảng thời gian ngắn, hi vọng có thể giúp bạn ít nhiều hiểu rõ hơn một chút về vấn đề này.

Một kịch bản không có index

Để hiểu index là gì, ta hãy thử đặt ra một kịch bản truy vấn đơn giản, giả sử ta muốn tìm trong bảng users, lấy ra thông tin của tất cả những user có name là DungNQ.

SELECT * FROM USER WHERE NAME = 'DungNQ';

Trong tình huống này, database của chúng ta sẽ phải đọc ra từng record trong bảng users, so sánh giá trị của trường name trong record đó với giá trị cần tìm, và thực hiện từ record đầu tiên cho tới record cuối cùng của bảng. Cách làm này gọi là full table search. Dĩ nhiên, ta có thể thấy đây là cách làm chậm nhất, vì phải lọc qua tất cả dữ liệu hiện hữu trong bảng. Từ đó đặt ra vấn đề, muốn tăng tốc độc truy vấn, phải làm sao giảm thiểu số lượng bản ghi/trường cần phải đọc khi thực hiện truy vấn.

Tăng tốc truy vấn bằng cách đánh chỉ mục.

Hãy tưởng tượng, cũng trong kịch bản truy vấn trên, nhưng trong tay ta đang có sẵn một chuỗi, bao gồm tất cả các giá trị của trường name có trong bảng users, và các giá trị này đã được sắp xếp theo thứ tự tăng dần. Lúc này, để tìm ra record có giá trị name = 'DungN', thay vì lôi lần lượt từ giá trị đầu tiên đến giá trị thứ n cuối cùng ra để so sánh (cần thực hiện n phép so sánh ), ta có thể thực hiện một phép tìm kiếm nhị phân. Rõ ràng việc thực hiện phép tìm kiếm ban đầu đã trở nên dễ dàng hơn và nhanh hơn rất nhiều. Không chỉ số lượng record ta phải đọc ít đi, mà trong mỗi record, ta cũng chỉ cần đọc giá trị của đúng trường name mà thôi. Và giả sử, ứng với mỗi một phần tử trong dãy như trên, ta có thể gán ứng với một giá trị con trỏ, trỏ đến record tương ứng trong bảng users, ta hoàn toàn có thể truy vấn tất cả các thông tin của user cần tìm, chứ không chỉ giá trị trường name được lưu trong dãy. Dạng cấu trúc dữ liệu như dãy được mô tả trên, chính là một dạng index, cũng thuộc loại phổ biến bậc nhất, B-tree index.

Một kịch bản khác.

Cũng trong kịch bản truy vấn trên, ta không có một dãy được sắp xếp theo thứ tự sẵn như trên nữa. Thay vào đó, ta có một array các cặp key => value dạng như 'DungNQ' => 0x28939 trong đó, key chính là giá trị của trường name trong bảng users, còn value là biến con trỏ chỉ đến record tương ứng trong bảng. Rõ ràng, trong trường hợp này, truy vấn đầu tiên, nếu được thực hiện trong array kia, sẽ nhanh chóng hơn rất nhiều so với thực hiện full table scan trên bảng users. Kiểu cấu trúc dữ liệu giống như mô tả trên cũng là một dạng index tương đối phổ biến, Hash table index.

Index là gì?

Ngoài B-tree index hay Hash table index ra, còn có một số loại index tương đối kém phổ biến hơn , như R-tree index hay Bitmap index. Mỗi loại Index đều có cấu trúc riêng, có ưu và nhược điểm riêng, phù hợp cho từng kiểu truy vấn đặc thù. Ví dụ như Hash table index có lợi thế rất nhanh khi thực hiện các phép truy vấn với toán tử = hay <>, tuy nhiên lại bó tay trước các phép truy vấn với toán tử < hay >. B-tree index là loại index phổ biến nhất, và là loại index mặc định trong hầu hết các hệ quản trị cơ sở dữ liệu. Tuy index loại này rất mềm dẻo, hữu ích trong rất nhiều tình huống so với Hash table index, nhưng lại chịu chết với các phép so sánh <>. Tổng kết chung lại , ta có thể có một định nghĩa khá chung và toàn diện cho index:

Index là một dạng cấu trúc dữ liệu, trong đó chứa giá trị của một trường nhất định trong một bảng dữ liệu, đồng thời trỏ đến record dữ liệu tương ứng.

Tổng kết

Lan man một hồi, có lẽ cũng là gọi là tạm đủ để trả lời mấy câu hỏi đặt ra lúc ban đầu : index là gì (khái niệm tự chém kia), index hoạt động như thế nào (giải thích chi tiết hai loại cơ bản nhất là đủ), tại sao đánh index lại làm truy vấn nhanh hơn(xem phần hoạt động). Tuy nhiên, nếu chỉ có nhiêu đó, thì chắc chỉ có ích cho hoạt động duy nhất, đấy là đi phỏng vấn. Nếu bạn là một lập trình viên bình thường, quần đùi chân đất, đọc xong bằng kia chữ, rốt cuộc là ta được cái gì :