Bài giảng Cấu trúc dữ liệu và giải thuật - Lưu trữ ngoài - Nguyễn Văn Linh

t khối của MergeSort, ta thấy rõ ràng Ví dụ về sắp xếp trộn nhiều đườngSắp xếp tập tin F có 23 mẩu tin với khóa là các số nguyên: 2 31 13 5 98 96 10 40 54 85 65 9 30 39 90 13 10 8 69 77 8 10 22.Sử dụng 6 tập tin, giả sử bộ nhớ trong có thể chứa được 3 mẩu tin.F[1]213319658586977F[2]596983039901022F[3]10405481013Ví dụ về sắp xếp trộn nhiều đường: Bước 1Từ 3 tập tin đã cóF[1]213319658586977F[2]596983039901022F[3]10405481013Trộn các đường độ dài 3 trong các tập tin F[1], F[2], F[3] thành các đường độ dài 9 và ghi vào trong các tập tin F[4], F[5] và F[6].F[4]2510133140549698F[5]8910133039658590F[6]810226977Ví dụ về sắp xếp trộn nhiều đường: Bước 2Đổi vai trò các tập tin F[1], F[2] và F[3] cho F[4],F[5] và F[6] tương ứngTrộn các đường độ dài 9 trong các tập tin F[1], F[2], F[3] thành đường độ dài 23 và ghi vào trong các tập tin F[4] còn các tập tin F[5] và F[6] đều rỗng. F[4]2510133140549698F[5]8910133039658590F[6]810226977F[4]25889101010131322303139405465697785909698Lưu trữ thông tin trong tập tinChúng ta sẽ coi một tập tin như là một chuỗi tuần tự các mẩu tin, mỗi mẩu tin bao gồm nhiều trường (field). Các mẩu tin có độ dài cố định và khảo sát các thao tác trên tập tin là:Insert: Thêm một mẩu tin vào trong một tập tin.Delete: Xoá một mẩu tin từ trong tập tin.Modify: Sửa đổi thông tin trong các mẩu tin.Retrieve: Tìm lại thông tin được lưu trong tập tin.Tập tin tuần tự Tổ chức: một danh sách liên kết của các khối, các mẩu tin được lưu trữ trong các khối theo một thứ tự bất kỳ.Tìm mẩu tin: Đọc từng khối, với mỗi khối ta tìm mẩu tin cần tìm trong khối, nếu không tìm thấy ta lại đọc tiếp một khối khác. Quá trình cứ tiếp tục cho đến khi tìm thấy mẩu tin hoặc duyệt qua toàn bộ các khối của tập tin và trong trường hợp đó thì mẩu tin không tồn tại trong tập tin.Tập tin tuần tự (tt)Thêm mẩu tin mới: Đưa mẩu tin này vào khối cuối cùng của tập tin nếu như khối đó còn chỗ trống. Ngược lại nếu khối cuối cùng đã hết chỗ thì xin cấp thêm một khối mới, thêm mẩu tin vào khối mới và nối khối mới vào cuối danh sách.Sửa đổi mẩu tin: Tìm mẩu tin cần sửa, thực hiện các sửa đổi cần thiết sau đó ghi lại mẩu tin vào vị trí cũ trong tập tin. Tập tin tuần tự (tt)Xoá mẩu tin: Tìm mẩu tin đó, nếu tìm thấy ta có thể thực hiện một trong các cách xoá sau đây:Một là xoá mẩu tin cần xoá trong khối lưu trữ nó, nếu sau khi xoá, khối trở nên rỗng thì xoá khối khỏi danh sách.Hai là đánh dấu xoá mẩu tin bằng một trong hai cách:Thay thế mẩu tin bằng một giá trị nào đó mà giá trị này không bao giờ là giá trị thật của bất kỳ một mẩu tin nào.Sử dụng bit xóaĐánh giá tập tin tuần tự Ðây là một phương pháp tổ chức tập tin đơn giản nhất nhưng kém hiệu quả nhất. Giả sử tập tin có n mẩu tin và mỗi khối lưu trữ được k mẩu tin thì toàn bộ tập tin được lưu trữ trong n/k khối. Do đó mỗi lần tìm (hoặc thêm hoặc sửa hoặc xoá) một mẩu tin thì phải truy xuất n/k khối.Tăng tốc độ cho các thao tác tập tinÐể cải thiện tốc độ thao tác trên tập tin, chúng ta phải tìm cách giảm số lần truy xuất khối. Muốn vậy phải tìm các cấu trúc sao cho khi tìm một mẩu tin chỉ cần truy xuất một số nhỏ các khối. Ðể tạo ra các tổ chức tập tin như vậy chúng ta phải giả sử rằng mỗi mẩu tin có một khoá (key).Hai mẩu tin khác nhau thì khoá của chúng phải khác nhau.Tập tin băm (hash files): Tổ chứcBảng băm là mảng một chiều B gồm m phần tử B[0], B[1], ..., B[m-1]). Mỗi phần tử là một con trỏ, trỏ tới phần tử đầu tiên của danh sách liên kết các khối.Ðể phân phối mẩu tin có khóa x vào trong các danh sách liên kết, ta dùng hàm băm.h(x) = x MOD m.Ví dụ về tập tin bảng bămMột tập tin có 24 mẩu tin với giá trị khóa là các số nguyên: 3, 5, 12, 65, 34, 20, 21, 17, 56, 1, 16, 2, 78, ,94, 38 ,15 ,23, 14, 10, 29, 19, 6, 45, 36Giả sử chúng ta có thể tổ chức tập tin này vào trong bảng băm gồm 7 phần tử và giả sử mỗi khối có thể chứa được tối đa 3 mẩu tin. Với mỗi mẩu tin r có khóa là x ta xác định h(x) = x MOD 7 và đưa mẩu tin r vào trong một khối của danh sách liên kết được trỏ bởi B[h(x)].0215614•1178152936•26516223•331794381045•4•551219•634206•Tập tin băm: Tìm mẩu tinÐể tìm một mẩu tin r có khóa là x, chúng ta xác định h(x) chẳng hạn h(x) = i, khi đó ta chỉ cần tìm r trong danh sách liên kết được trỏ bởi B[i]. Chẳng hạn để tìm mẩu tin r có khóa là 36, ta tính h(36) = 36 MOD 7 = 1. Như vậy nếu mẩu tin r tồn tại trong tập tin thì nó phải thuộc một khối nào đó được trỏ bởi B[1]. Tập tin băm: Thêm mẩu tin mớiÐể thêm mẩu tin r có khoá x, trước hết ta phải tìm mẩu tin r. Nếu tìm thấy thì thông báo “mẩu tin đã tồn tại” Ngược lại ta sẽ tìm một khối (trong danh sách các khối của lô được trỏ bởi B[h(x)]) còn chỗ trống và thêm r vào khối này. Nếu không còn khối nào đủ chỗ cho mẩu tin mới ta yêu cầu hệ thống cấp phát một khối mới và đặt mẩu tin r vào khối này rồi nối khối mới này vào cuối danh sách liên kết của lô.Tập tin băm: Xoá mẩu tinÐể xoá mẩu tin r có khoá x, trước hết ta phải tìm mẩu tin này. Nếu không tìm thấy thì thông báo “Mẩu tin không tồn tại”. Nếu tìm thấy thì đặt bít xoá cho nó. Ta cũng có thể xoá hẳn mẩu tin r và nếu việc xoá này làm khối trở nên rỗng thì ta giải phóng khối này (xoá khối khỏi danh sách liên kết các khối).Tập tin băm: Đánh giáGiả sử tập tin có n mẩu tin và mỗi khối lưu trữ được k mẩu tin thì tập tin cần n/k khối. Trung bình mỗi danh sách liên kết (mỗi lô) của bảng băm có n/mk khối (do bảng băm có m lô), mà chúng ta chỉ tìm trong một danh sách liên kết nên ta chỉ phải truy xuất n/mk khối. Số này nhỏ hơn m lần so với cách tổ chức tập tin tuần tự (trong tập tin tuần tự ta cần truy xuất tất cả các khối, tức là n/k khối). Tập tin chỉ mục (index file): Tổ chứcTập tin chính và tập tin chỉ mục thưa (sparse index). Tập tin chính bao gồm các khối lưu các mẩu tin sắp thứ tự theo giá trị khóa. Tập tin chỉ mục thưa bao gồm các khối chứa các cặp (x,p) trong đó x là khoá của mẩu tin đầu tiên trong một khối của tập tin chính, còn p là con trỏ, trỏ đến khối đó.Tập tin chỉ mục: Ví dụ Các khối trong tập tin chính lưu trữ được tối đa 3 mẩu tin, mỗi khối trong tập tin chỉ mục lưu trữ được tối đa 4 cặp khoá – con trỏ. TT chỉ mục(3, ) (10, ) (23, ) (28, )(42, ) (48, )TT chính3 5 810 11 1623 25 2728 31 3842 46 48 52 60B1B2B3B4B5B6Tập tin chỉ mục: Tìm mẩu tinÐể tìm mẩu tin r có khoá x, ta phải tìm cặp (z,p) với z là giá trị lớn nhất và z ≤ x. Mẩu tin r có khoá x nếu tồn tại thì sẽ nằm trong khối được trỏ bởi p. Chẳng hạn để tìm mẩu tin r có khoá 46 trong tập tin được biểu diễn trong hình sau:TT chỉ mục(3, ) (10, ) (23, ) (28, )(42, ) (48, )TT chính3 5 810 11 1623 25 2728 31 3842 46 48 52 60B1B2B3B4B5B6Tập tin chỉ mục: Thêm mẩu tin mớiGiả sử tập tin chính được lưu trong các khối B1, B2, ..., Bm. Dùng thủ tục tìm kiếm để xác định một khối Bi nào đó. Nếu tìm thấy thì thông báo “mẩu tin đã tồn tại”, ngược lại, Bi là nơi có thể chứa mẩu tin r. Nếu Bi còn chỗ trống thì xen r vào đúng vị trí của nó trong Bi. Chỉnh lại tập tin chỉ mục nếu mẩu tin mới trở thành mẩu tin đầu tiên trong khối Bi. Nếu Bi không còn chỗ trống để xen thì ta phải xét khối Bi+1 để có thể chuyển mẩu tin cuối cùng trong khối Bi thành mẩu tin đầu tiên của khối Bi+1 và xen mẩu tin r vào đúng vị trí của nó trong khối Bi . Ðiều chỉnh lại tập tin chỉ mục cho phù hợp với trạng thái mới của Bi+1. Quá trình này có thể dẫn đến việc ta phải xét khối Bm, nếu Bm đã hết chỗ thì yêu cầu hệ thống cấp thêm một khối mới Bm+1, chuyển mẩu tin cuối cùng của Bm sang Bm+1, mẩu tin cuối cùng của Bm-1 sang Bm Xen mẩu tin r vào khối Bi và cập nhật lại tập tin chỉ mục. Việc cấp phát thêm khối mới Bm+1 đòi hỏi phải xen thêm một cặp khoá-con trỏ vào khối cuối cùng của tập tin chỉ mục, nếu khối này hết chỗ thì xin cấp thêm một khối mới để xen cặp khóa-con trỏ này. Ví dụ thêm mẩu tin mớiXen mẩu tin r với khóa x = 24 vào trong tập tin được biểu diễn trong hình sau:TT chỉ mục(3, ) (10, ) (23, ) (28, )(42, ) (48, )TT chính3 5 810 11 1623 25 2728 31 3842 46 48 52 60B1B2B3B4B5B6Cấu trúc của tập tin sau khi thêm mẩu tin r như sau:TT chỉ mục(3, ) (10, ) (23, ) (27, )(38, ) (48, )TT chính3 5 810 11 1623 24 2527 28 3138 42 46 48 52 60B1B2B3B4B5B6Tập tin chỉ mục: Xoá mẩu tinTìm r, nếu không tìm thấy thì thông báo “Mẩu tin không tồn tại”.Ngược lại ta xoá mẩu tin r trong khối chứa nó.Nếu mẩu tin bị xoá là mẩu tin đầu tiên của khối thì phải cập nhật lại giá trị khoá trong tập tin chỉ mục. Trong trường hợp khối trở nên rỗng sau khi xoá mẩu tin thì giải phóng khối đó và xoá cặp (khoá, con trỏ) của khối trong tập tin chỉ mục. Việc xoá trong tập tin chỉ mục cũng có thể dẫn đến việc giải phóng khối trong tập tin này.Tập tin chỉ mục: Đánh giáTa thấy việc tìm một mẩu tin chỉ đòi hỏi phải đọc chỉ một số nhỏ các khối (một khối trong tập tin chính và một số khối trong tập tin chỉ mục). Tuy nhiên trong việc xen thêm mẩu tin, như trên đã nói, có thể phải đọc và ghi tất cả các khối trong tập tin chính. Ðây chính là nhược điểm của tập tin chỉ mục.Cây tìm kiếm m-phân Cây tìm kiếm m-phân (m-ary tree) là sự tổng quát hoá của cây tìm kiếm nhị phân trong đó mỗi nút có thể có m nút con. Giả sử n1 và n2 là hai con của một nút nào đó, n1 bên trái n2 thì tất cả các con của n1 có giá trị nhỏ hơn giá trị của các nút con của n2. B-cây B-cây bậc m là cây tìm kiếm m-phân cân bằng có các tính chất sau:Nút gốc hoặc là lá hoặc có ít nhất hai nút con,Mỗi nút, trừ nút gốc và nút lá, có từ m/2 đến m nút con vàCác đường đi từ gốc tới lá có cùng độ dài.Tập tin B-cây:Tổ chức Mỗi nút trên cây là một khối trên đĩa, các mẩu tin của tập tin được lưu trữ trong các nút lá trên B-cây và lưu theo thứ tự của khoá. Giả sử mỗi nút lá lưu trữ được nhiều nhất b mẩu tin.Mỗi nút không phải là nút lá có dạng (p0,k1,p1,k2,p2,...,kn,pn), với pi (0 ≤ i ≤ n) là con trỏ, trỏ tới nút con thứ i của nút đó và ki là các giá trị khóa. Các khoá trong một nút được sắp thứ tự, tức là k1 phải xen một khóa và một con trỏ vào nút cha của P... Quá trình này có thể sẽ dẫn tới nút gốc và cũng có thể phải chia cắt nút gốc, trong trường hợp này phải tạo ra một nút gốc mới mà hai con của nó là hai nửa của nút gốc cũ. Khi đó chiều cao của B-cây sẽ tăng lên 1.