Bài giảng Phân tích thiết kế giải thuật - Chương 4: B-Cây

 leaf [ y ] 
 3	 n [ z ]  t  1 
 4	 for j  1 to t  1 
 5	 do key j [ z ]  key j + t [ y ] 
 6	 if not leaf [ y ] 
 7	 then for j  1 to t 
 8	 do c j [ z ]  c j + t [ y ] 
 9	 n [ y ]  t  1 
 N W  
 P Q R S T U V 
x 
key i [ x ] 
y = c i [ x ] 
key i - 1 [ x ] 
22.9.2004 
19 
Ch. 4: B-Trees 
Tách một nút của một B-cây 
(tiếp) 
10	 for j  n [ x ]  1 downto i  1 
11	 do c j +1 [ x ]  c j [ x ] 
12	 c i +1 [ x ]  z 
13	 for j  n [ x ] downto i 
14	 do key j +1 [ x ]  key j [ x ] 
15	 key i [ x ]  key t [ y ] 
16	 n [ x ]  n [ x ]  1 
17	D ISK -W RITE ( y ) 
18 	D ISK -W RITE ( z ) 
19	D ISK -W RITE ( x ) 
22.9.2004 
20 
Ch. 4: B-Trees 
Tách một nút của một B-cây 
(tiếp) 
B-T REE -S PLIT -C HILD cần 
 ( t ) thời gian CPU (các dòng 4-5 và 7-8) 
O (1) disk operations (các dòng 17-19). 
22.9.2004 
21 
Ch. 4: B-Trees 
Chèn một khóa vào trong một B-cây 
Thủ tục B-T REE -I NSERT để chèn một khóa k vào một B-cây T . 
Thủ tục gọi B-T REE -S PLIT -C HILD để đảm bảo khi gọi đệ quy thì sẽ không bao giờ xuống một nút đã đầy. 
B-T REE -I NSERT ( T , k ) 
 1	 r  root [ T ] 
 2	 if n [ r ] = 2 t  1 
 3	 then s  A LLOCATE -N ODE () 
 4	 root [ T ]  s 
 5	 leaf [ s ]  FALSE 
 6	 n [ s ]  0 
 7	 c 1 [ s ]  r 
 8	 B-T REE -S PLIT -C HILD ( s , 1, r ) 
 9	 B-T REE -I NSERT -N ONFULL ( s , k ) 
10	 else B-T REE -I NSERT -N ONFULL ( r , k ) 
22.9.2004 
22 
Ch. 4: B-Trees 
Tách một nút gốc đầy 
Ví dụ: tách một nút gốc đầy của một B-cây mà bậc tối thiểu là t = 4. 
Nút gốc mới là s . Nút gốc cũ r được tách thành hai nút con của s . 
Chiều cao của một B-cây tăng thêm 1 mỗi khi nút gốc được tách. 
 A D F H L N P 
T 8 
T 1 
T 2 
T 7 
T 6 
T 5 
T 4 
T 3 
H 
 A D F 
 L N P 
T 1 
T 2 
T 4 
T 3 
T 5 
T 6 
T 8 
T 7 
root [ T ] 
root [ T ] 
r 
r 
s 
22.9.2004 
23 
Ch. 4: B-Trees 
Chèn một khóa vào một nút không đầy 
Thủ tục để chèn một khóa vào một nút không đầy 
B-T REE -I NSERT -N ONFULL ( x , k ) 
1	 i  n [ x ] 
2	 if leaf [ x ] 
3	 then while i  1 and k  key i [ x ] 
4	 do key i+ 1 [ x ]  key i [ x ] 
5	 i  i  1 
6	 key i+ 1 [ x ]  k 
7	 n [ x ]  n [ x ]  1 
8	 D ISK -W RITE ( x ) 
 N W  
x 
key i + 1 [ x ] 
key i [ x ] 
nút lá 
22.9.2004 
24 
Ch. 4: B-Trees 
Chèn một khóa vào một nút không đầy 
(tiếp) 
 9	 else while i  1 and k  key i [ x ] 
