[Database Index] P1: Cơ bản về index database trong MySQL

Mở đầu

Việc tối ưu hiệu năng luôn là một vấn đề quan trọng trong các sản phẩm công nghệ, là một điều ảnh hưởng trực tiếp đến trải nghiệm của người dùng ở bất kì sản phẩm cuối nào trong CNTT: Game, Livestream, E-Commerce, … Mặc dù các database hiện nay đã có nhiều cơ chế tự động tối ưu, tuy nhiên ta vẫn cần có những cách để có thể chi phối và giúp cải thiện hiệu năng ứng dụng.

Index trong Database

• Indexes (hay còn được gọi là keys trong MySQL) là một cấu trúc dữ liệu mà MySQL sẽ sử dụng để có thể tìm kiếm một row nào đó nhanh chóng. Index là một phần cực kỳ quan trọng trong việc tối ưu hiệu năng của CSDL, nhất là khi dữ liệu của bạn ngày càng tăng lên nhiều hơn.
• Với một CSDL nhỏ, chỉ khoảng 100-200 row thì ta không cần tới index làm gì cả. Nhưng khi dữ liệu ngày càng tăng lên, hiệu năng có thể sụt giảm nhanh chóng nếu không có index.

Các loại indexes

• Có nhiều loại indexes khác nhau, mỗi kiểu được thiết kế phục vụ cho những mục đích khác nhau. Indexes thường được triển khai ở tầng storage engine, chứ không phải tầng server. Index cũng không được chuẩn hoá, điều này có nghĩa là trên các engine khác nhau, cách hoạt động của chúng cũng sẽ khác nhau.
• Ở bài viết, ta sẽ tìm hiểu theo engine InnoDB

B-tree indexes

• Đây là kiểu indexes thường được nhắc đến phổ biến nhất, khi người ta nói về đánh index database mà không nhắc chính xác là loại index nào, thì khả năng cao đó là B-tree indexes
• Ý tưởng đơn giản của B-Tree là toàn bộ dữ liệu sẽ được lưu theo thứ tự sắp xếp.

• B-Tree tăng tốc độ tìm kiếm dữ liệu vì ta sẽ không cần đi qua cả một bảng để tìm kiếm dữ liệu đang search. Ta sẽ bắt đầu từ node root trên cùng, ở trên root sẽ chứa con trỏ tới các node con theo một quy luật, ví dụ toàn bộ cây bên trái sẽ là những node có giá trị nhỏ hơn node root, còn bên phải thì lớn hơn.

Adaptive hash index

• Engine InnoDB có một cơ chế được gọi là Adaptive hash index. Cơ chế này hoạt động khi nó tự phát hiện một dữ liệu nào đó được truy cập rất nhiều, lúc này dữ liệu đó sẽ được đặt bên trên cả index của cây B-Tree, dạng như cache. GIúp cho dữ liệu này còn có tốc độ truy vấn cao hơn bình thường.
• Tuy nhiên cơ chế này không thể tắt đi, hay điều chỉnh thông số.

Cách hoạt động của index

• Hãy tưởng tượng bạn đang cần tìm tên Nguyễn Quốc Hưng trong một cuốn danh bạ điện thoại dày cộp không có mục lục.

• Lật từng trang để tìm lúc này tìm có vẻ thật bất khả thi, trong trường hợp xấu nhất, nếu tên Nguyễn Quốc Hưng ở cuối và ta lật từ đầu, vậy ta phải lật hết N trang của cuốn sách O(N)

SELECT id FROM books WHERE name = "Hung";

Liệu có cách nào nhanh hơn không ?

Trong thực tế, ta đã luôn vô thức làm cách nhanh hơn. Bạn có thể chỉ cần chọn 1 trang ở giữa, bên trong là tên Minh, M thì ở sau H, lúc này bạn biết hiện tại là ở vùng chữ M, và Hưng (H) không thể xuất hiện ở những trang phía sau nữa được, và ta chỉ cần tìm ngược lại phía trước. Lật 1 trang sách thấy tên của Hoàng Dương (D), ta biết H không thể ở phía trước D, vì vậy ta chỉ cần tìm tiếp trong phần tiếp theo của chữ D.

B-Tree vs Binary Tree

• Có thể bạn sẽ thấy B-Tree khá giống cây nhị phân tìm kiếm, tuy nhiên không hẳn vậy. Cây nhi jphaan tìm kiếm chỉ có một dữ liệu tại một node, trong khi đó B-Tree sử dụng một mảng dữ liệu tại một node và có con trỏ tới các node con ở từng dữ liệu trong mảng.

• Giả sử, ta muốn tìm kiếm một dữ liệu giá trị = 29 trong cây

• Ở node đầu, ta thấy dữ liệu sẽ nằm trong khoảng 10-50, lúc này ta sẽ đi tới node con qua con trỏ lưu từ 10-50

• Tiếp tục lặp lại như vậy cho đến khi ta tìm đến node lá ở dưới cùng chứa dữ liệu thực sự

Một số hạn chế của B-Tree

• B-Tree sẽ không hiệu quả nếu ta tìm kiếm dữ liệu không phải ở bên trái của cột dữ liệu tìm kiếm. Ví dụ

first_name LIKE 'J%'

Tham khảo:

• Database Internals
• https://dev.mysql.com/doc/refman/8.0/en/glossary.html#glos_b_tree