Tìm hiểu về index trong database

Trong các hệ quản trị cơ sở dữ liệu quan hệ RDBMS, thì indexing đóng một vai trò quan trọng trong thiết kế, vận hành nhằm giúp hệ thống đạt được hiệu năng tối ưu, giảm thời gian, tài nguyên cho các truy vấn CSDL. Index cho phép RDBMS server tìm và truy vấn các rows dữ liệu nhanh hơn so với không index nhưng cũng kèm theo chi phí cho việc tạo, cập nhật index

1. Một số khái niệm như

• Search-key: thuộc tính được dùng để tìm kiếm bản ghi
• Index-file: bao gồm các bản ghi dạng Search-key – Pointer.

2. Có hai loại index cơ bản gồm:

• Ordered indices: các search-key được lưu trữ có thứ tự
• Hash indices: các search-key phân tán đồng đều trong các bucket bằng một hàm băm (hash)

3. Chỉ tiêu đánh giá index

Để đánh giá index có hiệu quả như thế nào thì có dùng một số độ đo như:

• Kiểu truy xuất hỗ trợ hiệu quả. (tìm kiếm chính xác hay trong khoảng giá trị)
• Thời gian truy cập
• Chi phí thời gian chèn bản ghi mới
• Chi phí xoá bản ghi
• Chi phí không gian lưu trữ

4. Ordered indices

Trong một ordered index, các index được lưu trữ theo thứ tự của search-key. Trong đó lại chia làm 2 loại Primary-index và Secondary index. Primary index là loại mà thứ tự search-key cũng chính là thứ tự trong file dữ liệu, cũng còn được gọi là một clusterd-index. Chú ý là search-key của primary index thường nhưng không bắt buộc phải là khoá chính. Secondary index là loại mà thứ tự của search-key khác thứ tự trong file dữ liệu hay còn gọi là non-clustering index.

Người ta thường chia theo cách lưu primary index theo hai loại: dense index và sparse index.

Dense index là mọi index-record có cho mọi search-key trong file dữ liệu. Ví dụ trong hình dưới có index cho column ID của table Instructor.

Hoặc index cho column dept_name của table instructor

Sparse index là nếu chỉ có index-record cho một số search-key trong file dữ liệu. Để tìm được một bản ghi tương ứng với search-key giá trị K thì chỉ cần tìm một search-key lớn nhất nhỏ hơn K trong file index và tìm tuần tự trong file dữ liệu từ vị trí con trỏ Pointer trong file index chỉ tới.

So sánh hai cách lưu index này thì sparse index tốn ít không gian lưu trữ hơn nhưng lại chậm hơn khi truy xuất dữ liệu. Một tradeoff được đưa ra đó là mỗi index trỏ tới một block trong file dữ liệu mà search-key value của nó là nhỏ nhất trong block đó.

Secondary indices có cấu trúc phức tạp hơn so với primary index. Mỗi index record trỏ tới một bucket chứa các con trỏ tới tất cả các bản ghi có giá trị search-key. Secondary index phải luôn là dense vì nếu không sẽ không truy xuất được vị trí bản ghi dễ dàng.

Một vấn đề cần đặt ra đó là khi mà một primary index quá lớn không chứa được trong RAM thì cần phải lưu ra ổ cứng, dẫn tới chi phí truy cập cao. Cách giải quyết vấn đề này đó là lưu primary index trên ổ cứng và xây một sparse index trên nó. Trong đó outer-index là sparse index của primary index và inter-index là primary index. Nếu outer index lại không đủ nhỏ thì tiếp tục xây một sparse index level cao hơn. Đây chính là khái niệm Multi-index.

Về phần cập nhật index như thế nào đối với trường hợp này đơn giản, các bạn có thể tự suy luận các thao tác thêm/xoá index. Chỉ cần lưu ý một điều đó là indices ở mọi level đều phải được cập nhật sau các thao tác xoá/thêm dữ liệu.

Nhận xét: cả secondary và primary index đều cải thiện hiệu năng truy xuất dữ liệu nhưng chi phí cho việc cập nhật index sau mỗi thao tác với dữ liệu là lớn. Chi phí scan tuần tự của primary index là bé nhưng với secondary index lại lớn vì khi truy cập một bản ghi trong file dữ liệu có thể phải load cả một block (5-10ms) so với 100nms nếu truy cập trực tiếp bản ghi.

5. B+ tree index file

Theo nhận xét trên, có một cách đơn giản hoá việc lưu trữ và cập nhật file index đó là dựa trên cấu trúc dữ liệu 

