Database Index - P1

Ai cũng hiểu Index sẽ làm tốc độ query nhanh hơn nhưng không phải ai cũng hiểu index là gì, cơ chế hoạt động, lưu trữ như thế nào và nguyên nhân vì sao lại giúp tăng tốc độ truy vấn.

MỤC LỤC

1. Database index là gì?
2. Tại sao Database Index giúp cải thiện tốc độ query.
3. Cơ chế hoạt động, lưu trữ của Index.
4. Ưu, nhược điểm của Database index.
5. Áp dụng vào thực tế phát triển.

1. Database index là gì?

• Hãy tưởng tượng cuốn từ điển Anh-Việt có khoảng 100.000 từ và thứ tự sắp xếp của nó không theo bảng chữ cái ABC. Vậy để tìm từ "favorite" bạn sẽ phải mở từng trang, kiểm tra từng từ. Một bài toán đơn giản, mỗi trang 20 từ, để kiểm tra hết 1 trang mất 2s. Tức là trường hợp xấu nhất là phải tìm cả 5000 trang từ điểm để tìm ra từ cần tìm, nghĩa là bạn đã mất 5000 trang * 2s = 10000s (27 giờ) để tra được nghĩa của 1 từ.
• Nếu tất cả đều là trường hợp xấu nhất thì tức là bạn mất (27 * 100.000 từ) / (24 * 365) = 308 năm để tra hết từ trong từ điển. Cả mấy cuộc đời để đi tra từ điển luôn :))
• Trong trường hợp từ điển được sắp xếp, bạn chỉ mất 30s để tìm ra từ cần tìm. 30/10000s = 0.003 (0.3%).

=> Vậy Database index tương tự với việc sắp xếp từ điển Anh-Việt theo bảng chữ cái ABC.

2. Tại sao Database Index giúp cải thiện tốc độ query.

Ví dụ:

• Database: MySQL
• Bảng User gồm các trường:

Field name       Data type      Size on disk
id (Primary key) Unsigned INT   4 bytes
name             Char(100)      100 bytes
email            Char(100)      100 bytes

• Số lượng bản ghi của User là 10.000.000 (10 triệu)
• Sử dụng Storage Engine: MyISAM
• Bài toán: Tìm kiếm tất cả các bản ghi User có name là Trần Quang Hợp

Trường hợp 1: Khi chưa index trường name

• 10.000.000 bản ghi, mỗi bản ghi có độ lớn là 204 bytes. My ISAM sử dụng default block là 1.024 bytes, mỗi block sẽ chứa đc ~ 1.024/204 = 5 bản ghi => Số lượng block được tạo ra là 10.000.000/5 = 2.000.000 blocks.
• Vì name không phải unique nên để giải bài toán trên, Database cần phải truy cập 2.000.000 blocks để đưa ra được kết quả. Nếu thời gian truy cập mỗi block là 0.01 ms. Thì sẽ mất 2.000.000 * 0.01 ms = 20.000 ms để hoàn thành câu query

Trường hợp 2: Khi đã index trường name

• Chúng ta tạo 1 bảng Index cho chỉ trường name , bảng Index được tạo ra như sau

Field name       Data type      Size on disk
name             Char(100)       100 bytes
(record pointer) Special         4 bytes

• Tương tự, chúng ta có 10.000.000 bản ghi, mỗi bản ghi có độ lớn là 104 bytes. My ISAM sử dụng default block là 1.024 bytes, mỗi block sẽ chứa đc ~ 1.024/104 = 9 bản ghi => Số lượng block được tạo ra là 10.000.000/9 = 1.111.112 blocks.
• Bảng trên name được sắp xếp theo alphabe a-z. Database sẽ sử dụng Binary search để tiến hành tìm kiếm trên bảng này. => Trung bình số blocks cần truy cập để giải bài toán trên sẽ là: log2 1.111.112 = 20.08 ~ 21 blocks.Thì sẽ mất 21 * 0.01 ms = 0.21 ms để hoàn thành câu query.

Kết luận: Nguyên nhân giúp Index giảm thời gian và tài nguyên để thực hiện 1 query là

1. Bảng Index mới được tạo ra chỉ bao gồm những trường cần cho việc query => giảm dung lượng trên từng bản ghi (ví dụ trên là: 204 -> 104). Từ đó giảm số lượng block được tạo ra.
2. Việc dữ liệu được sắp xếp, Database có thể sử dụng thuật toán tìm kiếm nhị phân (Binary search) để tối ưu quá trình tìm kiếm. Số lượng blocks phải truy cập giảm đáng kể, thời gian thực hiện câu query cũng giảm đáng kể(2.000.000 blocks -> 21 blocks, 20s -> 0.21 ms).

3. Cơ chế hoạt động, lưu trữ của Index.

Dựa vào ví dụ của phần 2, chúng ta cũng hiểu được phần nào cơ chế hoạt động và lưu trữ của Index. Vậy mình xin tóm tắt lại như sau:

• Index sẽ được Database lưu tương tự như 1 bảng bao gồm: Các trường dữ liệu được index + 1 trường dữ liệu lưu trữ id của bản ghi được lưu trên bảng gốc.
• Bảng Index sử dụng thuật toán tìm kiếm nhị phân (Binary search) cho việc thực hiện query.
• Lưu trữ của bảng Index tương tự với bảng thường trên Database.

4. Ưu, nhược điểm của Database index.

Sau khi đọc các phần trên ai cũng hiểu được ưu điểm của việc Database Index. Vậy nhược điểm của Database Index là gì?

1. Vì Index sẽ tạo bảng riêng gồm các trường được Index => cũng sẽ mất một phần dung lượng lưu trữ trên ổ đĩa, ổ cứng.
2. Index phải được cập nhật thường xuyên để đảm bảo tính chính xác của từng query. Tức là mỗi lần bổ sung thêm 1 bản ghi bản gốc, chúng ta phải update lại Index.

Tất cả các nhược điểm này đều có hướng giải quyết và so với lợi ích Index mang lại thì không đáng là gì cả.

5. Áp dụng vào thực tế phát triển.

1. Hiện tại tất cả các Database gồm Relational Database (MS SQL, MySQL, PostgreSQL), NoSQL Database (MongoDB, ...) đều cung cấp việc tạo Index và update Index.
2. Dữ liệu càng nhiều, dung lượng mỗi bản ghi càng lớn thì Index càng phát huy sức mạnh.
3. Đối với số lượng bản ghi ít, dung lượng nhỏ thì không cần Index vì sẽ không cải thiện được nhiều, tốn dung lượng lưu trữ, mất thời gian update Index.

Thanks all. To be continue

P2: Mình sẽ trình bày các loại Index và các cách lưu trữ Index khác nhau phục vụ các bài toán khác nhau.