Giới thiệu về Đánh chỉ mục (Indexing) trong SQL

Trong hướng dẫn này, hãy tìm hiểu về đánh chỉ mục trong cơ sở dữ liệu và các kỹ thuật đánh chỉ mục khác nhau.

Đã cập nhật 5 thg 10, 2026 · 14 phút đọc

Khám phá cùng AI

Là một nhà khoa học dữ liệu, bạn sẽ thường xuyên phải xử lý khối lượng dữ liệu khổng lồ. Làm việc với dữ liệu (tồn tại với số lượng lớn) không hề đơn giản. Vì vậy, để xử lý hiệu quả nhất có thể, bạn cần hiểu rõ cách dữ liệu được tổ chức ở cấp độ vật lý để có thể xử lý chúng bằng những kỹ thuật tiện dụng.

SQL là một kỹ năng bắt buộc đối với mọi kỹ sư phần mềm hiện đại vì hầu hết phần mềm đều phụ thuộc vào một dạng dữ liệu nào đó và tích hợp tốt với RDBMS (Hệ quản trị cơ sở dữ liệu quan hệ). Dù là ứng dụng web, API hay ứng dụng nội bộ, RDBMS luôn hiện diện. Và SQL là ngôn ngữ để truy vấn RDBMS.

Với vai trò là nhà khoa học dữ liệu, việc biết SQL và các kỹ thuật liên quan là điều thiết yếu. Để có thể truy vấn RDBMS và tìm câu trả lời cho các câu hỏi cụ thể về dữ liệu bạn đang xử lý, SQL là yêu cầu tối thiểu.

Trong video mới nhất với DataCamp, David Robinson (Chief Data Scientist @ DataCamp) đã cho chúng ta thấy cách anh ấy sử dụng SQL trong một bài toán Khoa học Dữ liệu. Hãy xem thử. Quy trình làm việc của anh ấy rất thú vị.

Hôm nay bạn sẽ tìm hiểu về một kỹ thuật gọi là đánh chỉ mục (Indexing), chủ yếu liên quan đến việc tổ chức dữ liệu bên trong cơ sở dữ liệu, và bạn sẽ triển khai một số kỹ thuật bằng SQL. Điều này sẽ cho bạn cái nhìn tổng quan về cách đánh chỉ mục có thể được dùng để lưu trữ thông tin trong cơ sở dữ liệu và cách nó giúp rút ngắn thời gian thực thi.

Lưu ý: Trước khi bắt đầu đọc hướng dẫn này, rất khuyến nghị bạn học các kiến thức cơ bản về SQL nếu bạn chưa quen thuộc. Khóa Intro to SQL for Data Science của DataCamp là một nguồn tài liệu tuyệt vời nếu bạn muốn ôn lại những điều cơ bản của SQL.

Ghi chú ngắn về cách tổ chức các bản ghi trong tệp

Trước khi tìm hiểu về đánh chỉ mục, điều bắt buộc là bạn phải hiểu cách dữ liệu được tổ chức vật lý bên trong các tệp. Dĩ nhiên, bạn sẽ không đi sâu vào mọi chi tiết, nhưng có cái nhìn tổng quan tốt về cách tổ chức sẽ giúp bạn hiểu đánh chỉ mục rõ ràng hơn. Bắt đầu thôi.

Về tổng thể, việc tổ chức các bản ghi/dữ liệu liên quan đến cách các bản ghi được lưu trữ và có thể chia rộng rãi thành hai kiểu:

Tổ chức có thứ tự: Tất cả bản ghi trong một tệp được sắp xếp theo một giá trị khóa tìm kiếm nào đó. Tìm kiếm nhị phân thường được áp dụng để tìm kiếm trong tệp có thứ tự. Điều này giúp tìm kiếm rất hiệu quả vì độ phức tạp thời gian tìm kiếm nằm trong thời gian lôgarit. Nhưng việc chèn vào tệp trở thành thao tác tốn kém vì bạn có thể phải tổ chức lại toàn bộ tệp để chứa mục mới.
Tổ chức không có thứ tự: Ở kiểu này, bản ghi được chèn vào nơi nào còn chỗ trong tệp, thường là cuối tệp. Vì sử dụng tìm kiếm tuyến tính cho kiểu này, việc tìm kiếm không hiệu quả bằng biến thể trước đó, nhưng chèn thì không quá tốn kém.

Mặc dù bạn có tổ chức tệp có thứ tự, điều gì xảy ra nếu kích thước khối của tệp và kích thước mỗi bản ghi bên trong tệp rất lớn? Hãy khám phá điều này trong phần tiếp theo.

Nhu cầu đánh chỉ mục

Bạn sẽ bắt đầu phần này bằng cách tìm hiểu động lực đằng sau việc sử dụng đánh chỉ mục để lưu trữ tệp/thông tin một cách hiệu quả và cách nó cải thiện các thao tác khác liên quan đến các tệp/thông tin đó.

Giả sử bạn có một bảng (quan hệ) gồm nhiều bản ghi trong cơ sở dữ liệu. Các bản ghi được chia thành 1000 khối. Về mặt trực quan, cách tổ chức trông như sau:

Từ cấu trúc trên, có thể thấy rằng:

Thứ tự được áp dụng cho cột đầu tiên của các bản ghi (coi đây là hệ cơ sở dữ liệu quan hệ trong đó dữ liệu được tổ chức theo dạng bảng)
Số lượng khối mà tổng dữ liệu được chia ra - 1000 khối.

Hãy nhớ rằng mỗi bản ghi còn có các cột khác, nhưng trong tổ chức này, thứ tự được áp dụng cho cột đầu tiên và các khối được chia theo đó. Giờ, nếu bạn thực hiện tìm kiếm nhị phân để tìm bất kỳ thứ gì trong tổ chức/bản ghi này, tổng thời gian sẽ là - $\log_{2}1000$, tương đương 10 đơn vị thời gian. Liệu thời gian tìm kiếm này có thể cải thiện không?

Đương nhiên là có.

Hãy liên hệ điều này với việc đọc một cuốn sách mà không có trang mục lục. Bạn mở ngẫu nhiên một trang (hoặc trong trường hợp tìm kiếm nhị phân, bạn mở trang giữa cuốn sách) rồi lật trái phải để đến trang bạn muốn. Chắc chắn tốn thời gian. Đúng không?

Nhưng nếu cuốn sách có trang mục lục, việc tìm kiếm sẽ hiệu quả hơn nhiều. Bạn có thể đến ngay trang cần chỉ bằng cách xem mục lục. Bạn có thể áp dụng đánh chỉ mục theo cách tương tự cho tình huống ở trên.

Dưới đây là tóm tắt cách bạn có thể áp dụng đánh chỉ mục ở đây:

Duy trì một con trỏ khối cho mỗi khối kèm theo các giá trị đã sắp xếp dùng trong cách tổ chức trước đó.

Điều này sẽ dẫn đến ít khối hơn được dùng để lưu tệp dữ liệu. Giờ, để tìm một bản ghi cụ thể, bạn chỉ cần tìm kiếm qua cấu trúc mới này gồm ít khối hơn và cuối cùng sẽ lấy được bản ghi (nếu có) trong thời gian ngắn hơn nhiều. Hãy hình dung điều này. Giả sử số bản ghi sau khi đánh chỉ mục dẫn đến 8 khối, bạn sẽ có cấu trúc như sau:

Thời gian tìm kiếm sẽ giảm mạnh nhờ số lượng khối ít hơn. Giả sử bạn muốn tìm bản ghi 90. Trong sơ đồ đánh chỉ mục mới này, trước tiên bạn sẽ phải xác định con trỏ khối tương ứng của nó, trong trường hợp này là 3, rồi dùng thông tin đó để tìm các bản ghi dữ liệu gốc chỉ trong một lần truy cập.