10 do i  i  1 
11 i  i  1 
12	 D ISK -R EAD ( c i [ x ]) 
13	 if n [ c i [ x ]] = 2 t  1 
14	 then B-T REE -S PLIT -C HILD ( x , i , c i [ x ]) 
15	 if k  key i [ x ] 
16	 then i  i  1 
17	 B-T REE -I NSERT -N ONFULL ( c i [ x ], k ) 
 N W  
 P Q R S T 
x 
y = c i [ x ] 
22.9.2004 
25 
Ch. 4: B-Trees 
Phân tích chèn một khóa vào trong một B-cây 
Thủ tục B-T REE -I NSERT cần 
số truy cập đĩa là O ( h ) vì số lần gọi D ISK -R EAD và D ISK -W RITE giữa các gọi B-T REE -I NSERT -N ONFULL là O (1). 
thời gian CPU là O ( t h ) = O( t log t n ) 
22.9.2004 
26 
Ch. 4: B-Trees 
Cho một B-cây với bậc tối thiểu t = 3 
Cây lúc đầu 
Đã chèn B vào 
Ví dụ cho các trường hợp khi chèn một khóa vào một B-cây 
G M P X 
A C D E 
J K 
N O 
R S T U V 
Y Z 
G M P X 
A B C D E 
J K 
N O 
R S T U V 
Y Z 
22.9.2004 
27 
Ch. 4: B-Trees 
Ví dụ cho các trường hợp khi chèn một khóa vào một B-cây 
G M P X 
A B C D E 
J K 
N O 
R S T U V 
Y Z 
G M P T X 
A B C D E 
J K 
N O 
R S 
Y Z 
U V 
G M P T X 
A B C D E 
J K 
N O 
Y Z 
Q R S 
U V 
Đã chèn Q vào cây: 
(tiếp) 
Chèn Q vào cây 
22.9.2004 
28 
Ch. 4: B-Trees 
Ví dụ cho các trường hợp khi chèn một khóa vào một B-cây 
(tiếp) 
Chèn L vào cây 
G M P T X 
A B C D E 
J K 
N O 
Y Z 
Q R S 
U V 
T X 
G M 
A B C D E 
J K L 
N O 
Y Z 
Q R S 
U V 
P 
T X 
G M 
A B C D E 
N O 
Y Z 
Q R S 
U V 
P 
J K 
 Đã chèn L vào cây: 
22.9.2004 
29 
Ch. 4: B-Trees 
Ví dụ cho các trường hợp khi chèn một khóa vào một B-cây 
(tiếp) 
Chèn F vào cây 
T X 
G M 
A B C D E 
J K L 
N O 
Y Z 
Q R S 
U V 
P 
T X 
C G M 
J K L 
N O 
Y Z 
Q R S 
U V 
P 
A B 
D E F 
T X 
C G M 
J K L 
N O 
Y Z 
Q R S 
U V 
P 
A B 
D E 
 Đã chèn F vào cây: 
