Tổng quan về lưu trữ và chỉ số

Các chỉ mục phân cụm

Khi một file nào đó được tổ chức để thứ tự của các bản ghi dữ liệu là giống nhau hoặc gần với thứ tự của các cổng vào dữ liệu trong một vài chỉ mục, thì chúng ta nói rằng chỉ mục này được phân cụm (clustered); ngược lại, nó là chỉ mục không phân cụm (unclustered index). Theo định nghĩa, chỉ mục sử dụng Alternative (1) là chỉ mục được phân cụm. Chỉ mục sử dụng Alternative (2) hoặc (3) có thể là một chỉ mục phân cụm chỉ nếu các bản ghi dữ liệu này được sắp xếp theo trường khoá tìm kiếm. Ngược lại, nếu thứ tự các bản ghi dữ liệu là ngẫu nhiên, hoàn toàn xác định bởi thứ tự vật lý của chúng, thì không có cách nào để sắp xếp những cổng vào dữ liệu này trong một chỉ mục theo cùng một thứ tự.

Thực tế, các file hiếm khi được lưu trữ theo thứ tự vì chi phí để duy trì việc này rất đắt nếu dữ liệu này cần được cập nhật. Vì thế trên thực tế, chỉ mục phân cụm là một chỉ mục sử dụng Alternative (1), và các chỉ mục sử dụng Alternatives (2) hoặc (3) là chỉ mục không phân cụm.

Đôi khi chúng ta coi chỉ mục đang sử dụng Alternative (1) là clustered file, vì các cổng vào dữ liệu là các bản ghi dữ liệu thực sự, và vì thế chỉ mục này là một file chứa các bản ghi dữ liệu. (Như đã quan sát ở trên, việc tìm và quét trên một chỉ mục sẽ trả về chỉ những cổng vào dữ liệu của nó, dù cho là chỉ mục này chứa những thông tin khác dùng để tổ chức các cổng vào dữ liệu.)

Chi phí của việc sử dụng một chỉ mục để đáp lại một truy vấn tìm kiếm miền có thể rất rất lớn tuỳ vào chỉ mục này có được phân cụm không. Nếu chỉ mục này được phân cụm, tức là, chúng ta đang sử dụng khoá tìm kiếm của một clustered file, rids trong các cổng vào dữ liệu trỏ tới một tập hợp các bản ghi kề nhau, và chúng ta chỉ cần truy cập một vài trang dữ liệu. Nếu chỉ mục này là không phân cụm, mỗi cổng vào dữ liệu có thể chứa một rid trỏ tới một trang dữ liệu riêng biệt, dẫn tới số lượng các trang dữ liệu I/Os nhiều bằng số lượng các cổng vào dữ liệu ứng với phép chọn miền, như minh hoạ trong Hình 1. Điểm này được bàn thêm trong Chương 13.

Các chỉ mục chính và chỉ mục phụ

Một chỉ mục trên một tập các trường trong đó có khoá chính (xem Chương 3) được gọi là chỉ mục chính; những chỉ mục khác được gọi là các chỉ mục phụ. (Cụm từ chỉ mục chính và chỉ mục phụ đôi khi được sử dụng với nghĩa khác. Chỉ mục sử dụng Alternative (1) được gọi là chỉ mục chính, và chỉ mục sử dụng Alternatives (2) hoặc (3) được gọi là chỉ mục phụ.)

Hai cổng vào dữ liệu được gọi là trùng nhau nếu chúng có cùng giá trị của trường khoá tìm kiếm liên quan đến chỉ mục này. Chỉ mục chính được đảm bảo là không chứa sự trùng nhau, nhưng chỉ mục trên các trường khác có thể chứa sự trùng nhau. Nói chung, các chỉ mục phụ sẽ chứa sự trùng nhau. Nếu chúng ta biết rằng không tồn tại sự trùng nhau, tức là chúng ta biết rằng khoá tìm kiếm chứa một một vài khoá dự tuyển, chúng ta gọi chỉ mục này là chỉ mục duy nhất.

Một vấn đề quan trọng là các cổng vào dữ liệu trong một chỉ mục được tổ chức như thế nào để hỗ trợ truy cập dữ liệu hiệu quả. Chúng ta sẽ bàn đến trong phần sau.

Chỉ mục dựa trên băm

Chúng ta có thể tổ chức các bản ghi sử dụng một công nghệ gọi là băm để nhanh chóng tìm được các bản ghi có giá trị khoá tìm kiếm bằng giá trị đưa vào. Ví dụ, nếu file của các bản ghi nhân viên được băm dựa trên trường name, chúng ta có thể truy cập tất cả các bản ghi về Joe.

Trong cách tiếp cận này, các bản ghi trong file được nhóm lại trong một buckets, trong đó một bucket chứa một trang chính và có thể là các trang khác được liên kết trong một chuỗi.

Một bản ghi nào đó thuộc về bucket nào đó có thể được xác định bằng cách thực hiện một hàm đặc biệt trên khoá tìm kiếm, hàm này gọi là hàm băm. Cho một bucket, cấu trúc chỉ mục dựa trên băm cho phép chúng ta truy cập trang chính của bucket này trong một hoặc hai đĩa I/Os.