. Với index file lưu dạng B+ tree thì các thao tác cập nhật index thực hiện cục bộ, chi phí nhỏ, không cần tái tổ chức lại toàn bộ file để đảm bảo hiệu năng. Tuy nhiên có khuyết điểm nhỏ đó là chi phí thêm/xoá index và không gian lưu trữ lớn hơn.

Điểm đặc biệt của B+ tree index so với B-tree index đó là chỉ có các node lá mới chứa con trỏ tới bản ghi dữ liệu.

Các bạn nhìn hình trên có thể thấy ngay cách tổ chức của B+ tree nên xin phép không trình bày ở đây. Các thao tác thêm/xoá index đều là thao tác của B+ tree nên các bạn có thể tham khảo trong Wiki. Ngoài ra có một số issue như: search-key là string hoặc cách build một B+ tree hiệu quả. Với trường hợp search-key là string thì có thể dùng prefix-compression. Với build B+tree có thể dùng cách bottom-up.

6. Multiple key access

Trong trường hợp câu truy vấn có nhiều columns thì có nên đánh index trên nhiều columns đó không. Ví dụ

select ID

from instructor

   where dept_name = “Finance” and  salary = 80000

có một số phương án như:

• Sử dụng index đối với dept_name để tìm các instructor có dept name là France và kiểm tra salary=8000
• Sử dụng index đối với salary để tìm các instructor có salary = 80000, và kiểm tra dept name
• Sử dụng index đối với dept_name để tìm các instructor có dept name là France. Tương tự dùng index với salary và tìm giao của hai tập thu được đó.

Từ nhu cầu đó, người ta đưa ra khái niệm index trên nhiều search-key và định nghĩa một thứ tự từ điển (a1, b1) < (a2, b2) nếu a1 < a2 hoặc a1=a2 và b1 < b2.

    Nếu trong thường hợp trên định nghĩa một index trên hai cột dept_name và salary thì với mệnh đề where dept_name =“Finance” and salary = 80000 hoặc where dept_name= “Finance” and salary < 80000 đều hiệu quả. Nhưng mệnh đề where dept_name < “Finance” and balance = 80000 lại không hiệu quả vì sẽ phải lấy nhiều bản ghi thoả mãn điều kiện 1 mà không thoả mãn điều kiện 2.

7. Hashing index

   Hash index thì không có gì lạ nếu bạn đã nắm được khái niệm hash trong cấu trúc dữ liệu. Có hai loại hash đó là static hash và dynamic hash.

    Static hash thì tổ chức có cố định một số bucket và hàm hash sẽ chuyển search-key thành mã để truy cập trực tiếp vào bucket (bucket là một đơn vị lưu trữ chứa một hoặc nhiều record). Ví dụ nếu sử dụng hash file organization đối với dept_name của bảng instructor mà giá trị hash.

h(Music) = 1       h(History) = 2

h(Physics) = 3  h(Elec. Eng.) = 3

thì ta có 

    Một vấn đề đó là cần phải chọn hàm hash đủ tốt để tránh collision. Nếu bucket bị overflow do không đủ bucket hoặc do phân phối các bản ghi bị skew dẫn tới nhiều records có cùng giá trị hash hoặc hàm hash không đưa ra được một phân phối uniform trên tập giá trị search-key. Khi đó có thể sửa dụng danh sách liên kết để lưu bucket.

Đối với việc sử dụng hash index ta có thể dùng bucket chứa các con trỏ tới các bản ghi dữ liệu

Như các bạn đã thấy vấn đề đối với static hashing đó là việc cố định số lượng bucket làm giảm hiệu năng hệ thống. Nếu ít bucket quá thì dễ bị bucket overflow, nếu quá nhiều bucket thì làm tốn không gian lưu trữ. Nếu database chia tách ra thì không gian lưu trữ lại bị bỏ phí.Một giải pháp cho vấn đề đó là tái tổ chức lại file index với hàm hash mới, nhưng chi phí lớn và ảnh hưởng tới các tính năng đã có. Một cách tốt hơn đó là dùng dynamic hashing. Chi tiết về dynamic hashing khá rộng nên mình không đề cập ở đây.

Nhận xét: các bạn đã thấy ưu nhược điểm của ordered index và hashing index. Tuỳ từng trường hợp cụ thể mà có thể sử dụng cho phù hợp. Ngoài ra cần chú ý một điểm nữa là ngoài B-tree, B+ tree, hashing còn nhiều loại cấu trúc index khác cho các loại dữ liệu khác nhau. Các bạn quan tâm có thể đọc trong tài liệu của Postgresql.