Chắc hẳn chúng ta đã quen thuộc với việc đánh index trong SQL để tăng tốc độ truy vấn. Nhưng liệu bạn đã hiểu rõ cơ chế của việc này, tại sao nó lại giúp tăng tốc độ truy vấn và nhược điểm của nó là gì? Trên bài viết này, chúng ta sẽ cùng tìm hiểu về chủ đề này.
1. Vấn đề thực tế
Hãy tưởng tượng bạn đang làm việc với I18n trên website, với 2 file biên dịch en.yml và vi.yml. Mỗi dòng trong en.yml tương ứng với vi.yml và ngược lại. Ví dụ:
en.yml: table: "table"
vi.yml: table: "cái bàn"Điều này có nghĩa là mỗi từ dịch sang tiếng Anh thì phải dịch sang tiếng Việt. Nhưng bạn nhận ra rằng en.yml có 1000 dòng mà vi.yml chỉ có 999 dòng, có nghĩa là bạn đã bỏ sót một từ nào đó trong việc dịch sang tiếng Việt. Bạn cần tìm ra dòng đó để cập nhật, nhưng cách nào để tìm nhanh nhất?
Nếu bạn dò từng dòng thì có thể phải dò tới 999 lần, quá nhiều lần truy vấn. Tuy nhiên, có cách để tìm nhanh hơn chỉ bằng tối đa 10 lần. Bằng cách dò từ trên xuống dưới giữa hai file với nhau và chia ra thành phạm vi tìm kiếm, bạn sẽ chỉ cần tối đa 10 lần để tìm ra dòng còn thiếu. Phương pháp này giống như việc "cưa đôi" phạm vi tìm kiếm và chia nhỏ nó đi từng bước.
Cơ chế đánh index trong SQL cũng dựa vào phương pháp tương tự như vậy.
2. Cơ chế đánh index
Hãy giả sử bạn có một bảng gồm 1000 bản ghi chứa tên của những người: "Phong", "Dung", "Hải",... Bạn muốn tìm người có tên là "Nam". Cơ chế đánh index sẽ hoạt động như thế nào trong trường hợp này?
Khi bạn thực hiện đánh index cho trường :name, index sẽ được đánh từ 0 đến 999 (tổng cộng 1000 bản ghi), theo thứ tự alphabet. Ví dụ: "An" sẽ có index là 0, "Anh" sẽ có index là 1, "Ánh" sẽ có index là 2,... Như vậy, các bản ghi của bạn sẽ được sắp xếp lại theo thứ tự tăng dần theo alphabet.
Khi bạn thực hiện câu truy vấn Select ... where name = "Nam", cơ chế đánh index sẽ sử dụng phương pháp "cưa đôi" mà chúng ta đã đề cập ở trên. Bằng cách so sánh từ khóa "Nam" với bản ghi ở index thứ 500, nhưng không phải so sánh bằng mà là so sánh lớn hơn hay nhỏ hơn. Ví dụ, nếu bản ghi ở index 500 có tên là "Hoàng", khi so sánh, ta nhận thấy "Hoàng" < "Nam" (theo alphabet). Điều này cho thấy "Nam" nằm ở nửa sau, với index lớn hơn 500. Ta tiếp tục "cưa đôi" và tìm kiếm tiếp. Sau tối đa 10 lần so sánh, ta sẽ tìm ra bản ghi có tên là "Nam".
Khi số lượng bản ghi càng nhiều, phương pháp đánh index càng hiển thị rõ ràng công dụng của nó. Ví dụ, nếu bạn có 1 triệu bản ghi, bạn chỉ cần so sánh tối đa 20 lần, vì 2^20 = 1024^2 > 1000^2 = 1000000. Trong khi phương pháp truy vấn thông thường có thể phải so sánh tối đa 999999 lần.
3. Đánh index cho nhiều trường (B tree)
Đánh index cho nhiều trường được gọi là phương pháp B tree.
Hãy giả sử bạn có 1 triệu bản ghi với tên người và tỉnh/thành cố định. Bạn muốn tìm người ở tỉnh "Ninh Bình" có tên là "Nam". Cơ chế index sẽ hoạt động như thế nào trong trường hợp này.
Đầu tiên, bạn sẽ đánh index cho cả trường :province và trường :name. Lúc này, 1 triệu bản ghi sẽ được nhóm lại theo tỉnh/thành trước, và các tỉnh/thành này sẽ được sắp xếp theo thứ tự alphabet. Ví dụ, "An Giang" có index là 0, "Bà Rịa Vũng Tàu" có index là 1, "Bắc Giang" có index là 2,... Trong mỗi nhóm tỉnh/thành, các bản ghi trong trường :name sẽ được đánh index lần nữa. Ví dụ, "An" có index là 0, "Anh" có index là 1, "Ánh" có index là 2,... Việc đánh index trong index như vậy tạo nên các nhánh, từ đó người ta gọi là B tree.
Khi bạn thực hiện câu truy vấn Select ...where province = "Ninh Bình" and name = "Nam", đầu tiên sẽ lọc ra những người ở tỉnh "Ninh Bình". Quá trình này sẽ lấy ra bản ghi đầu tiên của mỗi tỉnh và so sánh với "Ninh Bình" bằng cách sử dụng phương pháp đánh index. Với tổng cộng 64 tỉnh/thành ở Việt Nam, bạn chỉ cần tối đa 6 lần so sánh là có thể tìm ra người ở tỉnh "Ninh Bình". Từ danh sách người ở tỉnh "Ninh Bình", bạn có thể lọc ra người có tên là "Nam" bằng cách sử dụng phương pháp đánh index một lần nữa.
Hình minh họa về B tree
Có thể bạn sẽ thắc mắc về việc chúng ta nên đánh index cho trường nào trước để tối ưu truy vấn, trường :province hay trường :name. Câu trả lời là đánh index cho trường có ít bản ghi hơn trước. Trong bài toán trên, có 64 tỉnh/thành nhưng có hàng trăm ngàn kiểu đặt tên, vì vậy nhóm theo trường :province trước là lựa chọn hợp lý. Khi lọc ra trường :province, bạn đã loại bỏ tới 63/64 tỉnh/thành không liên quan, tương đương với một lượng bản ghi rất lớn. Trong khi đánh index theo trường :name, hầu như mọi bản ghi đều phải được xem xét ít nhất một lần.
Khi đánh index theo thứ tự nào, bạn cũng cần áp dụng đúng thứ tự đó trong câu truy vấn. Nếu không, việc đánh index sẽ không có tác dụng. Ví dụ, nếu bạn đánh index cho trường :province trước và sau đó mới tới trường :name, khi sử dụng câu truy vấn "Select ... where name = 'Nam' and province = 'Ninh Binh'", việc đánh index sẽ không có tác dụng.
4. Nhược điểm của đánh index
Đánh index giúp tăng tốc độ truy vấn, nhưng sau mỗi lần insert, update hoặc delete (thay đổi cơ sở dữ liệu), chúng ta cần thực hiện lại việc đánh index. Do đó, tốc độ của các hoạt động này sẽ giảm đi. Ví dụ, ban đầu "An" có index là 0, "Anh" có index là 1, "Ánh" có index là 2. Khi bạn xóa "An", thì bản ghi "Anh" sẽ có index là 0, "Ánh" sẽ có index là 1, và các bản ghi khác sau đó cũng phải thay đổi tương tự. Nhược điểm của phương pháp đánh index chính là giảm tốc độ của các hoạt động insert, update, delete. Mặc dù nói là giảm, nhưng trong thực tế, khi cập nhật hoặc xóa bản ghi, chúng ta cũng cần truy vấn tới bản ghi đó, điều này làm tăng công việc này và giảm công việc khác. Tuy nhiên, việc giảm từ 999999 lần so sánh xuống còn 20 lần so sánh là đáng đổi.
5. Khi nào không nên dùng đánh index?
Khi số lượng bản ghi quá ít, cụ thể là dưới 10, việc đánh index không hiệu quả vì việc so sánh trực tiếp 10 lần vẫn nhanh hơn việc so sánh lớn hơn hay nhỏ hơn 3 hay 4 lần.
Website của tôi: https://www.websitegiare.co
