Chơng 3 Tìm kiếm trên bộ nhớ ngoài
3.3. File có chỉ số
Cấu trúc file băm đợc tạo ra dựa trên khoá của mẫu tin. Trong mục này chúng ta trình bày một phơng pháp tổ chức file khác cũng dựa vào khoá của mẫu tin bằng cách sắp xếp các mẫu tin theo thứ tự tăng dần của các giá trị khoá.
Cấu trúc file chỉ số đợc hình thành nh sau:
Ta sắp xếp các mẫu tin của file theo giá trị khoá tăng dần vào một số khối cần thiết. Ta có thể sắp xếp các mẫu tin vào một khối cho tới khi khối đầy. Song thông thờng, trong mỗi khối ngời ta để dành một không gian cho các mẫu tin đợc thêm vào file sau này. Lý do là để phép toán bổ sung vào file đợc thực hiện dễ dàng hơn. Ta sẽ gọi file gồm các mẫu tin chứa trong các khối này là file chính,
để phân biệt với file chỉ số đợc tạo ra sau đây:
36 92 232 5 9 21 49 169 58 3 143 195 211
121
Hệ số của một khối là cặp (v, b), trong đó b là địa chỉ của khối, còn v là giá trị khoá nhỏ nhất của các mẫu tin trong khối b. Từ các khối của file chính, ta sẽ tạo ra file chỉ số, file này gồm các chỉ số khối của file chính. Các chỉ số khối
đợc sắp theo thứ tự tăng dần của khoá vào một số khối cần thiết. Các khối này có thể đợc móc nối với nhau tạo thành một danh sách liên kết. Trong trờng hợp này file chỉ số gồm một danh sách liên kết các khối, các khối chứa các chỉ số khối của file chính. Một cách khác ta cũng có thể sử dụng một bảng để lu giữ địa chỉ của các khối trong file chỉ số.
Ví dụ 3.3: Tệp gồm các mẫu tin có các khoá nh sau:
3, 5, 9, 15, 21, 36, 49, 58, 92, 121, 143, 169, 195, 211, 232
Giả sử mỗi khối chứa 4 mẫu tin (với tệp mẫu tin đợc đại diện bởi khoá).
Song ở đây mỗi khối sẽ thực hiện lu trữ 3 mẫu tin (3 khoá) để các phép toán trên file thực hiện đơn giản hơn.
Đầu tiên ta sắp xếp các khoá của file theo thứ tự tăng dần vào các khối, ta
đợc:
Tiếp theo “Xây dựng” tệp chỉ số:
Chỉ số của mỗi khối là cặp (v, b), b là địa chỉ khối đợc đánh số từ 0 đến 4, v là giá trị khoá nhỏ nhất trong các mẫu tin trong khối b và v ở đây gồm:
Khối có địa chỉ là 0, v sẽ là 3 Khối có địa chỉ là 1, v sẽ là 15 Khối có địa chỉ là 2, v sẽ là 49 Khối có địa chỉ là 3, v sẽ là 121 Khối có địa chỉ là 4, v sẽ là 195 Cấu trúc file sẽ nh sau:
3 5 9 15 21 36 49 58 92 121143 169 195 211 232
T×m kiÕm:
Giả sử ta cần tìm mẫu tin x với khoá v cho trớc. Trớc hết ta cần tìm trên file chỉ số một chỉ số (v1, b1) sao cho v1 có giá trị lớn nhất trong file chỉ số thoả
mãn điều kiện v1 ≤ v. Ta sẽ nói v1 phủ v.
Việc tìm kiếm trên file chỉ số một giá trị khoá v1 phủ giá trị khoá v cho tr- ớc có thể thực hiện bằng cách tìm tuần tự hoặc tìm kiếm nhị phân.
Trong tìm kiếm tuần tự, ta cần xem xét tất cả các mẫu tin của file chỉ số cho tới khi tìm thấy một chỉ số (v1, b1) với v1 phủ v. Nếu v nhỏ hơn giá trị khoá
của mẫu tin đầu tiên trong file chỉ số thì điều đó có nghĩa là trong file chỉ số không chứa giá trị khoá phủ v.
Phơng pháp có hiệu quả hơn là tìm kiếm nhị phân. Giả sử các mẫu tin của file chỉ số đợc sắp xếp vào các khối đợc đánh số từ 1 đến m. Xét khối thứ [m/2], giả sử (v2, b2) là mẫu tin đầu tiên trong khối. So sánh giá trị khoá cho trớc v với giá trị khoá v2. Nếu v < v2 ta tiến hành tìm kiếm trên các khối 1, 2, ..., [m/2] - 1.
Còn nếu v ≥ v2, ta tiến hành tìm kiếm trên các khối [m/2], [m/2] + 1, ..., m. Quá
trình trên đợc lặp lại cho tới khi ta chỉ cần tìm kiếm trên một khối. Lúc này ta chỉ việc lần lợt so sánh giá trị khoá v cho trớc với giá trị khoá chứa trong khối này.
Để tìm ra mẫu tin x với khoá v cho trớc, trớc hết ta tìm trên file chỉ số một chỉ số (v1, b1) với v1 phủ v. Sau đó lần lợt xét các mẫu tin trong khối có địa chỉ b1
để phát hiện ra các mẫu tin có khoá v, hoặc không nếu trong khối không có mẫu tin nào với khoá là v. Nếu trên file chỉ số không chứa giá trị khoá v1 phủ v, thì file chính không chứa mẫu tin có khoá v.
3 15 49 121 195
3 5 9 15 21 36 49 58 92 121143 169 195 211 232
Ví dụ: Với cấu trúc file ở ví dụ 3.3, giả sử tìm kiếm mẫu tin có khoá 21.
Đầu tiên tìm trên file chỉ số một cặp (v1, b1) sao cho v1 là giá trị lớn nhất trong file chỉ số, thoả mãn v1 ≤ 21, b1 ở đây đợc đánh số: 0, 1, 2, ... Việc tìm kiếm này
đợc thực hiện bằng hai cách nh sau:
- T×m kiÕm tuÇn tù:
Đọc lần lợt các mẫu tin trên file chỉ số và so sánh với 21: Mẫu tin đầu tiên là 3 < 21. Đọc tiếp và lần lợt so sánh ta thấy các mẫu tin có khoá 5, 15 đều bé hơn 21 và sau khoá 15 là khoá 49 > 21. Nh vậy ta đã tìm đợc cặp (15, 1)
- Tìm kiếm nhị phân:
Theo các lu trữ nh ở ví dụ 3.3 thì file chỉ số có 3 khối, chia đôi số khối ta có nửa số khối trớc gồm:
và nửa số khối sau gồm:
Thực hiện so sánh 21 với khoá 121, thấy rằng 21 < 195 . Nh vậy ta sẽ tiếp tục tìm kiếm trên nửa trớc bằng cách tiếp tục chia đôi số khối nửa trớc một lần nữa, ta đợc 2 khối :
So sánh 21 với 49, thấy 21 < 49 nên ta tìm kiếm trên nửa số khối trớc (chỉ có một khối). Trên khối này, ta sẽ tìm đợc cặp (15, 1)
Sau khi đã tìm đợc cặp chỉ số trên file chỉ số, tiếp tục thực hiện tìm kiếm trên khối có địa chỉ là 1: Đọc lần lợt các khoá trong khối có địa chỉ bằng 1 và tìm
đợc khoá 21.
3 15 49 121
195
3 15 49 121
Nh vậy, việc tìm kiếm này không cần phải đọc hết tất cả các mẫu tin trong file chính mà chỉ cần đọc các mẫu tin trong file chỉ số để tìm ra cặp chỉ số mà có thể chứa mẫu tin cần tìm sau đó lần lợt đọc các mẫu tin trong khối có địa chỉ tơng ứng đó.
Bổ sung:
Giả sử ta cần thêm vào file mẫu tin r với giá trị khoá v. Giả sử file chính đ- ợc chứa trong các khối B1, B2, ...., Bk và các giá trị khoá của các mẫu tin trong khối Bi nhỏ hơn các giá trị khoá trong khối Bi+1.
Trớc hết ta cần tìm ra khối Bi cần phải xếp mẫu tin r vào đó. Muốn vậy ta
áp dụng thủ tục tìm kiếm trên file chỉ số để tìm ra chỉ số (v1, b1) với v1 phủ v. Nếu tìm thấy thì Bi là khối có địa chỉ b1, ngợc lại Bi là khối B1.
Trong trờng hợp Bi cha đầy và r còn cha có ở trong khối Bi thì ta xếp mẫu tin r vào đúng vị trí của nó, tức là phải đảm bảo trật tự tăng dần theo khoá.
Nếu Bi là B1 thì sau khi thêm vào mẫu tin r, nó trở thành mẫu tin đầu tiên trong khối B1, do đó ta cần phải tiến hành sửa đổi chỉ số của khối B1 trong file chỉ sè.
Trong trờng hợp Bi đã đầy, ta tiến hành xếp mẫu tin r vào đúng vị trí của nó trong Bi, khi đó còn thừa ra một mẫu tin. Tìm đến khối Bi+1 (ta biết đợc địa chỉ của khối Bi+1 bằng cách tìm trong chỉ số). Nếu Bi+1 cha đầy thì ta xếp mẫu tin thừa ra của Bi vào vị trí đầu tiên trong khối Bi+1 đồng thời sửa lại chỉ số của Bi+1 trong file chỉ số. Nếu khối cũng đầy hoặc không tồn tại khi Bi là Bk thì ta thêm vào file chính một khối mới và xếp mẫu tin r vào khối mới này. Chỉ số của khối mới thêm vào cần phải đợc xen vào file chỉ số.
Ví dụ: Cũng với cấu trúc lu trữ ở ví dụ 3.3, hãy bổ sung vào file một mẫu tin có khoá 65
Tìm đến khối mà sẽ chứa khoá 65 bằng cách tìm cặp chỉ số (v1, b1) sao cho
lu trữ theo cách mỗi khối còn chừa ra một chỗ trống cho nên xen khoá 65 vào tr- ớc 92 và lúc này 92 sẽ bị đẩy vào chỗ trống cuối cùng trong khối. Lúc này ta đợc mét cÊu tróc nh sau:
Loại bỏ:
Để loại bỏ mẫu tin r có khoá v, ta áp dụng thủ tục tìm kiếm để định vị mẫu tin trong file. Sau đó tiên hành xoá bỏ r bằng nhiều cách khác nhau, chẳng hạn có thể đặt lại giá trị của bit đầy/ rỗng tơng ứng với mẫu tin cần loại bỏ ở đầu khối.
Ví dụ: Giả sử với cấu trúc lu trữ ở ví dụ 3.3, ta cần loại bỏ mẫu tin có khoá
21. Đầu tiên tìm khoá 21 giống nh đã trình bày trong phép toán tìm kiếm. Sau đó tiến hành xoá mẫu tin có khoá 21 bằng cách đặt lại giá trị bit.