SQL - Index hoạt động như thế nào?

anqua

• 4 min read

Uầy uầy uây uây
Sao mơí query có tí mà database quay quay?

Đánh index vào em ơi. Có index query mơí nhanh được.

Vậy thì index là cái chi chi? Nó hoạt động thế nào? Sao nó lại nhanh? Cùng mình "back to the old school" tìm hiểu nhé!

Index là cái chi chi?

Khi bạn muốn tìm kiếm nội dung trong 1 quyển sách, đầu tiên bạn nghĩ ngay đến mục lục của nó. Khi đã có mục lục của cuốn sách, việc tìm kiếm nội dung nhanh chóng và đỡ tốn công hơn rất nhiều so với việc bạn phải lật từng trang.

Đối vơí database cũng vậy
Index là 1 bảng tra cứu đặc biệt mà Database Search Engine có thể sử dụng để tăng nhanh thời gian và hiệu suất thu thập dữ liệu. Hiểu đơn giản, index trong một Database là tương tự như Mục lục của cuốn sách.

Index hoạt động như thế nào?

Index ra đời để giải bài toán tìm kiếm.
Thời sinh viên, có môn "Cấu trúc dữ liệu và giải thuật" chắc anh em đều đã được học các thuật toán tìm kiếm + độ phức tạp thuật toán. Lúc đi học học kiểu qua loa, đi làm mơí thâý nó quan trọng thật =))

Index cũng hoạt động dưạ trên 1 trong số đó: "Binary Search" hay còn gọi là "Tìm kiếm nhị phân"

So sánh nhanh Liner Search và Binary Search:

Liner Search có độ phức tạp trung bình là: O(n/2)
Binary Search có độ phức tạp trung bình là: O(log(n))

Nhưng để sử dụng Binary Search, tập dữ liệu của chúng ta cần được sắp sếp. SQL dùng B-Tree để thực hiện điều đó

B-Tree

B-tree là một kiến 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ách hoạt động của B-Tree tương tự cây nhị nhân

Tuy nhiên chúng có 1 điểm khác biệt lớn đấy là

  • Cây nhị phân phát triển theo chiều cao. Môĩ node sẽ chỉ có 2 keys
  • B-Tree phát triển theo chiều rộng. Hạn chế tối đa chiều cao. 1 node có nhiều keys

Tại sao lại vậy? Theo dõi 1 gif hoạt động tìm kiếm của cây nhị phân nhé

  • Dữ liệu được lưu vào Disk (ổ cứng) dươí dạng các Blocks (khôí)
  • Khi duyệt 1 node, các keys của node được đọc từ Disk và lưu vào RAM
  • Tốc độ đọc dữ liệu từ Disk lâu gấp rất nhiều lần đọc từ RAM

Do đó, để giảm thời gian tìm kiếm. Chúng ta cần giảm số lần duyệt node. Đồng nghĩa giảm tối đa chiều cao của cây.

Đối vơí cây nhị phân, chiều cao của cây ngày càng tăng > tốc độ tìm kiếm ngày càng giảm.

B-Tree hạn chế tối đa chiều cao cây bằng cách lưu nhiều keys vào 1 node thay vì 2 keys

Về 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 ấy.
Baì viết này mình xin phép chỉ nhăc tới cơ chế, không đi sâu vào phân tích B-Tree. Bạn đọc có thể research thêm về B-Tree trong database nhé

Tính toán xem có đúng là xài index thì nhanh hơn thật không nào

Giả sử:
Chúng ta có bảng posts như sau

id - int - 4 bytes
name - string(255) - 255 bytes

Kích thước 1 records: 4 + 255 = 259 bytes

Data lưu vào disk dươí dạng blocks, môĩ blocks có size là 1024 bytes

=> Mỗi blocks lưu: 1024/259 = 3 records

Bảng "posts" có 10_000_000 records

=> Cần sử dụng 3_333_334 blocks

Liner Search có độ phức tạp trung bình là: O(n/2)
Binary Search có độ phức tạp trung bình là: O(log2(n))

Query không sử dụng index:

Số lần đọc vào blocks là: 3_333_334/2 = 1_666_667 lần

Query sử dụng index:

Số lần đọc vaò blocks là: log2(3_333_334) = 22 lần

Một sự khác biệt khủng khiếp đúng không nào?