Có bao giờ bạn tự hỏi câu truy vấn sử dụng index như thế nào? Index là gì? Có cấu tạo thế nào mà câu truy vấn lại nhanh hơn nhiều như thế? Bài viết hôm nay sẽ giúp các bạn hiểu rõ hơn về index để có thể tự trả lời những câu hỏi tương tự như vậy.
Tìm dữ liệu trong một tập nhiều dòng
Tập dữ liệu không có thứ tự
Dữ liệu trong cơ sở dữ liệu quan hệ được lưu trữ dưới dạng bảng, hay có thể nói cách khác là hàng và cột. Nhìn vào bảng dữ liệu trong hình dưới đây và bạn hãy trả lời truy vấn “tìm nhân viên có ID bằng 5”. Bạn sẽ làm thế nào?

Để đảm không bỏ sót có phải bạn sẽ duyệt từng dòng một từ trên xuống dưới, rà soát xem cột ID của dòng nào có giá trị bằng 5 hay không?
Nếu dòng này nằm ngay trên đầu hoặc ở dòng thứ 2 hoặc thứ 3 thì bạn sẽ nhanh chóng tìm thấy nó. Nhưng nếu nó nằm ở dưới cùng thì sao? Bạn phải duyệt qua hết bảng mới có kết quả cuối cùng.
Giả sử ngay dòng đầu tiên cột ID đã bằng 5 rồi, liệu bạn có tiếp tục tìm xuống dưới không? Bởi vì câu truy vấn của chúng ta không giới hạn chỉ tìm một người (TOP 1) mà cũng không có ràng buộc nào nói mỗi ID là duy nhất. Do đó, bạn bắt buộc phải duyệt đến cuối bảng vì có thể có một nhân viên khác có ID cũng bằng 5 thì sao.
Tập dữ liệu có thứ tự
Nếu bảng này được sắp xếp theo thứ tự tăng dần của cột ID thì thế nào?

Chúng ta có thể lựa chọn duyệt bảng theo hướng từ trên xuống hoặc từ dưới lên. Ta có thể dự đoán giá trị cần tìm là 5 thì duyệt từ trên xuống gần hơn, nhưng nếu giá trị cần tìm là 15 thì duyệt từ dưới lên có lẽ nhanh hơn?
Đó là do ví dụ của chúng ta chỉ có vài dòng, nếu bảng NhanVien này có hàng trăm ngàn hoặc hàng triệu dòng thì thế nào? Chưa kể giá trị ID không chắc là liên tục. Chúng ta sẽ không đoán được giá trị cần tìm ở đoạn nào nên chỉ có thể chọn một trong hai hướng và duyệt đến đầu bên kia.
Trong tình huống bảng đã sắp xếp theo thứ tự như này. Khi đã tìm thấy dòng có ID bằng 5 rồi, nếu có thêm nhân viên khác cùng ID thì hẳn phải ở ngay dòng kế tiếp.
Bạn chỉ cần nhìn thêm dòng kế tiếp có phải bằng 5 hay không. Nếu không phải thì kết thúc truy vấn, còn nếu là 5 thì kiểm tra thêm dòng kế tiếp cho đến khi không tìm thêm được giá trị tương tự nữa.
Dữ liệu dù được sắp xếp theo thứ tự vẫn chưa giúp câu truy vấn chạy nhanh được. Nếu không may giá trị cần tìm nằm kề cuối thì ta vẫn phải duyệt hầu như là hết bảng. Đây vẫn chưa là index
Clustered index
Tìm kiếm với clustered index
Bây giờ, nếu ta tạo clustered index trên cột ID cho bảng này thì dữ liệu được tổ chức như thế nào? Chúng ta chạy câu lệnh đơn giản sau để tạo index
CREATE UNIQUE CLUSTERED INDEX CIX_NhanVien ON NhanVien(ID ASC)
Những dòng dữ liệu trong bảng được gom nhóm lại với nhau tạo thành page, một page có kích thước 8KB và tùy thuộc vào kích thước của mỗi dòng mà chứa được số lượng tương ứng. Giả dụ bảng NhanVien trên có kích thước 2000 bytes cho mỗi dòng, nên mỗi page sẽ chứa được 4 dòng như hình bên dưới

