Bài giảng B-Tree

1B-Tree Xóa một khóa khỏi một B-cây Thủ tục B-TREE-DELETE(x, k) để xóa khóa k khỏi cây con có gốc tại x bảo đảm rằng khi B-TREE-DELETE được gọi đệ quy lên x thì — số khóa trong x phải  t (bậc tối thiểu của cây). Do đó, khi thủ tục thực thi, đôi khi một khóa được di chuyển (từ một nút thích hợp khác) vào một nút trước khi đệ quy xuống nút đó. 2 3Xóa một khóa khỏi một B-cây B-TREE-DELETE(x, k) 1. Nếu khóa k có trong nút x và x là một nút lá thì xóa k khỏi x, rồi tái cân bằng (phần sau). 2. Nếu khóa k có trong nút x và x là một nút trong thì a. Nếu nút con y ở trước k có ít nhất t khóa thì tìm khóa trước (predecessor) k’ của k trong cây con có gốc tại y. Xóa k’, trong nút x thay k bằng k’. (Tìm và xóa k’ có thể thực thi trong một lượt đi xuống duy nhất.)  k  x y cây con có gốc tại y 4Xóa một khóa khỏi một B-cây B-TREE-DELETE(x, k) 1. ... 2. Nếu khóa k có trong nút x và x là một nút trong thì a. ... b. Tương tự, nếu nút con z ở sau k có ít nhất t khóa thì tìm khóa sau (successor) k’ của k trong cây con có gốc tại z. Xóa k’, trong x thay k bằng k’. (Tìm và xóa k’ có thể thực thi trong một lượt đi xuống duy nhất.)  k  x z cây con có gốc tại z 5Xóa một khóa khỏi một B-cây B-TREE-DELETE(x, k) 1. ... 2. Nếu khóa k có trong nút x và x là một nút trong thì a. ... b. ... c. Nếu không, cả y lẩn z đều chỉ có t  1 khóa, hợp nhất k và nguyên cả z vào y, thành ra x mất k và con trỏ đến z , và bây giờ y chứa 2t  1 khóa. Giải phóng (free) z và gọi đệ quy B-TREE-DELETE(y, k) để xóa k khỏi cây con có gốc y.  k   k’ x y l’ z 6Xóa một khóa khỏi một B-cây (tiếp) Minh họa bước hợp nhất    k’ k l’  x y z  k   k’ x y l’ z 7Xóa một khóa khỏi một B-cây B-TREE-DELETE(x, k) 1. ... 2. ... 3. Nếu khóa k không có trong nút trong x thì xác định gốc c i [x] của cây con chứa k, nếu k có trong cây. Nếu c i [x] chỉ có t  1 khóa, thực thi bước 3a hay 3b nếu cần (để đảm bảo rằng giải thuật, khi được gọi đệ quy, sẽ xuống một nút chứa ít nhất t khóa). Xong rồi gọi B-TREE- DELETE lên nút con thích hợp của x. 8Xóa một khóa khỏi một B-cây (tiếp) 3. ... a. Nếu c i [x] chỉ có t  1 khóa, nhưng lại có một nút anh em bên phải (hay bên trái) với ít nhất t khóa, thì cho nút c i [x] thêm một khóa bằng cách đem một khóa từ x xuống c i [x], đem một khóa từ nút anh em của c i [x] lên x, và đem con trỏ tương ứng từ nút anh em vào nút c i [x].  m   l x c i [x] n n’  nút anh em bên phải 9Xóa một khóa khỏi một B-cây (tiếp) Minh họa  n   l m x c i [x] n’   m   l x c i [x] n n’  10 Xóa một khóa khỏi một B-cây (tiếp) 3. ... a. ... b. Nếu c i [x] và mọi nút anh em của nó chỉ có t  1 khóa, thì hợp nhất c i [x] và một nút anh em bằng cách đem một khóa từ x xuống nút mới tạo, khóa này sẽ là khóa giữa của nút.  l l’ x c i [x] m  m’ n  h 11 Xóa một khóa khỏi một B-cây (tiếp) Minh họa  l’ x n  h l m  m’  l l’ x c i [x] m  m’ n  h 12 Xóa một khóa khỏi một B-cây (tiếp) Thủ tục B-TREE-DELETE cần — số truy cập lên đĩa là O(h) vì có O(1) lần gọi DISK-READ và DISK-WRITE giữa các gọi đệ quy của thủ tục. — thời gian CPU của thủ tục là O(t h) = O(t log t n). 13 Ví dụ cho các trường hợp khi xóa một khóa khỏi một B-cây Cho một B-cây có bậc tối thiểu t = 3 ° Cây lúc đầu, xóa F khỏi cây T XC G M J K L N O Y ZQ R S U V P A B D E T XC G M J K L N O Y ZQ R S U V P A B D E - F đã được xóa: trường hợp 1 F 14 Ví dụ cho các trường hợp khi xóa một khóa khỏi một B-cây ° Xóa M khỏi cây: trường hợp 2a T XC G M J K N O Y ZQ R S U V P A B D E T XC G L J K N O Y ZQ R S U V P A B D E - M đã được xóa: L 15 C L Ví dụ cho các trường hợp khi xóa một khóa khỏi một B-cây ° Xóa G khỏi cây: trường hợp 2c T X N O Y ZQ R S U V P A B T XC L N O Y ZQ R S U V P A B D E J K - G đã được xóa: J KD E G D E G J 16 Ví dụ cho các trường hợp khi xóa một khóa khỏi một B-cây ° Xóa D khỏi cây: trường hợp 3b T XC L N O Y ZQ R S U V P A B D E J K C L P T X N O Y ZQ R S U VA B D E J K C L P T X N O Y ZQ R S U VA B E J K - D đã được xóa: 17 Ví dụ cho các trường hợp khi xóa một khóa khỏi một B-cây ° Xóa B khỏi cây: trường hợp 3a C L P T X N O Y ZQ R S U VA B E J K E L P T X N O Y ZQ R S U VA B C J K E L P T X N O Y ZQ R S U VA C J K - B đã được xóa khỏi cây: