Chơng 3 Tìm kiếm trên bộ nhớ ngoài
3.4. Cây tìm kiếm ngoài
Mục đích của chúng ta là nghiên cứu các cấu trúc dữ liệu biểu diễn file sao cho các phép toán trên file đợc thực hiện hiệu quả, tức là với số lần thực hiện phép toán truy cập khối ít nhất có thể đợc, khi cần phải tìm kiếm, bổ sung, loại bỏ hoặc sửa đổi các mẫu tin trên file. B- cây là một cấu trúc dữ liệu đặc biệt thích hợp để biểu diễn file. Trong mục này chúng ta sẽ trình bày B-cây và các kỹ thuật
để thực hiện các phép toán tìm kiếm, bổ sung và loại bỏ trên B-cây.
3.4.1. Cây tìm kiếm đa nhánh (Multiway Search Trees)
Cây tìm kiếm n nhánh là sự tổng quát hoá của cây tìm kiếm nhị phân, trong đó mỗi đỉnh của cây có nhiều nhất n con. Các đỉnh của cây đợc gắn với giá
trị khoá của mẫu tin. Nếu đỉnh A có r con (r ≤ n) thì nó chứa đúng r - 1 khoá (k1,
3 15 49 121 195
3 5 9 15 21 36 49 58 65 92 121143 169 195 211 232
k2, ..., kr-1) trong đó k1 < k2 < ... < kr-1 (chúng ta giả thiết rằng các giá trị khoá đợc sắp xếp giá trị tuyến tính). Tổng quát hoá tính chất về khoá gắn với các đỉnh của cây tìm kiếm nhị phân, cây tìm kiếm n nhánh phải thoả mãn tính chất sau đây.
Nếu đỉnh A có r con và chứa các khoá (k1, k2, ..., kr-1) thì các khoá chứa trong các
đỉnh của cây con thứ nhất của đỉnh A nhỏ hơn k1, còn các khoá nhỏ hơn chứa trong các đỉnh của cây con thứ i (i = 2, 3, ..., r - 1) phải lớn hơn hoặc bằng ki-1 và nhỏ hơn ki, các khoá chứa trong các đỉnh của cây con thứ r phải lớn hơn hoặc bằng kr-1. Mỗi lá của cây chứa một số khoá, tối đa là s.
3.4.2. B-C©y
B-cây là một loại đặc biệt của cây tìm kiếm n nhánh cân bằng. B-cây đợc
định nghĩa nh sau:
B-cây cấp n là cây tìm kiếm n nhánh thoả mãn các tính chất sau:
1. Nếu cây không phải là cây chỉ gồm có gốc thì gốc có ít nhất hai con và nhiÒu nhÊt n con.
2. Mỗi đỉnh trong của cây, trừ gốc, có ít nhất n/2 con và nhiều nhất n con.
3. Tất cả các lá của cây trên cùng một mức. (Nói cách khác, tất cả các đ- ờng đi từ gốc tới lá cây có cùng độ dài).
T tởng của việc tổ chức File dới dạng B-cây là nh sau ta sắp xếp các mẫu tin của file (file chính) vào một số khối cần thiết. Mỗi khối này sẽ là lá của B- cây. Trong mỗi khối các mẫu tin đợc sắp xếp theo thứ tự tăng dần của khoá. Các chỉ số của các khối này (các lá) lại đợc sắp xếp vào một số khối mới. Trong mỗi khối này, các chỉ số đợc sắp xếp theo thứ tự tăng dần của khoá. Trong B-cây, các khối này sẽ là các đỉnh ở mức trên của mức các lá. Ta lại lấy chỉ số của các khối vừa tạo ra sắp xếp vào một số khối mới.
Các khối này lại là các đỉnh ở mức trên của mức từ đó chúng đợc tạo ra.
Quá trình trên sẽ đợc tiếp tục cho tới khi các chỉ số có thể xếp gọn vào một khối.
Nh vây mỗi đỉnh của B-cây là một khối. Mỗi đỉnh trong của B-cây có dạng (p0, v1, p1, v2, p2, ..., vm, pm) trong đó v1 < v2 <...< vm và (vi, pi), 0 ≤ i ≤ m, là chỉ số của khối, tức là vi là giá trị khoá nhỏ nhất trong một khối, còn pi là con trỏ trỏ tới khối chứa khoá nhỏ nhất vi, tức là con trỏ trỏ tới đỉnh con thứ i của đỉnh trong
đang nói tới. Lu ý rằng giá trị của khoá v0 không đợc lu giữ ở đỉnh trong để tiết kiệm bộ nhớ.
Ví dụ 3.4: Hình sau biểu diễn một B-cây cấp 3. B-cây đợc tạo thành từ 11 khối đợc đánh số B1, B2, ..., B11. Mỗi khối là đỉnh trong chứa đợc 3 chỉ số. Mỗi khối là lá chứa đợc 3 mẫu tin.
B1
B2 B3 B4
B5 B6 B7 B8 B9 B10 B11
T×m kiÕm:
Giả sử chúng ta cần tìm mẫu tin r có khoá v cho trớc. Chúng ta cần phải tìm đờng đi từ gốc của B-cây tới lá, sao cho lá này cần phải chứa mẫu tin r nếu nó cã trong file .
Trong quá trình tìm kiếm, giả sử tại một thời điểm nào đó ta đạt tới đỉnh B.
Nếu khối B là lá, ta tìm trong khối B xem nó có chứa mẫu tin r hay không. Các mẫu tin sắp xếp theo thứ tự tăng dần của khoá, do đó sự tìm kiếm trong khối B có thể tiến hành bằng kỹ thuật tìm kiếm tuần tự hoặc tìm kiếm nhị phân.
21 143
9 58 92 195
3 5 9 15 21 36 49 58 92 121 143 169 195 211 232
Nếu B là đỉnh trong chứa (p0, v1, p1, v2, p2, ..., vm, pm) thì ta cần xác định vị trí của giá trị khoá v trong dãy khoá v1,v2, ...,vm. Nếu v < v1 thì ta đi xuống đỉnh
đợc trỏ bởi p0. Nếu vi ≤ v < vi+1 thì ta đi xuống đỉnh đợc trỏ bởi pi (i = 1, 2, ..., m - 1). Còn nếu vn < v thì ta đi xuống đỉnh đợc trỏ bởi pn.
Bổ sung:
Giả sử ta cần bổ sung vào B-cây một mẫu tin r với khoá là v. Đầu tiên ta áp dụng thủ tục tìm kiếm để tìm ra khối B cần phải bổ sung mẫu tin r vào đó.
Nếu khối B còn đủ chỗ cho mẫu tin r thì ta xếp mẫu tin r vào khối B sao cho thứ tự tăng dần của khoá đợc bảo tồn. Chú ý rằng, r không thể là mẫu tin đầu tiên của khối B, trừ khi B là lá ngoài cùng bên trái. Nếu B là lá ngoài cùng bên trái thì giá trị nhỏ nhất của khối B không có mặt trong các đỉnh là tiền thân của B. Vì vậy trong trờng hợp này chỉ cần thêm mẫu tin r vào khối B là xong, không cần sửa đổi gì với các đỉnh là tiền thân của khối B.
Nếu B không còn đủ không gian để lu giữ mẫu tin r thì ta thêm vào B-cây một lá mới, khối B’. chuyển một nửa số mẫu tin ở cuối của khối B sang khối B’. Sau đó xếp mẫu tin r vào khối B hoặc khối B’ sao cho vẫn đảm bảo đợc tính tăng dần của các giá trị khoá. Giả sử Q là cha của B, ta có thể biết đợc Q nếu trong quá trình tìm kiếm, ta lu lại vết của đờng đi từ gốc tới B. Giả sử chỉ số của khối B’ là (v’, p’), trong đó v’ là khoá nhỏ nhất trong B’, còn p’ là địa chi của khối B’. áp dụng thủ tục trên để bổ sung (v’, p’) vào khối Q. Nếu khối Q không còn đủ chỗ cho (v’, p’) thì ta lại phải thêm vào B-cây một đỉnh mới Q’, nó là em liền kề của Q. Sau đó lại tìm đến cha của đỉnh Q để đa vào chỉ số của khối mới Q’. Quá trình có thể đợc tiếp diễn và dẫn đến việc phải phân đôi số giá trị khoá ở gốc, nửa sau
đợc chuyển vào khối mới. Trong trờng hợp này, ta phải tạo ra một gốc mới có
đúng hai con, một con là gốc cũ, một con là đỉnh mới đa vào.
Ví dụ: Giả sử với cấu trúc lu trữ ở ví dụ 3.4, ta cần bổ sung mẫu tin có khoá 32. Trớc hết ta phải tìm khối cần phải đa mẫu tin này vào. Bắt đầu từ gốc B1, vì 21 < 32 < 143, ta đi xuống B3. Tại B3, 32 < 58, ta đi xuống B7, B7 là lá, vậy cần phải đa mẫu tin với khoá 32 vào B7. Nhng khối B7 đã đầy. Ta thêm vào khối mới B12 và xếp các mẫu tin với khoá 21, 32 vào khối B7, xếp các mẫu tin với khoá
36, 49 vào khối B12. Chỉ số của khối B12chứa giá trị khoá 36. Cần phải xếp chỉ số B12 vào cha của B7 là B3. Nhng B3 cũng đầy. Thêm vào khối mới B13. Sau đó các chỉ số của các khối B7, B12 đợc xếp vào B3 còn các chỉ số của các khối B8, B9 đợc xếp vào B13. Bây giờ chỉ số của khối B13 là 58 và địa chỉ của khối B13 cần đợc xếp vào khối B1. Nhng B1 cũng đầy thêm vào B-cây khối mới B14. Xếp các chỉ số của B2, B3 vào B1, các chỉ số của B13, B4 vào B14. Vì B1 là gốc, ta phải thêm vào gốc mới khối B15 và xếp các chỉ số của B1 và B14 vào B15. Kết quả ta có B-cây nh sau:
B15
B1 B14
B2 B3 B13 B4
B5 B6 B7 B12 B8 B9 B10 B11 Loại bỏ:
58
21 143
195
3 5
143 169 195 211 232
92
9 36
9 15 21 32 36 49 58 92 121
Giả sử ta cần loại khỏi B-cây mẫu tin r với khoá v. Đầu tiên áp dụng thủ tục tìm kiếm để tìm ra lá B chứa mẫu tin r. Sau đó loại mẫu tin r trong khối B.
Giả sử sau khi loại bỏ B không rỗng. Trong trờng hợp này, nếu r không phải là mẫu tin đầu tiên trong B, ta không phải làm gì thêm. Nếu r là mẫu tin đầu tiên trong B thì sau khi xoá r, chỉ số của B đã thay đổi. Do đó ta cần tìm đến đỉnh Q là cha của B. Nếu là con trởng của Q thì giá trị khoá v’ trong chỉ số (v’, p’) của B không có trong Q. Trong trờng hợp này ta cần tìm đến tiền thân A của B sao cho A không phải là con trởng của cha mình A’. Khi đó giá trị khoá nhỏ nhất trong B đợc chứa trong A’. Do đó trong A’, ta cần thay giá trị khoá cũ v bởi giá
trị mới v’.
Giả sử sau khi loại bỏ mẫu tin r, B trở thành rỗng. Loại bỏ lá B khỏi B-cây.
Điều đó dẫn đến cần loại bỏ chỉ số của B trong đỉnh cha Q của B.
Nếu sau khi loại bỏ, số các con của đỉnh Q ít hơn [n/2] thì ta tìm đến đỉnh Q’ là anh em liền kề của đỉnh Q. Nếu Q’ có nhiều hơn [n/2] con thì ta phân phối lại các giá trị khoá trong Q và Q’ sao cho cả hai có ít nhất [n/2] con . khi đó các chỉ số của Q hoặc Q’ có thể thay đổi. Ta lại phải tìm đến các tiền thân của Q để phản ánh sự thay đổi này.
Nếu Q’ có đúng [n/2] con, thì ta kết hợp hai đỉnh Q và Q’ thành một đỉnh.
Một trong hai đỉnh bị loại khỏi cây. Các khoá chứa trong đỉnh này đợc chuyển sang đỉnh còn lại. Điều này dẫn đến cần loại bỏ chỉ số của đỉnh bị loại ra khỏi cha của Q. Sự loại bỏ này đợc thực hiện bằng cách áp dụng thủ tục loại bỏ đã
trình bày.
Quá trình loại bỏ có thể dẫn đến việc loại bỏ gốc cây, khi chúng ta cần kết hợp hai con của gốc thành một đỉnh, đỉnh này trở thành gốc mới của B-cây.
Ví dụ: Giả sử chúng ta cần loại mẫu tin với khoá 58 khỏi B-cây trong hình trên. Đầu tiên tìm lá chứa khoá 58. Đó là khối B8. Xoá mẫu tin 58, khối B8 thành
con. Số con của B13 ít hơn [n/2] (ở đây [n/2] = [3/2] = 2). Tìm đến em liền kề của B13 là B4, số con của B4 là hai. Kết hợp hai đỉnh này thành một đỉnh B13. Cần phải loại bỏ chỉ số của khối B4 khỏi B14, B14 trở thành chỉ có một con. Tìm đến anh liền kề của B14 là B1. Số con của B1 là hai. Kết hợp B1 và B14 thành một đỉnh B1, B1 trở thành gốc mới của B-cây.
B1
B2 B3 B4
B5 B6 B7 B8 B9 B10 B11