Nguyên lý hoạt động của index: cấu trúc dữ liệu và thuật toán tìm kiếm

Hôm nay tụi mình sẽ đào sâu hơn vào kiến trúc của index và xem thử tụi nó thực sự hoạt động như thế nào bên trong. Biết cách index được xây dựng không chỉ giúp hiểu tại sao query chạy nhanh hơn mà còn biết cách chọn index tối ưu cho từng bài toán khác nhau.

Khi nói về cấu trúc index, ý là dữ liệu được tổ chức bên trong index ra sao để đảm bảo tìm kiếm nhanh nhất. Hãy tưởng tượng một cái tủ tài liệu. Nếu tài liệu cứ chất đống lung tung thì tìm cái cần sẽ rất cực. Nhưng nếu tủ được sắp xếp theo thứ tự alphabet thì tìm kiếm sẽ dễ hơn nhiều. Index hoạt động cũng kiểu vậy: nó sắp xếp dữ liệu để việc tìm thông tin cần thiết diễn ra nhanh nhất có thể.

Cấu trúc B-TREE của index

B-TREE (balanced tree — cây cân bằng) là loại index được dùng nhiều nhất trong PostgreSQL. Về cơ bản, nó là một cấu trúc dạng cây, nơi dữ liệu được tổ chức thành các node, và tìm kiếm diễn ra bằng cách đi từ node gốc xuống các lá.

Nó trông như này nè:

         Gốc
          /       |       \
      Node 1    Node 2    Node 3
     /   \       |       /   \
Lá1  Lá2   Lá3  Lá4  Lá5

Mỗi node chứa các giá trị khóa, giúp điều hướng tìm kiếm. Ví dụ, nếu node gốc chứa các giá trị [10, 20, 30], thì:

• Tất cả dữ liệu nhỏ hơn 10 nằm ở Lá 1.
• Tất cả dữ liệu giữa 10 và 20 — ở Lá 2, vân vân.

Ưu điểm của index B-TREE:

• Tìm kiếm dữ liệu nhanh: độ phức tạp tìm kiếm là O(log n), nhanh hơn nhiều so với tìm tuyến tính.
• Phù hợp cho tìm kiếm theo khoảng (ví dụ, tìm tất cả giá trị giữa 10 và 50).

Ví dụ: giả sử tụi mình có bảng students với cột age. Khi tạo index B-TREE trên cột này:

CREATE INDEX age_idx ON students (age);

PostgreSQL sẽ tạo một cây cân bằng cho các giá trị tuổi, giúp tìm sinh viên theo tuổi hoặc theo khoảng tuổi rất nhanh.

Thuật toán tìm kiếm trong B-TREE

Khi bạn chạy query, PostgreSQL dùng index để tìm dữ liệu như sau:

1. Xác định khóa tìm kiếm (ví dụ, tuổi 25).
2. Bắt đầu từ node gốc.
3. So sánh khóa với các khoảng giá trị trong node và đi tiếp vào node con phù hợp.
4. Lặp lại bước 3 cho đến khi tới lá.
5. Trả về dữ liệu từ lá khớp với khóa.

Ví dụ query:

SELECT * FROM students WHERE age = 25;

Index giúp giảm số lượng dữ liệu cần quét, đảm bảo tìm kiếm nhanh.

Thuật toán tìm kiếm và hiệu năng

Index tăng tốc tìm kiếm bằng cách giảm số dòng cần quét. Không có index, PostgreSQL sẽ quét toàn bộ bảng (cái này gọi là quét tuần tự, hay Seq Scan). Có index thì sẽ dùng quét theo index (Index Scan), nhanh hơn nhiều.

So sánh quét tuần tự và quét theo index

• Quét tuần tự (Seq Scan):

  • PostgreSQL đọc từng dòng của bảng, kiểm tra điều kiện query rồi trả về dòng phù hợp.
  • Dùng khi không có index hoặc query lấy gần hết dữ liệu trong bảng.

• Quét theo index (Index Scan):

  • PostgreSQL dùng index để tìm dòng phù hợp, sau đó chỉ đọc bảng cho các dòng đó.
  • Nhanh hơn nhiều với bảng lớn nếu query chỉ lấy một phần nhỏ dữ liệu.

Ví dụ: không có index, tìm theo tuổi

SELECT * FROM students WHERE age = 25;

kết quả có thể phải đọc 1 triệu dòng. Có index B-TREE thì hệ thống chỉ đọc khoảng 100 dòng thôi chẳng hạn.

Ảnh hưởng của cấu trúc index tới hiệu năng

Index chạy nhanh hơn vì nó giảm lượng dữ liệu cần quét. Ví dụ, nếu bảng có hàng triệu dòng, index sẽ tổ chức lại để query chỉ cần đọc vài node thay vì cả bảng.

Hiểu cấu trúc index là rất quan trọng. Biết index hoạt động thế nào sẽ giúp bạn hiểu tại sao một số query lại chậm và cách tăng tốc chúng.

Thêm nữa, cần biết nên dùng loại index nào. Tìm theo khoảng thì dùng B-TREE. Tìm trong array hoặc JSONB thì dùng GIN. Chọn sai index có thể làm database chậm đi.

Ví dụ thực tế

Cùng xem index giúp tụi mình làm việc như thế nào nha.

Index cho sắp xếp

CREATE INDEX salary_idx ON employees (salary);
SELECT * FROM employees ORDER BY salary;

Có index B-TREE, PostgreSQL có thể trả về dữ liệu đã sắp xếp trực tiếp từ index, không cần sort thêm.

Index cho khoảng giá trị

CREATE INDEX price_idx ON products (price);
SELECT * FROM products WHERE price BETWEEN 100 AND 500;

Index B-TREE giúp tìm nhanh các dòng nằm trong khoảng giá trị chỉ định.

Câu hỏi thường gặp và những điểm cần chú ý

Tại sao không phải lúc nào cũng nên dùng index? Index chiếm dung lượng ổ cứng và làm chậm thao tác insert, update, delete vì phải cập nhật lại cấu trúc index. Nên chỉ tạo index cho các cột hay dùng trong query thôi nha.

Khi nào index không giúp ích? Với query lấy gần hết bảng (ví dụ, WHERE true), PostgreSQL sẽ chọn Seq Scan vì đọc node index không mang lại lợi ích gì.