Vì vậy, thời gian tìm kiếm trong trường hợp này sẽ là $\log_{2}8 + 1$ = 4 đơn vị thời gian, giảm đáng kể so với trước.

Ví dụ trên giới thiệu nhu cầu thực hiện đánh chỉ mục. Dưới đây là một số điểm đáng lưu ý về đánh chỉ mục:

Việc sắp xếp trên dữ liệu gốc chỉ có thể thực hiện theo một trường. Sau đó các mục của trường này có thể được đánh chỉ mục tương ứng. Chỉ khi bạn tìm kiếm theo trường đó, thời gian tìm kiếm mới được cải thiện. (Cực kỳ quan trọng)
Các chỉ mục cũng được sắp xếp.
Bản ghi chỉ mục gồm hai trường (cấu trúc của tệp chỉ mục):
- Khóa của tệp gốc
- Con trỏ tới khối nơi khóa xuất hiện trong dữ liệu gốc
Tìm kiếm nhị phân được dùng để duyệt qua các chỉ mục.
Để truy cập một bản ghi bằng các mục chỉ mục, số lần truy cập khối trung bình cần thiết -$\log_{2}B_i + 1$, trong đó $B_i$ là số khối trong các bản ghi đã đánh chỉ mục
Có thể tạo chỉ mục trên bất kỳ trường nào của quan hệ (khóa chính, khóa ứng viên, trường không phải khóa).

Giờ đây, dựa trên cách sắp xếp dữ liệu gốc và số bản ghi bạn sẽ duy trì trong tệp chỉ mục, có thể có nhiều sơ đồ đánh chỉ mục khác nhau. Ở phần tiếp theo, bạn sẽ tìm hiểu những loại phổ biến nhất.

Các chiến lược đánh chỉ mục khác nhau:

Đánh chỉ mục dày đặc (Dense Indexing): Nếu tạo mục chỉ mục cho mỗi giá trị khóa tìm kiếm, đó là đánh chỉ mục dày đặc. Hãy xem sơ đồ sau để hình dung.

Đánh chỉ mục thưa (Sparse Indexing): Nếu chỉ tạo mục chỉ mục cho một số bản ghi, đó là đánh chỉ mục thưa. Dưới đây là sơ đồ mô tả trực quan.

Các sơ đồ trên giúp cả hai sơ đồ đánh chỉ mục trở nên dễ hiểu. Một điểm then chốt bạn cần lưu ý là ví dụ về đánh chỉ mục thưa ở trên là sự kết hợp của cả dày đặc và thưa. Bởi vì đối với mỗi giá trị khóa tìm kiếm duy nhất (1, 2 và 3) đều có chỉ mục, nhưng không phải mỗi bản ghi dữ liệu đều có chỉ mục.

Giờ bạn sẽ tìm hiểu các loại sơ đồ đánh chỉ mục khác dựa trên cấp độ bản ghi. Trong đánh chỉ mục một cấp, số lượng tệp chỉ mục chỉ là một. Nhưng đôi khi kích thước tệp chỉ mục trở nên quá lớn đến mức bản thân tệp chỉ mục cũng được đánh chỉ mục. Khi đó gọi là đánh chỉ mục đa cấp. Hãy đi sâu hơn.

Dưới đây là tổng quan về các chiến lược đánh chỉ mục tiếp theo dựa trên cấp bậc.

Đánh chỉ mục một cấp:

Đánh chỉ mục sơ cấp (Primary indexing)
Đánh chỉ mục gom cụm (Clustered indexing)
Đánh chỉ mục thứ cấp (Secondary indexing)

Đánh chỉ mục đa cấp:

Cây B (B Tree)
Cây B+ (B+ Tree)

