Index là gì và vì sao cần nó?

Index là một cấu trúc dữ liệu giúp database tìm kiếm nhanh hơn. Khi một bảng có hàng triệu dòng, index có thể giúp database tìm đúng dữ liệu cần thiết mà không phải đọc toàn bộ bảng.

Để hiểu vì sao, chúng ta sẽ sử dụng PostgreSQL, một hệ quản trị cơ sở dữ liệu quan hệ phổ biến, miễn phí và mã nguồn mở. Những nguyên lý này cũng được áp dụng trong các hệ quản trị khác như MySQL hay SQL Server.

Mọi con số trong khoá đều đo trên PostgreSQL 18 với một bảng 5 triệu xe. Cách dựng lại môi trường này trên máy bạn nằm ở cuối bài.

Điều gì xảy ra khi dữ liệu ngày càng lớn?

Giả sử chúng ta có một website mua bán xe cũ, với thông tin của từng chiếc xe được lưu trong bảng vehicles.

Khi người dùng tìm một chiếc xe theo biển số, ứng dụng thực hiện câu SQL:

SELECT * FROM vehicles WHERE plate = '25F-950.00';

Nếu bảng chỉ có 10.000 xe, truy vấn này thường chạy rất nhanh. Nhưng vài năm sau, website đã có 5 triệu xe. Cũng câu SQL đó, PostgreSQL có thể mất nhiều thời gian hơn đáng kể.

Nguyên nhân nằm ở cách PostgreSQL tìm dữ liệu.

Nếu cột plate không có index, PostgreSQL thường phải đọc lần lượt các dòng trong bảng và kiểm tra biển số của từng xe. Cách tìm kiếm này được gọi là quét tuần tự (sequential scan).

Thử xem PostgreSQL phải kiểm tra bao nhiêu dòng trong hai trường hợp:

10.000 xe 10.000 dòng đã kiểm tra

xe cần tìm

5.000.000 xe 5.000.000 dòng đã kiểm tra gấp 500 lần

xe cần tìm

Với 10.000 xe, PostgreSQL cần kiểm tra 10.000 dòng. Khi bảng tăng lên 5 triệu xe, lượng dữ liệu phải kiểm tra tăng gấp 500 lần. Dù chỉ có một chiếc xe khớp với biển số cần tìm, PostgreSQL vẫn phải kiểm tra hết bảng để đảm bảo không bỏ sót kết quả nào.

Trong một phép thử với PostgreSQL 18 trên Apple M5, truy vấn mất khoảng 0,8 ms khi bảng có 10.000 xe và 113 ms khi bảng có 5 triệu xe.

Vấn đề không nằm ở việc so sánh biển số. Mỗi lần so sánh rất nhanh, nhưng thực hiện nó hàng triệu lần thì lại tốn thời gian.

Index giúp tìm kiếm nhanh hơn như thế nào?

Thay vì mỗi lần tìm xe đều phải kiểm tra cả bảng, chúng ta có thể tạo một index trên cột plate:

CREATE INDEX ON vehicles (plate);

PostgreSQL sẽ tạo thêm một cấu trúc dữ liệu riêng để tra cứu biển số. Trong index, các giá trị được tổ chức theo thứ tự, kèm thông tin giúp xác định dòng dữ liệu tương ứng trong bảng.

Khi cần tìm biển số 25F-950.00, PostgreSQL có thể tra cứu trong index để xác định những dòng cần đọc, thay vì kiểm tra lần lượt cả 5 triệu xe.

Trong cùng phép thử trước đó, thời gian truy vấn giảm từ 113 ms xuống khoảng 0,03 ms.

Tất nhiên, index không phải lúc nào cũng nhanh hơn. Nếu một câu SQL cần đọc phần lớn dữ liệu trong bảng, PostgreSQL có thể chọn quét tuần tự thay vì sử dụng index.

Nhưng với những truy vấn chỉ cần tìm một vài dòng trong hàng triệu dòng dữ liệu, index có thể tạo ra sự khác biệt rất lớn.

Chúng ta đã nói nhiều đến việc PostgreSQL đọc và kiểm tra từng dòng. Nhưng dữ liệu thực sự được lưu trữ như thế nào, và PostgreSQL tìm đến một dòng cụ thể bằng cách nào?

PostgreSQL thực sự tìm một dòng dữ liệu như thế nào?

Thiết lập môi trường

Repository của khoá: mt26691/database-index-hoat-dong-nhu-the-nao. Nó chứa dữ liệu mẫu, file Docker Compose và file SQL của từng bài; README.md có hướng dẫn chi tiết.

Máy cần cài Docker, không cần cài PostgreSQL. Clone repository và khởi động PostgreSQL:

git clone https://github.com/mt26691/database-index-hoat-dong-nhu-the-nao.git
cd database-index-hoat-dong-nhu-the-nao
docker compose up -d --wait

Lần khởi động đầu, lệnh cuối tải PostgreSQL 18 và tự tạo bảng vehicles 5 triệu xe, mất khoảng một phút. Không cần tạo database hay import dữ liệu bằng tay.

Chạy SQL của bài này:

docker compose exec db psql -f bai/01-index-la-gi.sql

Mở PostgreSQL để chạy các truy vấn khác:

docker compose exec db psql

Số mili giây trên máy bạn sẽ khác số trong bài, tuỳ cấu hình máy. Các lệnh khác, cách kết nối bằng DBeaver hay pgAdmin, và cách xoá môi trường có trong README.md của repository.