Cột ID làm clustered index key nên dữ liệu của bảng sẽ được sắp xếp theo giá trị tăng dần trên cột này.
Chúng ta thấy các dòng dữ liệu với ID từ 1 đến 4 nằm trong page thứ nhất. Từ 5 đến 8 nằm trong page thứ hai. Từ 9 đến 12 thuộc page thứ 3 và ID từ 13 đến 16 thuộc page thứ 4.
Các page này thể hiện đầy đủ dữ liệu của bảng và liên kết hai chiều với nhau theo từng cặp nằm cạnh nhau hoặc có thể bất kì khoảng cách nào. Chỉ cần có liên kết là thể hiện được thứ tự của dữ liệu.
Phía bên trái có một page khác chứa các giá trị 13, 9, 5 và NULL. Đây có thể xem là page mô tả rút gọn dữ liệu của cột ID.
Mỗi một dòng trong page này đại diện một tập dữ liệu ở page mà nó link tới. Và page được link tới này có thể lại chứa các dòng link tới những page khác (nhiều cấp). Tất nhiên dữ liệu trong page bên trái là clustered key, trong hình 3 chính là các giá trị từ cột ID.
Cấu trúc dữ liệu này gọi là B-Tree, nó sẽ giúp SQL Server xác định vị trí dòng dữ liệu cực nhanh vì không gian tìm kiếm sẽ giảm đi đáng kể thông qua cấu trúc này. Hãy thử tìm lại nhân viên có ID bằng 5 xem.
Thay vì duyệt từ đầu bảng như lúc nãy, giờ ta chỉ cần duyệt các dòng trong page bên trái. Xuất phát từ bất kì hướng nào cho đến khi gặp giá trị 5. Lần theo đường dẫn liên kết tới page ở bên phải rồi duyệt page này sẽ tìm thấy giá trị 5.
Vì chúng ta khai báo clustered index key là unique nên việc tìm kiếm sẽ kết thúc ngay khi tìm thấy dòng dữ liệu có giá trị ID bằng 5. Nếu không unique SQL Server sẽ tìm thêm ở page bên cạnh.
Có thể bạn sẽ nói làm như vậy cũng thực hiện nhiều phép so sánh, gần bằng duyệt từng dòng trực tiếp trên bảng. Nhưng đây là bảng có kích thước nhỏ, bạn hãy hình dung nếu bảng có một triệu pages thì thế nào? Thời gian tìm kiếm một dòng dữ liệu khi đó không còn phụ thuộc vào số lượng dòng mà là chiều cao của cây index.
Đây chính là cách hoạt động của index, nó sẽ giúp chúng ta định hướng tìm kiếm trong một tập dữ liệu nhỏ hơn và do đó sẽ có tốc độ nhanh hơn.
Cấu tạo của clustered index
Những page chứa dữ liệu của bảng như thế này gọi là leaf node, xét theo cấp độ gọi là leaf level hay còn gọi level 0. Cao hơn sẽ có level 1 và cứ tăng lên 1 như vậy cho đến khi chứa đủ dữ liệu thì dừng.
Cấp cao nhất sẽ là root level. Những level ở giữa root và leaf thì gọi là intermediate level. Trong hình 3 không có intermediate level, bạn có thể xem minh họa ở trang này.
Nếu leaf level (của clustered index) chứa dữ liệu của bảng thì các level trên chứa cái gì? Những dữ liệu này từ đâu mà có?
Mỗi page ở level trên cũng có kích thước 8KB. Dữ liệu được chứa trong này là clustered key của bảng, được gọi là index record. Kích thước của index record sẽ quyết định số lượng record có trong page.
Giả sử cột ID có kiểu dữ liệu INT (4 bytes) cộng với các chi phí tổ chức lưu trữ nữa thành 11 bytes cho mỗi record. Với không gian 8096 bytes mỗi page có thể chứa tối đa 736 index records (tính toán tương đối). Tương ứng với 736 pages ở level dưới.
Bây giờ ta thấy rõ rằng duyệt 736 pages để tìm một giá trị sẽ tốn thời gian hơn nhiều so với duyệt 2 pages. Một page ở level 1 (root page) và 1 page ở level 0 (leaf page). Đây chính là cách mà index giúp ta tăng tốc độ tìm kiếm.
Chúng ta hãy cùng khảo sát clustered index trên bảng NhanVien để kiểm chứng những điều trên. Sử dụng hai câu lệnh DBCC IND() và DBCC PAGE() như hướng dẫn ở bài trước mình từng đề cập. (Mình sẽ cập nhật scripts tạo bảng NhanVien và insert dữ liệu sau)

Các tham số từ trái qua phải gồm tên database, tên bảng và index_id. Chúng ta hãy chú ý đến bảng kết quả. PagePID là ID của các page thuộc bảng NhanVien trên FileID 1 (vì nhiều bảng có thể được lưu trên cùng file và một bảng cũng có thể được lưu trên nhiều file).
PageType 10 thuộc system dùng để quản lý space của bảng ta tạm thời chưa quan tâm. PageType 1 chính là data page chứa dữ liệu bảng NhanVien. PageType 2 là index page chứa index record, và cũng là root page trong ví dụ của chúng ta.
Cột IndexLevel thể hiện đúng như những gì chúng ta nói ở trên. Level 0 thấp nhất cũng là leaf level, nơi chứa dữ liệu của bảng (data page). Level 1 cao nhất nên là root level. Hãy chú ý PagePID của root page vì chúng ta sẽ khảo sát nội dung của nó.
Bốn page có level bằng 0 được link với hai page bên cạnh thể hiện qua cột PrevPagePID và NextPagePID. Cùng với thông tin FileID thông qua cột NextPageFID và PrevPageFID.
Tiếp theo, hãy cùng xem nội dung page root level có giống những gì chúng ta đã mô tả không nhé.

Page root có ID 401 và nội dung của nó có 4 dòng chứa key ID lần lượt NULL, 5, 9, 13. Mỗi dòng này link tới page ở level 0 có pageID ở chột ChildPageId. Giống như những gì chúng ta thấy trong hình 3.
Vậy khi tìm kiếm một giá trị, SQL Server sẽ bắt đầu từ root page, lần theo giá trị trong page đó đi xuống các level thấp hơn và cuối cùng sẽ đến được page chứa giá trị cần tìm. Thời gian của việc tìm kiếm này phụ thuộc vào chiều cao của index (số lượng level). Và số lượng level phụ thuộc vào kích thước index key.
Tóm lại clustered index trong SQL Server có các đặc điểm sau
- Dữ liệu của bảng sẽ được sắp xếp theo thứ tự clustered key
- Sử dụng cấu trúc B-Tree để tạo ra các cấp độ lưu trữ key hỗ trợ tìm kiếm
- Index có level càng cao thì việc tìm kiếm càng tốn thời gian hơn
- Level của index phụ thuộc vào độ lớn dữ liệu trong bảng và kích thước của index key
Pingback: Tìm hiểu index trong SQL Server (phần 2) - QUẢN TRỊ CƠ SỞ DỮ LIỆU
Pingback: 11 bài viết về Index Trong Sql Là Gì - Học Điện Tử Cơ Bản