Đối với việc thêm bản ghi, bản ghi được thêm vào một bucket phù hợp cùng với các trang ‘tràn’ nếu cần thiết. Để tìm kiếm một bản ghi nếu biết giá trị khoá tìm kiếm, chúng ta áp dụng hàm băm này để xác định bucket nào chứa bản ghi và tìm trong tất cả các trang của bucket này. Nếu chúng ta không có giá trị khoá tìm kiếm, ví dụ, chỉ mục này được xây dựng dựa trên sal và chúng ta muốn tìm các bản ghi có giá trị tuổi bằng một tuổi nào đó nhập vào, chúng ta phải quét tất cả các trang trong file này.

Trong chương này, chúng ta giả sử rằng việc áp dụng một hàm băm tới (khoá tìm kiếm của) một bản ghi nào đó cho phép chúng ta xác định và truy cập được trang chứa bản ghi này chỉ bằng một thao tác I/O. Trên thực tế, các cấu trúc chỉ mục dựa trên băm thường thực hiện việc thêm, xoá và cho phép chúng ta truy cập đến trang chứa bản ghi này bằng một hoặc hai thao tác I/Os (xem Chương 11).

Chỉ mục băm được minh hoạ trong Hình 2, nơi mà dữ liệu được lưu trong một file được băm trên trường age; các cổng vào dữ liệu trong file chỉ mục đầu tiên này là các bản ghi dữ liệu thực. Việc áp dụng hàm băm trên trường age xác định được trang chứa bản ghi này. Hàm băm h trong ví dụ này thực sự rất đơn giản; nó chuyển giá trị khoá tìm kiếm thành biểu diễn nhị phân và sử dụng hai bit ít quan trọng nhất để định danh bucket.

Hình 2 cũng chỉ ra chỉ mục với khoá tìm kiếm sal chứa cặp (sal, rid) là các cổng vào dữ liệu. Rid (viết tắt của record id) cấu thành nên cổng vào dữ liệu trong chỉ mục thứ hai này là một con trỏ trỏ tới một bản ghi có giá trị khoá tìm kiếm sal (và được chỉ ra trong hình này là một mũi tên trỏ tới bản ghi dữ liệu này).

Việc sử dụng ký hiệu này được giới thiệu trong Phần 2, Hình 2 minh hoạ Alternatives (1) và (2) cho các cổng vào dữ liệu. File của các bản ghi nhân viên được băm trên trường age, và Alternative (1) được sử dụng cho các cổng vào dữ liệu. Chỉ mục thứ hai trên trường sal cũng sử dụng việc băm để xác định các cổng vào dữ liệu – bây giờ là cặp (sal, rid của bản ghi nhân viên), tức là Alternative (2) được sử dụng cho các cổng vào dữ liệu.

Index-Organized File Hashed trên age, với Chỉ mục Hỗ trợ trên sal