Bạn sẽ học tất cả các chiến lược đánh chỉ mục thuộc nhóm đánh chỉ mục một cấp. Ở cuối hướng dẫn này, bạn sẽ có liên kết để khám phá các sơ đồ đánh chỉ mục đa cấp nếu quan tâm. Giờ hãy xem xét Đánh chỉ mục sơ cấp.

Đánh chỉ mục sơ cấp:

Một chỉ mục sơ cấp là một tệp có thứ tự với các bản ghi có độ dài cố định gồm hai trường:

Trường thứ nhất trùng với khóa chính của tệp dữ liệu.
Trường thứ hai là con trỏ tới khối dữ liệu nơi khóa chính xuất hiện. - Nguồn

Chỉ mục được tạo cho bản ghi đầu tiên của mỗi khối được gọi là neo khối (block anchors). Trong đánh chỉ mục sơ cấp, số mục chỉ mục = số khối dữ liệu gốc. Số lần truy cập khối trung bình khi dùng chỉ mục sơ cấp là:

$\log_{2}B_i + 1$, trong đó $B_i$ là số khối trong các bản ghi đã đánh chỉ mục.

Tham khảo sơ đồ sau để hiểu rõ hơn:

Hình ngoài cùng bên phải là dữ liệu gốc được chia thành nhiều khối. Lưu ý cột chứa các số 1,2,3,...,9 là các khóa chính. Hình ngoài cùng bên trái là các mục chỉ mục, trong đó mỗi mục gồm:

Mục đầu tiên của mỗi khối dữ liệu (neo khối)
Mục thứ hai biểu thị con trỏ khối.

Hãy dành chút thời gian nghĩ xem đây là loại đánh chỉ mục nào (Thưa hay Dày đặc). Dùng phần bình luận để đăng câu trả lời của bạn.

Giờ bạn sẽ học về Đánh chỉ mục gom cụm.

Đánh chỉ mục gom cụm:

Đánh chỉ mục gom cụm được tạo trên tệp dữ liệu mà các bản ghi trong tệp được sắp xếp vật lý theo một trường không phải khóa và trường này không có giá trị riêng biệt cho mỗi bản ghi. Trường này được gọi là trường gom cụm (clustering field) dùng để đánh chỉ mục. Do đó có tên gọi - đánh chỉ mục gom cụm.

Sơ đồ luôn giúp dễ hiểu hơn. Như bạn thấy, dữ liệu gốc được sắp xếp theo một thuộc tính không phải khóa và với mỗi giá trị khác nhau của thuộc tính không phải khóa, một mục chỉ mục được tạo. Số lần truy cập khối trung bình cần để định vị một bản ghi cụ thể bằng sơ đồ này là $\geq$ $\log_{2}B_i + 1$, trong đó $B_i$ là số khối trong các bản ghi đã đánh chỉ mục. Lưu ý dấu $\geq$ ở đây.

Trong đánh chỉ mục gom cụm, sau khi xác định được khối chứa một khóa cụ thể, bạn có thể phải duyệt qua các khối khác nữa (điều này thể hiện khá rõ từ hình trên).

Bạn có thể muốn nghĩ xem đây là loại đánh chỉ mục nào (Thưa hay Dày đặc). Dùng phần bình luận để đăng câu trả lời. Giờ hãy học về Đánh chỉ mục thứ cấp.

Đánh chỉ mục thứ cấp:

Giả sử bạn có một bảng tên Employee trong cơ sở dữ liệu. Bảng có các thuộc tính sau:

employee_id
employee_name
employee_department
employee_salary

