Khi tối ưu hóa hiệu năng cơ sở dữ liệu, việc đầu tiên mà nhiều người nghĩ đến là tạo index cho các trường trong bảng. Tuy nhiên, không phải ai cũng hiểu rõ index là gì và cơ chế hoạt động của nó ra sao. Bài viết này sẽ giải thích chi tiết về cơ chế hoạt động và tác dụng của index trong database, giúp bạn hiểu rõ hơn về công cụ mạnh mẽ này.
Mục Lục
Tại Sao Cần Index Trong Database?
Hãy tưởng tượng bạn cần lưu trữ danh sách thành viên theo tên và tìm kiếm một tên cụ thể khi cần. Cách đơn giản nhất là lưu vào một mảng và thêm giá trị khi có thành viên mới. Tuy nhiên, để kiểm tra xem một thành viên đã tồn tại trong mảng hay chưa, bạn cần duyệt toàn bộ mảng. May mắn thì bạn có thể tìm thấy ngay, nhưng cũng có thể phải duyệt đến cuối mảng.
Để tiết kiệm thời gian tìm kiếm, chúng ta có thể sử dụng thuật toán tìm kiếm nhị phân (binary search). Với mảng đã được sắp xếp, mỗi khi muốn tìm một phần tử, ta chọn phần tử ở giữa mảng và so sánh. Nếu phần tử cần tìm lớn hơn phần tử giữa, ta chọn nửa bên phải, ngược lại chọn nửa bên trái. Quá trình này lặp lại cho đến khi tìm thấy phần tử cần tìm.
Ví dụ trên là một dạng của cây nhị phân (Binary-Tree). Thay vì lưu trữ giá trị của mảng, nó giữ con trỏ trỏ đến node tiếp theo.
B-Tree Là Gì?
B-tree là một cấu trúc dữ liệu để lưu trữ dữ liệu dưới dạng các node được sắp xếp theo thứ tự nhất định.
Cấu trúc B-Tree minh họa các node và liên kết
B-Tree lưu trữ dữ liệu theo cách mỗi node lưu trữ key theo thứ tự tăng dần. Mỗi node này chứa các liên kết đến những node trước và sau nó. Node bên trái có key nhỏ hơn hoặc bằng key của node hiện tại, còn node bên phải thì có key lớn hơn hoặc bằng key của node hiện tại. Nếu một node có n keys thì nó sẽ có tối đa n + 1 node con.
B-Tree index tăng tốc độ truy vấn dữ liệu vì storage engine không phải duyệt toàn bộ bảng để tìm kiếm. Thay vào đó, nó sẽ đi từ node gốc (root). Các node gốc chứa con trỏ tới các node con. Bằng cách so sánh giá trị cần tìm với các giá trị trong node con và xác định các giới hạn trên và dưới của một node, storage engine có thể dễ dàng tìm kiếm sự tồn tại của một giá trị.
Cấu trúc tổng quát của B-Tree được thể hiện như sau:
Cấu trúc tổng quát của B-Tree với các node và con trỏ
Cách B-Tree Index Hoạt Động Trong Database
Cấu trúc của B-Tree khá phức tạp vì nó không chỉ lưu trữ index mà còn lưu trữ cả value liên kết với index đó. Giá trị này liên kết đến bản ghi dữ liệu thực tế trong database, cặp key-value này được gọi là payload.
Mô hình Key-Value trong B-Tree Index
Để hiểu rõ hơn về cơ chế lưu trữ và tìm kiếm kiểu B-Tree, hãy xem ví dụ sau:
Tạo một bảng dữ liệu:
CREATE TABLE People (
last_name varchar(50) not null,
first_name varchar(50) not null,
dob date not null,
gender enum('m', 'f')not null,
key(last_name, first_name, dob)
);Trong bảng People, index được tạo trên các cột last_name, first_name, và dob.
Bảng People với index trên last_name, first_name, dob
Thứ tự của index phụ thuộc vào thứ tự cột trong quá trình tạo bảng. Khi các giá trị trùng nhau, giá trị tiếp theo sẽ được dùng làm tiêu chí để sắp xếp. Ví dụ, hai người có cùng tên là Basinger Viven, nhưng khác ngày sinh, thì ngày sinh sẽ được dùng để sắp xếp. Điều này giúp B-Tree index có thể tìm kiếm và sắp xếp dữ liệu một cách hiệu quả.
Các Kiểu Truy Vấn Hiệu Quả Với B-Tree
B-Tree rất hữu ích trong việc tìm kiếm đầy đủ giá trị, hoặc trong một dải giá trị (key range), hoặc một tiền tố xác định (key prefix). Trong ví dụ trên, B-tree có thể được sử dụng để:
Tìm kiếm đầy đủ giá trị (Full value)
Tìm kiếm tất cả các giá trị đầy đủ trong những cột đã được đánh index. Ví dụ, tìm kiếm những người có tên Cuba Allen và sinh năm 1960-01-01.
Tìm kiếm tiền tố bên trái (Leftmost Prefix)
Tìm kiếm tất cả những người có tên Allen. Điều này chỉ ứng dụng với cột đầu tiên trong index.
Tìm kiếm tiền tố cột (Column Prefix)
Tìm kiếm những người có last_name bắt đầu bằng chữ cái J. Điều này cũng chỉ hữu ích cho cột đầu tiên của index.
Tìm kiếm trong một dải các giá trị (Range)
Tìm kiếm những người có tên nằm trong khoảng từ Allen đến Barymore. Tuy nhiên, nó cũng chỉ hữu ích với cột đầu tiên của Index.
Tìm kiếm một phần và một dải trong phần tiếp theo (Partial and Range)
Tìm kiếm những người có last_name là Allen và có first_name bắt đầu bằng ký tự K. Nó chỉ có tác dụng với last_name và một dải của first_name.
Vì các node trên tree đã được sắp xếp, chúng có thể thực hiện cả hai việc: tìm kiếm giá trị và tìm kiếm trên một tập đã sắp xếp. Điều này làm cho B-Tree trở thành một công cụ mạnh mẽ cho việc tối ưu hóa truy vấn.
Một Số Giới Hạn Của B-Tree
- Giới hạn lớn nhất của B-Tree là nó chỉ tìm kiếm tốt tại cột ngoài cùng bên trái của index.
- Bạn không thể bỏ qua các cột trong index. Ví dụ, không thể chỉ tìm kiếm từ
last_namevàdobmà bỏ quafirst_name. - Storage engine không thể tối ưu truy vấn với bất kỳ cột nào nằm bên phải một dải giá trị. Ví dụ, nếu bạn truy vấn
WHERE last_name="Smith" AND first_name LIKE 'J%' AND dob='1976-12-23', thì index sẽ chỉ có tác dụng trên hai cột đầu tiên bên trái. Bởi vìLIKEở đây được hiểu như một dải các giá trị.
Qua đây, chúng ta có thể thấy rằng việc sắp xếp các cột trong index là vô cùng quan trọng. Để có hiệu suất tối ưu, việc tạo chỉ mục cho cùng một cột với các thứ tự khác nhau là cần thiết.
Tạo B-Tree Index Trong MySQL
Tạo Index lúc tạo bảng:
CREATE TABLE t(
c1 INT PRIMARY KEY,
c2 INT NOT NULL,
c3 INT NOT NULL,
c4 VARCHAR(10),
INDEX (c2,c3)
);Thêm index vào bảng có sẵn:
CREATE INDEX index_name ON table_name (column_list);Thêm index cho một cột:
CREATE INDEX idx_c4 ON t(c4);Kết luận
Bài viết đã giới thiệu về khái niệm đánh chỉ số (indexing) trong database, tập trung vào B-Tree index. Mục đích của indexing là tăng performance của hệ thống, giúp truy vấn nhanh hơn. Tuy nhiên, nhược điểm lớn là insert hay update sẽ chậm đi vì hệ thống cần sắp xếp lại chỉ số. Giống như việc sắp xếp sách trên giá, nó có tác dụng cho lần tìm kiếm về sau nhưng lại tốn thời gian để tìm được một nơi đặt phù hợp. Hy vọng bài viết này giúp bạn hiểu rõ hơn về B-Tree index và cách nó hoạt động trong cơ sở dữ liệu.