Ghi nhớ rằng khoá tìm kiếm cho một chỉ mục nào đó có thể là một hoặc nhiều trường, và nó không cần định danh duy nhất một bản ghi. Ví dụ, trong chỉ mục salary, hai cổng vào dữ liệu có cùng khoá tìm kiếm giá trị là 6003. (Có sự lạm dụng trong sử dụng khái niệm khoá. Khoá chính hoặc khoá dự tuyển - những trường định danh duy nhất một bản ghi; xem Chương 3- không liên quan đến khái niệm của khoá tìm kiếm.

Chỉ mục dựa trên cây

Ngoài cách sử dụng chỉ mục dựa trên băm, chúng ta còn có thể sử dụng cấu trúc dữ liệu dạng cây để tổ chức các bản gho. Các cổng vào dữ liệu được sắp xếp theo thứ tự của giá trị khoá tìm kiếm, và một cấu trúc dữ liệu tìm kiếm phân cấp được duy trì để định hướng việc tìm kiếm.

Hình 3 chỉ ra các bản ghi nhân viên như Hình 2, nhưng lần này nó được tổ chức trong một chỉ mục cấu trúc cây với khoá tìm kiếm là age. Với mỗi nút trong hình này (ví dụ, các nút có nhãn A, B, Ll, L2) là một trang vật lý, và việc truy cập một nút cần một I/O đĩa.

Mức thấp nhất của cây này gọi là mức lá, chứa các cổng vào dữ liệu; trong ví dụ của chúng ta đó là những bản ghi nhân viên. Để minh hoạ những ý tưởng này tốt hơn, chúng ta vẽ Hình 3 như là ở đó có việc thêm vào các bản ghi nhân viên, một số có tuổi nhỏ hơn 22 và một số có tuổi lớn hơn 50 (giá trị tuổi thấp nhất và cao nhất xuất hiện trong Hình 2.) Những bản ghi nhân viên có tuổi nhỏ hơn 22 sẽ được xuất hiện trong các trang lá (L1), và các bản ghi có tuổi lớn hơn 50 sẽ xuất hiện trong các trang lá (L3).

Chỉ mục có cấu trúc dạng cây

Cấu trúc này cho phép chúng ta định vị các cổng vào dữ liệu với các giá trị khoá tìm kiếm trong một vùng mong muốn một cách hiệu quả. Tất cả các tìm kiếm bắt đầu ở nút cao nhất, gọi là nút gốc, và nội dung của các trang ở mức không-lá định hướng việc tìm kiếm tới trang lá đúng. Các trang không-lá chứa các nút phân tách nhau bởi giá trị khoá tìm kiếm. Con trỏ bên trái của giá trị khoá k trỏ tới cây con chứa chỉ những cổng vào dữ liệu nhỏ hơn k. Con trỏ bên phải của giá trị khoá k trỏ tới cây con chứa chỉ những cổng vào dữ liệu lớn hơn hoặc bằng k. Trong ví dụ của chúng ta, giả sử rằng chúng ta muốn tìm tất cả cổng vào dữ liệu với 24 < age < 50. Mỗi đường đi từ nút gốc tới một nút con trong Hình 2 có một nhãn giải thích nội dung chứa trong cây con đó. (Mặc dù các nhãn của các đường đi còn lại không được chỉ ra, nhưng chúng ta cũng có thể dễ dàng suy luận ra.) Trong ví dụ tìm kiếm của chúng ta, chúng ta tìm các cổng vào dữ liệu có giá trị khoá tìm kiếm > 24, và nó được định hướng là ở nút con giữa, nút A. Kiểm tra nội dung của nút này, chúng ta lại được định hướng để tìm tiếp trong nút B. Kiểm tra nội dung của nút B, chúng ta lại được định hướng để tìm tiếp trong nút lá L1, nút này chứa các cổng vào dữ liệu chúng ta đang tìm.

Quan sát thấy rằng các nút là L2 và L3 cũng chứa những cổng vào dữ liệu thoả mãn điều kiện của chúng ta. Để thuận lợi cho việc truy cập các cổng vào dữ liệu dữ liệu như vậy trong khi tìm kiếm, tất cả các trang lá được duy trì trong một danh sách liên kết đôi. Vì thế, chúng ta có thể đến trang L2 sử dụng con trỏ next trên trang L1, và sau đó đến trang L3 sử dụng con trỏ next trên L2.

Vì thế, số lượng thao tác I/Os trong quá trình tìm kiếm bằng với chiều dài đường đi từ gốc đến lá cộng với số các trang lá chứa các cổng vào dữ liệu thoả mãn. B+tree là một cấu trúc chỉ mục đảm bảo rằng tất cả các đường đi từ gốc đến lá trong một cây nào đó sẽ có chiều dài tương đương, tức là, cấu trúc này luôn cân bằng về chiều cao. Việc tìm kiếm một trang lá thoả mãn nhanh hơn tìm kiếm nhị phân tất cả các trang trong một file được sắp vì mỗi nút không phải là lá có thể phù hợp với một số lượng lớn các con trỏ, và chiều cao của cây trong thực tế ít khi nhiều hơn ba hoặc bốn. Chiều cao của cây cân bằng là chiều dài của đường đi từ gốc đến lá; trong Hình 3, chiều cao của cây là ba. Số lượng các I/Os để truy cập một trang lá mong muốn nào đó là bốn, bao gồm gốc và các trang lá. (Trong thực tế, gốc thường nằm trong buffer pool vì nó thường xuyên được truy cập, và chúng ta cần ba thao tác I/Os cho một cây có chiều cao bằng ba.)

Số lượng trung bình các con của một nút không phải là lá được gọi là fan-out của cây. Nếu tất cả các nút không phải là lá có n con, một cây chiều cao h sẽ có n^h trang lá. Trong thực tế, các nút không có cùng số lượng các con, nhưng khi sử dụng F là giá trị trung bình của n, chúng ta vẫn có được số lượng các trang lá xấp xỉ là F^h. Trong thực tế, F ít nhất là 100, có nghĩa là cây có chiều cao bằng bốn sẽ chứa 100 triệu trang lá. Vì thế, chúng ta có thể phải tìm kiếm trong một file có 100 triệu trang lá và tìm ra trang chúng ta muốn mà chỉ cần sử dụng bốn thao tác I/Os; trong khi đó, tìm kiếm nhị phân của file tương đương sẽ mất log₂100.000.000 (over 25) I/Os.

Mô hình định giá

Trong so sánh về các tổ chức file của chúng ta, và trong cuối chương này, chúng ta sử dụng một mô hình định giá đơn giản để cho phép ước lượng chi phí (theo thời gian thực thi) của các thao tác cơ sở dữ liệu khác nhau. Chúng ta sử dụng B để ký hiệu cho số lượng các trang dữ liệu khi các bản ghi được dồn đầy vào trong trang mà không còn không gian lãng phí nào, và R để ký hiệu cho số lượng các bản ghi trong mỗi trang. Thời gian trung bình để đọc hoặc ghi một trang đĩa là D, và thời gian trung bình để xử lý một bản ghi (ví dụ, so sánh một giá trị của trường với một hằng số nào đó) là C. Trong tổ chức file băm, chúng ta sử dụng một hàm gọi là hàm băm để ánh xạ một bản ghi vào một dải của các số; thời gian yêu cầu để áp hàm băm này cho một bản ghi nào đó là H. Với các chỉ mục cây, chúng ta sẽ sử dùng F để ký hiệu cho fan-out, như đề cập trong Phần 3.3, fan-out có giá trị ít nhất là 100.

Ngày nay giá trị của D bằng khoảng 15milli giây, C và H = 100nano giây; vì thế chúng ta hy vọng là chi phí cho I/O là chủ yếu. I/O thường chiếm phần lớn hơn rất nhiều so với giá của các thao tác khác, và vì thế việc tính được chi phí I/O sẽ cung cấp cho chúng ta chi phí xấp xỉ khá đúng. Thêm nữa, tốc độ CPU hiện nay tăng lên đáng kể, ngược lại tốc độ xử lý trên đĩa không tăng lên tương ứng. (Mặt khác, khi kích thước bộ nhớ chính tăng lên, số lượng các trang được đưa vào bộ nhớ chính cùng tăng lên, dẫn đến số lượng các yêu cầu I/O ít đi!) Chúng ta tập trung vào các thành phần I/O trong mô hình định giá, và chúng ta giả sử hằng số C là chi phí xử lý mỗi bản ghi trong bộ nhớ trong. Bạn hãy luôn lưu ý đến những quan sát sau:

Những hệ thống thực phải đề cập đến những ảnh hưởng khác đến chi phí, như giá CPU (và chi phí truyền dữ liệu qua mạng trong các cơ sở dữ liệu phân tán).

Mặc dù chúng ta chỉ tập trung vào chi phí I/O, mô hình chính xác xem xét tất cả khía cạnh cũng sẽ rất phức tạp. Vì thế, chúng ta sử dụng một mô hình đơn giản trong đó chúng ta chỉ đếm số lượng các trang đọc hoặc ghi vào đĩa và dùng nó làm thước đo I/O. Chúng ta bỏ qua vấn đề quan trọng là truy cập theo khối trong phân tích của chúng ta- thông thường, các hệ thống đĩa cho phép chúng ta đọc một khối các trang bằng chỉ một yêu cầu I/O. Chi phí sẽ bằng thời gian cần để tìn trang đầu tiên trong khối và chuyển tất cả các trang trong khối này vào bộ nhớ. Việc truy cập theo khối như thế này có thể rẻ hơn nhiều so với phát ra một yêu cầu I/O ứng với mỗi trang trong khối, đặc biệt nếu những yêu cầu này không được thực hiện liên tiếp, vì chúng ta sẽ phải cộng thêm chi phí tìm kiếm từng trang trong khối.

Chúng ta bàn đến những thành phần liên quan đến mô hình định giá bất cứ khi nào những giả định đơn giản này ảnh hưởng đến những kết luận quan trọng của chúng ta.

Heap file

Quét: Chi phí là B(D+RC) vì chúng ta phải truy cập B trang, mỗi trang mất một thời gian là D, và với mỗi trang, cần phải xử lý R bản ghi và mỗi bản ghi mất thời gian C.

Tìm kiếm với phép chọn bằng: Giả sử chúng ta biết rằng có chính xác một bản ghi thoả mãn điều kiện bằng, tức là, việc chọn lọc được xác định dựa trên một khoá dự tuyển. Trung bình, chúng ta phải quét một nửa file, giả sử rằng bản ghi này tồn tại và việc phân bố giá trị trong trường tìm kiếm là đồng đều. Với mỗi trang dữ liệu được truy cập, chúng ta phải kiểm tra tất cả các bản ghi trên trang này để xem nó có phải là bản ghi cần tìm. Chi phí là 0.5B(D + RC). Tuy nhiên, nếu không có bản ghi nào thoả mãn điều kiện chọn, chúng ta phải quét toàn bộ file để chắc chắn điều này. Nếu phép chọn không dựa trên trường khoá dự tuyển (ví dụ, “Tìm các nhân viên có age=18”, chúng ta luôn luôn phải quét toàn bộ file vì các bản ghi có age = 18 có thể xuất hiện nhiều lần trong toàn bộ file, và chúng ta không biết có bao nhiêu bản ghi thoả mãn đang tồn tại.

Tìm kiếm với phép chọn miền: Toàn bộ file phải được quét vì các bản ghi thoả mãn phải có thể xuất hiện ở bất kỳ đâu trong file này, và chúng ta không biết có bao nhiêu bản ghi thoả mãn đang tồn tại. Chi phí là B(D + RC).

Thêm: Chúng ta giả sử rằng các bản ghi luôn được thêm vào cuối của file. Chúng ta phải nạp trang cuối cùng trong file này vào bộ nhớ trong, thêm bản ghi, và viết trang này trở lại đĩa. Chi phí là 2D + C.

Xoá: Chúng ta phải tìm bản ghi cần xoá, loại bỏ bản ghi này ra khỏi trang, và viết trang đã sửa này trở về đĩa. Để đơn giản, chúng ta giả sử rằng không có một sự cố gắng nén file nào được thực hiện để tiết kiệm không gian trống sinh ra sau khi xoá bản ghi.

Chúng ta giả sử rằng bản ghi bị xoá được xác định sử dụng record id. Vì chúng ta có thể dễ dàng xác định được page id thông qua record id, nên chúng ta có thể đọc trực tiếp trang này. Vì thế, chi phí tìm kiếm là D.

Nếu bản ghi bị xoá được xác định bằng cách sử dụng điều kiện bằng hoặc điều kiện miền trên một số trường, chi phí tìm kiếm được trình bày trong phần thảo luận về các phép chọn bằng và phép chọn miền. Chi phí của việc xoá cũng bị ảnh hưởng bởi số lượng các bản ghi thoả mãn, vì tất cả các trang chứa những bản ghi này cũng phải được sửa đổi theo.

Sorted Files

Quét: Chi phí là B(D + RC) bởi vì tất cả các trang phải được kiểm tra. Ghi nhớ rằng trường hợp này không tốt hay xấu hơn trường hợp các file không được sắp xếp. Tuy nhiên, thứ tự các bản ghi được quét tương ứng với thứ tự được sắp, tức là, tất các các bản ghi được quét theo thứ tự của age, và sau đó nếu age bằng nhau thì chúng quét theo thứ tự của sal.

Tìm kiếm với phép chọn bằng: Chúng ta giả sử rằng phép chọn bằng này được so sánh theo cặp hai trường là (age, sal), và lưu ý là các bản ghi được sắp xếp theo hai trường này. Mặt khác, chúng ta giả sử rằng điều kiện chọn được xác định trên ít nhất một trường đầu tiên trong khoá tổ hợp (ví dụ, age = 30). Nếu không (ví dụ, điều kiện là sal = 50 hoặc department = “Toy”), thứ tự được xếp này không giúp được chúng ta và chi phí giống hệt như trường hợp của heap file.

Chúng ta có thể định vị trang đầu tiên chứa bản ghi cần tìm bằng tìm kiếm nhị phân trong log₂B bước. (Phân tích này giả sử rằng các trang trong file được sắp này được lưu trữ tuần tự, và chúng ta có thể truy cập trang thứ i trên file này một cách trực tiếp). Mỗi bước yêu cầu một thao tác I/O đĩa và hai phép so sánh. Khi trang được biết, bản ghi thoả mãn đầu tiên có thể được định vị lại bằng tìm kiếm nhị phân trên trang này với chi phí là Clog2R. Như vậy, tổng chi phí là Dlog2B + Clog2R, nó được cải thiện đáng kể so với tìm kiếm trên heap file.

Nếu có một số bản ghi thoả mãn (ví dụ, “Tìm tất cả các bản ghi có age=18”), chúng được bảo đảm là liền kề nhau do các bản ghi được sắp xếp trên trường age, và vì thế chi phí truy cập tất cả các bản ghi này bằng chi phí xác định bản ghi đầu tiên (Dlog2B + Clog2R) cộng với chi phí đọc tất cả các bản ghi thoả mãn một cách tuần tự. Lý tưởng thì tất cả các bản ghi thoả mãn được đặt vừa trong một trang đơn. Nếu không có bản ghi nào thoả mãn, chi phí này được xác định bằng chi phí tìm kiếm bản ghi thoả mãn đầu tiên, đó là tìm trang chứa bản ghi thoả mãn và thực hiện tìm kiếm trên trang này.

Tìm kiếm với phép chọn miền: Một lần nữa giả sử rằng phép chọn miền được so sánh trên khoá tổ hợp này, bản ghi đầu tiên thoả mãn điều kiện chọn được xác định giống như trong tìm kiếm với điều kiện bằng. Sau đó, các trang dữ liệu được truy cập một cách tuần tự để tìm ra tất cả các bản ghi thoả mãn điều kiện; điều này tương tự như trong tìm kiếm bằng với rất nhiều bản ghi thoả mãn.

Chi phí là chi phí tìm kiếm cộng với chi phí truy cập tập các bản ghi thoả mãn điều kiện tìm kiếm. Với các phép chọn có miền nhỏ, tất cả các bản ghi thoả mãn có thể xuất hiện trong trang này. Với các miền tìm kiếm lớn hơn, chúng ta phải nạp thêm các trang để chứa các bản ghi thoả mãn.

Thêm: Để thêm một bản ghi nào đó mà vẫn duy trì được thứ tự sắp xếp, đầu tiên chúng ta phải tìm vị trí có thể thêm được trong file này, thêm bản ghi vào và sau đó viết lại các trang này lên đĩa (giả sử rằng file này không có khe rỗng nên tất cả các bản ghi cũ phải dịch chuyển một slot). Để lấy trung bình, chúng ta có thể giả sử rằng các bản ghi được thêm sẽ ở giữa của file. Vì thế, chúng ta phải đọc nửa cuối của file này và sau đó viết nó quay trở lại đĩa sau khi thêm bản ghi mới. Chi phí bằng chi phí của việc tìm vị trí đặt bản ghi mới cộng với 2•(0.5B(D + RC)), tức là bằng chi phí tìm kiếm cộng B(D+RC).

Xoá: Chúng ta phải tìm bản ghi cần xoá, loại bản ghi này khỏi trang và viết trang được sửa này quay lại đĩa. Chúng ta cũng phải đọc và ghi tất cả các trang phía sau vì tất cả bản ghi theo sau bản ghi được xoá phải được dồn lại phía trước để không bị lãng phí vùng trống trên đĩa.

Nếu các bản ghi cần xoá được xác định bằng điều kiện bằng hoặc miền, chi phí của việc xoá này phục thuộc vào số lượng các bản ghi thoả mãn điều kiện. Nếu điều kiện này được xác định trên trường được sắp, các bản ghi thoả mãn được đảm bảo là liền kề nhau, và bản ghi đầu tiên thoả mãn có thể được xác định bằng tìm kiếm nhị phân.

Clustered Files

Trong clustered file, kết quả nghiên cứu trên phạm vi rộng đã chỉ ra rằng các trang thường được sử dụng khoảng 67%. Vì thế, số lượng các trang dữ liệu vật lý khoảng 1.5B, và chúng ta sử dụng quan sát này trong phân tích sau.

Quét: Chi phí của việc quét bằng khoảng 1.5B(D + RC) bởi vì tất cả các trang phải được kiểm tra; chi phí này tương đương với trường hợp các file được sắp, cùng với những điều chỉnh hiển nhiên khi số lượng các trang dữ liệu tăng lên. Ghi nhớ rằng mô hình chi phí của chúng ta không cân nhắc đến sự khác nhau trong chi phí khi I/O tuần tự. Chúng ta hy vọng là các file được sắp làm việc tốt hơn trong trường hợp này, dù cho clustered file sử dụng ISAM.

Tìm kiếm với phép chọn bằng: Chúng ta giả sử rằng phép chọn bằng được so sánh trên khoá tìm kiếm (age, sal). Chúng ta có thể xác định được trang đầu tiên chứa bản ghi cần tìm trong logf1.5B bước, tức là bằng với việc tìm ra tất cả các trang từ gốc đến lá phù hợp. Trong thực tế, trang gốc dường như luôn ở buffer pool và chúng ta tiết kiệm được một I/O, nhưng chúng ta bỏ quan điều này trong khi phân tích. Mỗi bước yêu cầu một I/O đĩa và hai phép so sánh. Đối với mỗi trang, bản ghi thoả mãn đầu tiên có thể được định vị lại bằng một tìm kiếm nhị phân trên trang này với chi phí bằng Clog2R. Tổng chi phí là DlogF1.5B + Clog2R, nó được cải thiện đáng kể so với tìm kiếm thậm chí trên các sorted files.

Nếu có một số bản ghi thoả mãn (ví dụ, “Tìm tất cả các bản ghi có age=18”), chúng được bảo đảm là liền kề nhau do các bản ghi được sắp xếp trên trường age, và vì thế chi phí truy cập tất cả các bản ghi này bằng chi phí xác định bản ghi đầu tiên (Dlog2B + Clog2R) cộng với chi phí đọc tất cả các bản ghi thoả mãn một cách tuần tự.

Tìm kiếm với phép chọn miền: Một lần nữa giả sử rằng phép chọn miền được so sánh với trên khoá tổ hợp này, bản ghi đầu tiên thoả mãn điều kiện chọn được xác định giống như trong tìm kiếm với điều kiện bằng. Sau đó, các trang dữ liệu được truy cập một cách tuần tự (sử dụng các liên kết phía trước và phía sau ở mức lá) để tìm ra tất cả các bản ghi thoả mãn điều kiện; điều này tương tự như trong tìm kiếm bằng với rất nhiều bản ghi thoả mãn.

Thêm: Để thêm một bản ghi nào đó, đầu tiên chúng ta phải tìm trang lá để thêm bản ghi này trong chỉ mục, đọc tất cả các trang từ gốc đến lá. Sau đó chúng ta phải thêm bản ghi mới. Hầu hết thời gian, trang lá có những vùng trống đủ để thêm bản ghi mới, và tất cả chúng ta cần phải làm là viết ra ngoài những trang lá sau khi sửa. Đôi khi, trang lá đầy và chúng ta cần truy cập và sửa những trang khác, nhưng điều này là hiếm khi xảy ra và chúng ta có thể bỏ qua nó. Vì thế, tổng chi phí bằng chi phí tìm kiếm cộng với một thao tác viết DlogF1.5B + Clog2R + D.

Xoá: Chúng ta phải tìm bản ghi cần xoá, loại bỏ nó khỏi trang, và viết trang được sửa này ra đĩa. Những trình bày và phân tích chi phí cho trường hợp thêm được áp dụng tốt ở đây.

Heap File với Unclustered Tree Index

Số lượng các trang lá trong một chỉ mục phụ thuộc vào kích thước của cổng vào dữ liệu. Chúng ta giả sử rằng mỗi cổng vào dữ liệu trong chỉ mục này có kích thước bằng một phần mười kích thước một bản ghi dữ liệu nhân viên. Số lượng các trang lá trong chỉ mục này là 0.1(1.5B) = 0.15B nếu chúng ta biết các trang chỉ mục thường sử dụng khoảng 67% khả năng lưu trữ của nó. Tương tự, số lượng các cổng vào dữ liệu trên một trang là 10(0.67R) = 6.7R.

Quét: Xem Hình 1 minh hoạ về một chỉ mục không phân cụm. Để quét toàn bộ file chứa các bản ghi nhân viên, chúng ta có thể quét mức lá của chỉ mục này và với mỗi cổng vào dữ liệu quét bản ghi dữ liệu tương ứng nằm trong file để thu được các bản ghi dữ liệu được sắp theo (age, sal).

Chúng ta có thể đọc tất cả các cổng vào dữ liệu với chi phí 0.15B(D+6.7RC) I/Os. Bây giờ chúng ta đi đến một phần quan trọng: Chúng ta phải tìm các bản ghi dữ liệu với mỗi cổng vào dữ liệu trong chỉ mục này. Chi phí của việc tìm các bản ghi nhân viên là một I/O ứng với mỗi bản ghi, vì chỉ mục này không phân cụm và mỗi cổng vào dữ liệu trên một trang lá của chỉ mục này có thể trỏ đến một trang khác trong file nhân viên. Chi phí của bước này là BR(D+C). Nếu chúng ta muốn các bản ghi nhân viên được sắp theo thứ tự, sẽ là tốt hơn nếu chúng ta bỏ qua chỉ mục này và quét file nhân viên một cách trực tiếp và sau đó sắp xếp nó. Một quy tắc đơn giản là file có thể được sắp bằng thuật toán hai-đường trong đó mỗi đường yêu cầu đọc và ghi toàn bộ file. Vì thế, chi phí I/O của việc sắp xếp file có B trang là AB, chi phí này ít hơn nhiều so với chi phí sử dụng chỉ mục không phân cụm.

Tìm kiếm với phép chọn bằng: Chúng ta giả sử rằng phép chọn bằng được so sánh trên khoá tìm kiếm (age, sal). Chúng ta có thể xác định được trang đầu tiên chứa cổng vào dữ liệu cần tìm trong logf0.15B bước, tức là bằng với việc tìm ra tất cả các trang từ gốc đến lá phù hợp. Mỗi bước yêu cầu một I/O đĩa và hai phép so sánh. Đối với mỗi trang, cổng vào dữ liệu thoả mãn đầu tiên có thể được định vị lại bằng một tìm kiếm nhị phân trên trang này với chi phí bằng Clog26.7R. Bản ghi dữ liệu thoả mãn đầu tiên có thể được tìm trong file nhân viên bằng một thao tác I/O khác. Tổng chi phí là DlogF0.15B + Clog26.7R + D, nó được cải thiện đáng kể so với tìm kiếm trên các sorted files.

Nếu có một số bản ghi thoả mãn (ví dụ, “Tìm tất cả các bản ghi có age=18”), chúng không được bảo đảm là liền kề nhau. Chi phí truy cập tất cả các bản ghi này là chi phí định vị cổng vào dữ liệu thoả mãn đầu tiên DlogF0.15B + Clog26.7R cộng với một thao tác I/O ứng bvới một bản ghi thoả mãn. Vì thế chi phí sử dụng một chỉ mục không phân cụm phụ thuộc nhiều vào số lượng các bản ghi thoả mãn.

Tìm kiếm với phép chọn miền: Một lần nữa giả sử rằng phép chọn miền được so sánh với trên khoá tổ hợp này, bản ghi đầu tiên thoả mãn điều kiện chọn được xác định giống như trong tìm kiếm với điều kiện bằng. Sau đó, các cổng vào dữ liệu được truy cập một cách tuần tự (sử dụng các liên kết phía trước và phía sau ở mức lá của chỉ mục này) để tìm ra tất cả các bản ghi thoả mãn điều kiện. Với mỗi cổng vào dữ liệu thoả mãn, chúng ta phải mất thêm một thao tác I/O để truy cập các bản ghi nhân viên tương ứng. Chi phí có thể trở nên quá lớn một cách nhanh chóng khi số lượng các bản ghi thỏa mãn điều kiện chọn miền tăng lên. Như một quy tắc ngón tay cái, nếu 10% bản ghi dữ liệu thoả mãn điều kiện chọn, sẽ tốt hơn nếu chúng ta truy cập tất cả các bản ghi nhân viên, sắp xếp chúng và sau đó giữ lại những bản ghi thoả mãn điều kiện chọn.

Thêm: Đầu tiên chúng ta phải thêm bản ghi này vào heap file nhân viên, chi phí là 2D+C. Thêm nữa, chúng ta phải thêm cổng vào dữ liệu tương ứng trong chỉ mục này. Việc tìm một trang lá chính xác có cho phí DlogF0.5B + Clog26.7R, và viết nó ra ngoài sau khi thêm cổng vào dữ liệu mới mất chi phí là D.

Xoá: Chúng ta cần định vị bản ghi dữ liệu cần xoá trong file nhân viên và cổng vào dữ liệu trong file chỉ mục, và bước tìm kiếm này có chi phí Dlogf0.15B+ Clog26.7R + D. Sau đó chúng ta cần viết ra ngoài những trang đã bị thay đổi trong file chỉ mục và file dữ liệu, chi phí là 2D.

Heap File với Unclustered Hash Index

Giống như đối với unclustered tree indexes, chúng ta giả sử rằng mỗi cổng vào dữ liệu có kích thước bằng một phần mười kích thước một bản ghi dữ liệu. Chúng ta chỉ đề cập đến băm tĩnh trong phân tích của chúng ta, và để đơn giản chúng ta giả sử rằng không có các chuỗi tràn.

Trong một file được băm tĩnh, các trang thường sử dụng khoảng 80% khả năng lưu trữ của nó (để có vùng trống phục vụ thao tác thêm và tối thiểu hoá khả năng overflows khi file được mở rộng). Đạt được điều này bằng cách thêm một trang mới vào bucket khi các bản ghi được nạp vào hashed file nếu mỗi trang đang tồn tại đều đã sử dụng 80% khả năng của nó. Vì thế số lượng các trang cần để lưu các cổng vào dữ liệu sẽ bằng 1.25 lần số lượng các trang trong trường hợp các cổng vào dữ liệu đã đầy, tức là bằng 1.25(0.105) = 0.125B. Số lượng các cổng vào dữ liệu đặt vừa khít trong một trang là 10(0.80R) = 8R.

Quét: Như đối với unclustered tree index, tất cả các cổng vào dữ liệu có thể được truy cập với chi phí thấp, ở mức 0.125B(D + 8RC) I/Os. Tuy nhiên, với mỗi cổng vào dữ liệu, chúng ta phải chịu thêm một thao tác I/O để truy cập bản ghi dữ liệu tương ứng, chi phí của bước này là R(D + C). Chi phí này là quá lớn và thêm nữa, kết quả lại không được sắp xếp. Vì thế không có các thao tác quét trên chỉ mục băm.

Tìm kiếm với phép chọn bằng: Thao tác này được hỗ trợ rất hiệu quả bởi các phép chọn so sánh, tức là các điều kiện bằng được xác định với mỗi trường trong khoá tìm kiếm tổ hợp (age, sal). Chi phí của việc xác định một trang chứa các cổng vào dữ liệu thoả mãn là H. Giả sử rằng bucket này gồm chỉ một trang (tức là, không có các trang tràn), việc truy cập nó mất chi phí là D. Nếu chúng ta giả sử rằng chúng ta tìm các cổng vào dữ liệu sau khi quét một nửa số bản ghi trên trang này, chi phí của việc quét trang này là 0.5(8R)C = 4RC. Cuối cùng, chúng ta phải truy cập các cổng vào dữ liệu từ file nhân viên, chi phí là D. Vì thế, tổng chi phí là H + 2D + 4RC, chi phí này thậm chí còn thấp hơn chi phí đối với tree index.

Nếu một vài bản ghi thoả mãn, chúng không được đảm bảo là được đặt liền kề nhau. Chi phí truy cập tất cả các bản ghi như vậy bằng chi phí của việc xác định cổng vào dữ liệu đầu tiên thoả mãn (H + D + 4RC) cộng với một I /O ứng với một bản ghi thoả mãn. Vì thế, chi phí sử dụng chỉ mục không phân cụm phụ thuộc rất nhiều vào số lượng các bản ghi thoả mãn.

Tìm kiếm với phép chọn miền: Toàn bộ heap file chứa các bản ghi nhân viên phải được quét với chi phí là B(D + RC).

Thêm: Đầu tiên chúng ta phải thêm bản ghi này vào heap file, chi phí là 2D + C. Thêm nữa, trang tương ứng trong chỉ mục này phải được xác định, thay đổi để thêm một cổng vào dữ liệu mới, và sau đó viết nó trở lại đĩa. Chi phí là H + 2D + C.

Xoá: Chúng ta cần định vị bản ghi dữ liệu cần xoá trong file nhân viên và cổng vào dữ liệu trong file chỉ mục; bước tìm kiếm này có chi phí là H + 2D + 4RC. Bây giờ, chúng ta cần viết ra ngoài những trang được thay đổi trong chỉ mục và file dữ liệu, chi phí là 2D.

So sánh chi phí I/O

Hình 4 so sánh chi phí I/O với các cấu trúc file khác nhau chúng ta đã trình bày ở trên. Heap file có cách lưu trữ hiệu quả và hỗ trợ thao tác quét và thêm các bản ghi một cách nhanh chóng. Tuy nhiên, nó lại chậm trong các thao tác tìm kiếm và xoá.

Sort file cũng có cách lưu trữ hiệu quả, nhưng lại chậm trong các thao tác thêm và xoá bản ghi. Việc tìm kiếm thực hiện nhanh hơn trong heap files. Bạn nên ghi nhớ rằng trong một DBMS thực, một file dường như không bao giờ được sắp xếp hoàn toàn.

Clustered file có tất cả các ưu điểm của sorted file và nó hỗ trợ việc thêm và xoá một cách hiệu quả. Tìm kiếm thậm chí còn nhanh hơn cả sorted files, mặc dù sorted file có thể nhanh hơn khi có một số lượng lớn các bản ghi dữ liệu được truy cập một cách tuần tự, vì I/O theo khối được thực hiện hiệu quả.

Unclustered tree và hash indexes thực hiện tìm kiếm, thêm và xoá nhanh hơn nhưng quét và tìm kiếm miền lại chậm. Hash indexes thực hiện nhanh hơn một chút trên các tìm kiếm bằng, nhưng chúng không hỗ trợ tìm kiếm miền.

Tóm lại, Hình 4 chỉ ra rằng không có tổ chức file nào hiệu quả hơn hẳn trong tất cả các trường hợp.

Tác động của Lưu lượng công việc

Điều đầu tiên được xem xét là lưu lượng công việc nào cần thực thi và những thao tác phổ biến. Các tổ chức file và các chỉ mục khác nhau tạo ra sự khác nhau trong thực thi các phép toán, phần này chúng ta đã nghiên cứu ở trên.

Nói chung, chỉ mục giúp truy cập các cổng vào dữ liệu thoả mãn đi