employee_id là khóa chính. Giờ đây, bạn đã tạo đánh chỉ mục sơ cấp trên bảng này dựa trên employee_id. Nhưng trong quá trình phát triển ứng dụng, bạn phát hiện phần lớn truy vấn cơ sở dữ liệu sử dụng thuộc tính employee_name. Khi đó, đánh chỉ mục sơ cấp sẽ không giúp nhiều, và việc duy trì một chỉ mục riêng cho tất cả các giá trị thuộc employee_name là thực tiễn tốt. Dù sao thì tên nhân viên cũng sẽ không được lưu theo thứ tự trong cơ sở dữ liệu. Vì vậy, đánh chỉ mục cho chúng chắc chắn sẽ tăng tốc các truy vấn liên quan đến tên nhân viên.

Đây là ví dụ kinh điển của đánh chỉ mục thứ cấp. Hãy thử dựng một hình minh họa phù hợp cho đánh chỉ mục thứ cấp:

Hãy thoải mái đăng một biểu diễn tốt hơn trong phần bình luận nếu bạn có.

Giờ bạn sẽ xem cách tạo chỉ mục trong PostgreSQL. Học khóa Joining Data in PostgreSQL của DataCamp nếu bạn muốn nắm vững những điều cơ bản.

Tạo chỉ mục trong PostgreSQL

Trước khi bắt đầu tạo chỉ mục trong cơ sở dữ liệu PostgreSQL, bạn sẽ cần một số dữ liệu trong một bảng. Hãy tạo một bảng đơn giản tên Student gồm các bản ghi sau:

student_id
student_name
student_year

Bạn sẽ đặt student_id làm khóa chính, và không cho phép tên sinh viên và năm học để trống.

Truy vấn như sau:

CREATE TABLE STUDENT(
   student_id TEXT PRIMARY KEY,
   student_name  TEXT NOT NULL,
   student_year  TEXT NOT NULL
);

Sau khi tạo bảng thành công, bạn sẽ cần chèn một số dữ liệu phù hợp vào bảng. Để tiện lợi, bạn có thể dùng tệp .csv này và nhập vào Student. Bạn có thể nhập một tệp .csv tương thích vào bảng PostgreSQL bằng truy vấn sau:

COPY STUDENT FROM '/path/to/csv/Student.csv' WITH (FORMAT csv);

Truy vấn trên giả định rằng tên tệp .csv từ đó dữ liệu được sao chép là Student.

Hãy xem dữ liệu. Chạy select * from STUDENT; trả về các bản ghi sau:

Truy vấn select sẽ trả về tổng cộng 86 bản ghi. Giờ bạn đã sẵn sàng tạo chỉ mục. Bạn có thể tạo chỉ mục đơn cột bằng cú pháp sau:

CREATE INDEX index_name
ON table_name (column_name);

Hãy tạo một chỉ mục trên trường student_id (đánh chỉ mục sơ cấp).

CREATE INDEX id_index
ON STUDENT (student_id);

Cũng có thể tạo chỉ mục đa cột:

CREATE INDEX id_index
ON STUDENT (student_id,student_name);

Bạn có thể xóa một chỉ mục bằng cú pháp sau:

DROP INDEX index_name;

Khó có thể cảm nhận rõ tác dụng của đánh chỉ mục trong một bảng nhỏ như STUDENT. Nhưng nếu bảng lớn (hãy nghĩ đến bảng cơ sở dữ liệu chứa dữ liệu tương tự của một trường đại học lớn), đánh chỉ mục chắc chắn sẽ đóng vai trò quan trọng.

Bạn đã làm được!

Chúc mừng bạn đã đọc đến cuối. Trong hướng dẫn này, bạn đã học về đánh chỉ mục, nhu cầu, các sơ đồ đánh chỉ mục khác nhau. Bạn cũng đã thấy cách thực hiện đánh chỉ mục đơn giản trong PostgreSQL.

Tuy nhiên, bạn chưa học về đánh chỉ mục đa cấp trong hướng dẫn này. Dưới đây là một số tài nguyên tuyệt vời nếu bạn muốn khám phá:

Nhưng liệu dùng chỉ mục lúc nào cũng có ích? Thực tế có những trường hợp không nên dùng đánh chỉ mục.