Table và Index trong Database

Mục tiêu chính của một Cơ sở dữ liệu (database) là lưu trữ data và cho phép truy cập data nhanh chóng. Nhưng làm sao database có thể sắp xếp data mà truy cập được hàng tỷ bản ghi dữ liệu trong nháy mắt?

Database đúng là có sử dụng file để lưu trữ data, nhưng thay vì sử dụng trực tiếp hệ thống file và folder của Hệ điều hành, chúng thêm thắt điều chỉnh cách truy cập làm sao để:

• Tối ưu dung lượng bộ nhớ

• Tối ưu truy cập dữ liệu

• Tối ưu cập nhật dữ liệu

Table

Hệ thống cơ sở dữ liệu lưu trữ các bản ghi dữ liệu, bao gồm nhiều field trong các Table, trong đó mỗi Table thường được biểu diễn trong một file riêng biệt. Ví dụ trong ngữ cạnh lập trình, Table Product ở đây là một class Product, các field của class Product chính là các Column, và mỗi một Row trong Table là một object thuộc kiểu Product.

Index

Mỗi một object Row này sẽ có Row_id độc nhất riêng biệt để phân biệt với nhau. Và thông thường khi chúng ta cần tìm kiếm một Row trong một danh sách hàng tỷ Row trong 1 Table, không ai đi duyệt 1 tỷ Row cả. Thay vào đó cần sử dụng một thuật toán tìm kiếm tối ưu hơn như kiểu B-Tree Search (B-Tree là cấu trúc dữ liệu cho phép tối ưu tốc độ tìm kiếm, tương tự Binary Search, độ phức tạp là O(log n)). Chà, với 1 tỷ bản ghi ta sẽ chỉ mất đâu đó 30 lần duyệt là đã có kết quả

Nhưng để thuật toán như Binary Search hoạt động, cần sắp xếp trước danh sách bản ghi theo thứ tự. Vậy là chúng ta sinh ra thêm 1 Table phụ mà các Row trong đó đã được sắp xếp sẵn, ví dụ theo row_id. Table phụ đó chính là Index

Data trong index chỉ chứa một con trỏ trỏ đến primary key hoặc row_id. Vậy nên khi tìm kiếm xong trên Index, database sẽ mất thêm một bước nữa là lấy row_id trong index và tìm kiếm trong Table để lấy thêm data của các field khác ra.

Chỗ này ta có thể tối ưu là bỏ đi bước sau (lấy thêm data ở Table gốc) bằng cách include thêm các field cần thiết trong index. Ví dụ:

CREATE INDEX IX_Product
ON Product Price
INCLUDE (ProductName, Description);

Trong nhiều trường hợp, Table chính chứa data được sắp xếp sẵn theo field row_id, và người ta gọi đó là Primary / Clustered Index. Các field còn lại được gọi là Secondary / Non-Clustered Index

Việc sử dụng Index có 1 sự đánh đổi là mỗi khi cập nhật dữ liệu trong table chính, database cũng cần cập nhật dữ liệu trong index. Vậy nên mặc định các database sẽ không tạo sẵn non-clustered index mà để cho developer tuỳ biến việc này

Tìm kiếm trên nhiều hơn 1 column

Index search hoạt động với 1 column, nhưng nếu với 2 column thì sao? Ví dụ ta có 1 query như sau

SELECT * 
FROM Product 
WHERE Type = 2 AND Price = 3000

Vậy nếu tạo 2 Index, 1 index cho cột Type và 1 index cho cột Price có tối ưu được không? Có lẽ là truy vấn vẫn tốt hơn việc không có index nào, nhưng database sẽ không tận dụng cả 2 index mà chỉ dùng 1 trong 2. Lí do vì 2 Index này không hề bổ trợ cho nhau.

Với 2 index riêng biệt, database chỉ có thể tìm kiếm trên 1 index như Price và cho ra 1 tập dữ liệu thu gọn bao gồm nhiều Product có Price = 3000 và sau đó bước 2 phải duyệt toàn bộ tập dữ liệu thu gọn này để tìm ra kết quả các Product có Type = 2. Index trên Type không có tác dụng

Nếu bạn đang nghĩ rằng 2 index sẽ mang đến binary search theo 2 cấp độ thì thật ra đó là sử dụng 1 Composite Index trên 2 field (Type, Price), tức là ví dụ data cần được sắp xếp theo Type trước rồi nếu Type bằng nhau thì mới sắp xếp Price.

CREATE INDEX idx_product_type_price ON Product (Type, Price);
-- Hoặc ngược lại:
-- CREATE INDEX idx_product_price_type ON Product (Price, Type);