22.9.2004 
30 
Ch. 4: B-Trees 
Xóa một khóa khỏi một B-cây 
Thủ tục B-T REE -D ELETE ( 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-T REE -D ELETE đượ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 đó đô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 đó. 
22.9.2004 
31 
Ch. 4: B-Trees 
Xóa một khóa khỏi một B-cây 
B-T REE -D ELETE ( 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. 
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’ bằng cách gọi đệ quy B-T REE -D ELETE ( y , k’ ), thay k bằng k’ trong x . 
 k  
 k’ 
x 
y 
22.9.2004 
32 
Ch. 4: B-Trees 
Xóa một khóa khỏi một B-cây 
B-T REE -D ELETE ( 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’ bằng cách gọi đệ quy B-T REE -D ELETE ( z , k’ ), thay k bằng k’ trong x . 
 k  
k’  
x 
z 
22.9.2004 
33 
Ch. 4: B-Trees 
Xóa một khóa khỏi một B-cây 
B-T REE -D ELETE ( 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 2 t  1 khóa. Giải phóng (free) z và gọi đệ quy B-T REE -D ELETE ( y , k ) để xóa k khỏi cây có gốc y . 
 k  
 k’ 
x 
y 
l’  
z 
22.9.2004 
34 
Ch. 4: B-Trees 
Xóa một khóa khỏi một B-cây 
(tiếp) 
  
 k’ k l’  
x 
y 
z 
22.9.2004 
35 
Ch. 4: B-Trees 
Xóa một khóa khỏi một B-cây 
B-T REE -D ELETE ( 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 ta sẽ xuống đến một nút chứa ít nhất t khóa. Xong rồi gọi B-T REE -D ELETE lên nút con thích hợp của x . 
22.9.2004 
36 
Ch. 4: B-Trees 
Xó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 với ít nhất t khóa, thì cho 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 ngay bên trái hay ngay bên phải của c i [ x ] lên x , và đem con trỏ tương ứng từ nút anh em vào c i [ x ] . 
 m  
 l 
x 
c i [ x ] 
n n’  
22.9.2004 
37 
Ch. 4: B-Trees 
Xóa một khóa khỏi một B-cây 
(tiếp) 
 n  
 l m 
x 
c i [ x ] 
n’  
22.9.2004 
38 
Ch. 4: B-Trees 
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 
22.9.2004 
39 
Ch. 4: B-Trees 
Xóa một khóa khỏi một B-cây 
(tiếp) 
 l’  
x 
n  
 h l m  m’ 
22.9.2004 
40 
Ch. 4: B-Trees 
Xóa một khóa khỏi một B-cây 
(tiếp) 
Thủ tục B-T REE -D ELETE cần 
 số truy cập lên đĩa là O ( h ) vì có O (1) lần gọi D ISK -R EAD và 
 D ISK -W RITE 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 ). 
22.9.2004 
41 
Ch. 4: B-Trees 
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 X 
C G M 
J K L 
N O 
Y Z 
Q R S 
U V 
P 
A B 
D E F 
T X 
C G M 
J K L 
N O 
Y Z 
Q R S 
U V 
P 
A B 
D E 
 F đã được xóa: trường hợp 1 
22.9.2004 
42 
Ch. 4: B-Trees 
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 X 
C G M 
J K 
N O 
Y Z 
Q R S 
U V 
P 
A B 
D E 
T X 
C G M 
J K L 
N O 
Y Z 
Q R S 
U V 
P 
A B 
D E 
T X 
C G L 
J K 
N O 
Y Z 
Q R S 
U V 
P 
A B 
D E 
 M đã được xóa: 
22.9.2004 
43 
Ch. 4: B-Trees 
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 
C L 
N O 
Y Z 
Q R S 
U V 
P 
A B 
D E G J K 
T X 
C G L 
J K 
N O 
Y Z 
Q R S 
U V 
P 
A B 
D E 
T X 
C L 
N O 
Y Z 
Q R S 
U V 
P 
A B 
D E J K 
 G đã được xóa: 
22.9.2004 
44 
Ch. 4: B-Trees 
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 X 
C L 
N O 
Y Z 
Q R S 
U V 
P 
A B 
D E J K 
C L P T X 
N O 
Y Z 
Q R S 
U V 
A B 
D E J K 
C L P T X 
N O 
Y Z 
Q R S 
U V 
A B 
E J K 
 D đã được xóa: 
22.9.2004 
45 
Ch. 4: B-Trees 
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 Z 
Q R S 
U V 
A B 
E J K 
E L P T X 
N O 
Y Z 
Q R S 
U V 
A B C 
J K 
E L P T X 
N O 
Y Z 
Q R S 
U V 
A C 
J K 
 B đã được xóa khỏi cây: 
22.9.2004 
46 
Ch. 4: B-Trees