Bài giảng Giải thuật - Chương 4: B - Cây
B-Caây
22.9.2004
Ch. 4: B-Trees
1
Caáu truùc döõ lieäu trong boä nhôù ngoaøi
° B-caây toång quaùt hoaù caây tìm kieám nhò phaân.
– “Heä soá phaân nhaùnh” (branching factor)
° B-caây laø caây tìm kieám caân baèng ñöôïc thieát keá ñeå laøm vieäc höõu hieäu
trong boä nhôù ngoaøi (ñóa cöùng).
– Boä nhôù chính (main memory)
– Boä nhôù ngoaøi (secondary storage)
°
Disk
– Track
– Page
° Thôøi gian chaïy goàm
– soá caùc truy caäp vaøo ñóa
– thôøi gian CPU
22.9.2004
Ch. 4: B-Trees
2
Truy caäp ñóa
° Moät nuùt cuûa B-caây thöôøng chieám nguyeân caû moät disk page.
° Heä soá phaân nhaùnh tuøy thuoäc vaøo tæ leä giöõa kích thöôùc cuûa khoùa vaø
kích thöôùc cuûa disk page.
22.9.2004
Ch. 4: B-Trees
3
Caùc thao taùc leân moät ñóa
° Cho x laø moät con troû ñeán moät ñoái töôïng (ví duï: moät nuùt cuûa moät B-
caây). Ñoái töôïng x coù theå coù nhieàu tröôøng
– Neáu x naèm trong boä nhôù chính, truy caäp caùc tröôøng cuûa x nhö
thöôøng leä, ví duï nhö key[x], leaf [x],...
– Neáu x coøn naèm treân ñóa thì duøng DISK-READ(x) ñeå ñoïc noù vaøo
boä nhôù chính.
– Neáu x ñaõ thay ñoåi thì duøng DISK-WRITE(x) ñeå tröõ noù vaøo ñóa.
° Caùch laøm vieäc tieâu bieåu vôùi moät ñoái töôïng x
...
x moät con troû ñeán moät ñoái töôïng naøo ñoù
DISK-READ(x)
caùc thao taùc truy caäp/thay ñoåi caùc tröôøng cuûa x
DISK-WRITE(x)
caùc thao taùc khoâng thay ñoåi moät tröôøng cuûa x
...
22.9.2004
Ch. 4: B-Trees
4
Heä soá phaân nhaùnh
° Ví duï moät B-caây maø:
– moãi nuùt coù 1000 khoùa, töùc laø B-caây coù heä soá phaân nhaùnh laø 1001
root[T]
1 nuùt
1000 khoùa
1000 khoùa
1001 nhaùnh
1001 nuùt
1000
1000
1000
1001
1.001.000 khoùa
1001
1001
1.002.001 nuùt
1000
1000
1000
1.002.001.000 khoùa
22.9.2004
Ch. 4: B-Trees
5
Ñònh nghóa cuûa B-caây
° Moät B-caây T laø moät caây coù goác, maø goác laø root[T], coù caùc tính chaát
sau
– Moãi nuùt x coù caùc tröôøng sau
°
n[x], soá löôïng khoùa ñang ñöôïc chöùa trong nuùt x
°
caùc khoùa: coù n[x] khoùa, ñöôïc xeáp theo thöù töï khoâng giaûm, töùc
laø
key1[x] key2[x] keyn[x ][x]
leaf [x], coù trò bool laø
°
TRUE neáu x laø moät laù
FALSE neáu x laø moät nuùt trong
– Moãi nuùt trong x chöùa n[x] + 1 con troû c1 [x], c2 [x],…, cn[x ]+1[x]
ñeán caùc nuùt con cuûa noù.
22.9.2004
Ch. 4: B-Trees
6
Ñònh nghóa cuûa B-caây
(tieáp)
Moâ hình moät nuùt cuûa B-caây
N W
x
ci [x]
22.9.2004
Ch. 4: B-Trees
7
Ñònh nghóa cuûa B-caây
(tieáp)
– Neáu ki laø khoùa tröõ trong caây con coù goác laø ci [x] thì
k1 key1[x] k2 key2[x] kn[x ] keyn[x ][x] kn[x ]+1
N W
x
ci [x]
ki
22.9.2004
Ch. 4: B-Trees
8
Ñònh nghóa cuûa B-caây
(tieáp)
– Taát caû caùc laù coù cuøng moät ñoä saâu, ñoù laø chieàu cao h cuûa caây
– Coù moät soá nguyeân t 2 goïi laø baäc toái thieåu cuûa caây sao cho
°
Moïi nuùt khoâng phaûi laø nuùt goác phaûi coù ít nhaát t − 1 khoùa.
Neáu caây thì nuùt goác phaûi coù ít nhaát moät khoùa.
°
Moåi nuùt coù theå chöùa toái ña 2t − 1 khoùa. Moät nuùt laø ñaày neáu
noù chöùa ñuùng 2t − 1 khoùa.
22.9.2004
Ch. 4: B-Trees
9
Chieàu cao cuûa moät B-caây
Ñònh lyù
Neáu n 1 thì moïi B-caây T vôùi n khoùa, chieàu cao h, vaø baäc toái thieåu t
2
n +1
h log
coù
t
2
Chöùng minh
Coù toái thieåu 2 nuùt ôû ñoä saâu 1, 2t nuùt ôû ñoä saâu 2,..., vaø 2t h − 1 nuùt ôû ñoä
h
saâu h. Vaäy soá khoùa toái thieåu laø
n 1+ (t −1) 2ti−1
i=1
th −1
t −1
=1+ 2(t −1)
= 2th −1
n +1
th
2
Do ñoù
, töø ñaây suy ra ñònh lyù.
22.9.2004
Ch. 4: B-Trees
10
Soá khoùa toái thieåu trong moät B-caây
° B-caây sao cho moïi nuùt ñeàu coù t − 1 khoùa, ngoaïi tröø nuùt goác chæ coù
1 khoùa.
—
Vaäy soá khoùa trong caây laø toái thieåu cho moïi caây coù baäc toái thieåu
laø t vaø chieàu cao laø h.
1 khoùa
ñoä saâu 0, soá nuùt: 1
t − 1 khoùa
t − 1
...
...
ñoä saâu 1, soá nuùt: 2
...
...
ñoä saâu 2, soá nuùt: 2t
t − 1
t − 1
t − 1
t − 1
...
...
...
...
...
...
...
...
t − 1
t − 1
t − 1
t − 1
t − 1
t − 1
t − 1
t − 1
ñoä saâu 3, soá nuùt: 2t2
22.9.2004
Ch. 4: B-Trees
11
Caùc thao taùc leân moät B-caây
° Caùc thao taùc leân moät B-caây:
– B-TREE-SEARCH
– B-TREE-CREATE
– B-TREE-INSERT
– B-TREE-DELETE
° Trong caùc thuû tuïc treân ta quy öôùc:
– Goác cuûa B-caây luoân luoân naèm trong boä nhôù chính.
– Baát kyø moät nuùt maø laø moät tham soá ñöôïc truyeàn ñi trong moät thuû
tuïc thì ñeàu ñaõ thöïc thi thao taùc DISK-READ leân noù.
22.9.2004
Ch. 4: B-Trees
12
Tìm trong moät B-caây
° Thuû tuïc ñeå tìm moät khoùa trong moät B-caây
– Input:
°
moät con troû chæ ñeán nuùt goác x cuûa moät caây con, vaø
moät khoùa k caàn tìm trong caây con.
°
– Output:
°
neáu k coù trong caây thì traû veà moät caëp (y, i) goàm moät nuùt y vaø
moät chæ soá i maø keyi [y] = k
°
neáu k khoâng coù trong caây thì traû veà NIL.
22.9.2004
Ch. 4: B-Trees
13
Tìm trong moät B-caây
(tieáp)
N W
x
B-TREE-SEARCH(x, k)
1
2
3
4
5
6
7
8
9
i 1
ci [x]
while i n[x] and k keyi [x]
do i i + 1
if i n[x] and k = keyi [x]
then return (x, i)
if leaf [x]
then return NIL
else DISK-READ(ci [x])
return B-TREE-SEARCH(ci [x], k)
22.9.2004
Ch. 4: B-Trees
14
Tìm trong moät B-caây
(tieáp)
° Caùc nuùt maø giaûi thuaät truy caäp taïo neân moät ñöôøng ñi töø goác xuoáng
ñeán nuùt coù chöùa khoùa (neáu coù).
Thôøi gian CPU ñeå xöû lyù moãi nuùt laø O(t).
° Do ñoù
– soá disk pages maø B-TREE-SEARCH truy caäp laø (h) = (log t n),
vôùi h laø chieàu cao cuûa caây, n laø soá khoaù cuûa caây.
– B-TREE-SEARCH caàn thôøi gian CPU O(t h) = O(t log t n).
22.9.2004
Ch. 4: B-Trees
15
Taïo moät B-caây troáng
° Thuû tuïc ñeå taïo moät nuùt goác troáng
– Goïi thuû tuïc ALLOCATE-NODE ñeå chieám moät disk page laøm moät
nuùt môùi.
B-TREE-CREATE(T )
1
2
3
4
5
x ALLOCATE-NODE()
leaf [x] TRUE
n[x] 0
DISK-WRITE(x)
root[T] x
– B-TREE-CREATE caàn O(1) thôøi gian CPU vaø O(1) disk
operations.
22.9.2004
Ch. 4: B-Trees
16
Cheøn moät khoùa vaøo moät B-caây
° Khi moät nuùt y laø ñaày (n[y] = 2t − 1), ñònh nghóa khoùa giöõa (median
key) cuûa y laø khoùa keyt [y].
° Ta seõ cheøn khoùa vaøo moät laù cuûa caây. Ñeå traùnh tröôøng hôïp cheøn
khoùa vaøo moät laù ñaõ ñaày, ta caàn moät thao taùc taùch (split) moät nuùt ñaày
y. Thao taùc naøy
– taùch nuùt ñaày y quanh nuùt giöõa cuûa noù thaønh hai nuùt, moãi nuùt coù
t − 1 khoùa
– di chuyeån nuùt giöõa leân nuùt cha cuûa y (phaûi laø nuùt khoâng ñaày)
vaøo moät vò trí thích hôïp.
° Ñeå cheøn khoùa maø chæ caàn moät löôït ñi töø nuùt goác ñeán moät laù, ta seõ
taùch moïi nuùt ñaày maø ta gaëp treân ñöôøng ñi töø goác ñeán nuùt laù.
– Phaûi ñaûm baûo ñöôïc raèng khi taùch moät nuùt ñaày y thì nuùt cha cuûa
noù phaûi laø khoâng ñaày.
22.9.2004
Ch. 4: B-Trees
17
Ví duï taùch moät nuùt ñaày
° Baäc toái thieåu t = 4. Vaäy soá khoùa toái ña cuûa moät nuùt laø 7.
° Taùch nuùt ñaày y laø con cuûa nuùt khoâng ñaày x.
x
N W
N
S
W
y = ci [x]
y = ci [x]
z = ci +1[x]
P Q R S T U V
P Q R
T U V
T1 T2 T3 T4 T5 T6 T7 T8
T1 T2 T3 T4
T5 T6 T7 T8
22.9.2004
Ch. 4: B-Trees
18
Taùch moät nuùt cuûa moät B-caây
° Thuû tuïc B-TREE-SPLIT-CHILD
– Input: moät nuùt trong khoâng ñaày x, moät chæ soá i maø nuùt y = ci [x]
laø moät nuùt ñaày
– Thuû tuïc taùch y thaønh hai nuùt vaø chænh x ñeå cho x coù theâm moät
nuùt con.
B-TREE-SPLIT-CHILD(x, i, y)
x
1
2
3
4
5
6
7
8
9
z ALLOCATE-NODE()
leaf [z] leaf [y]
n[z] t − 1
for j 1 to t − 1
do keyj [z] keyj + t [y]
if not leaf [y]
then for j 1 to t
do cj [z] cj + t [y]
n[y] t − 1
N W
y = ci [x]
P Q R S T U V
22.9.2004
Ch. 4: B-Trees
19
Taùch moät nuùt cuûa moät B-caây
(tieáp)
10
11
12
13
14
15
16
17
18
19
for j n[x] + 1 downto i + 1
do cj +1 [x] cj [x]
ci +1 [x] z
for j n[x] downto i
do keyj +1 [x] keyj [x]
keyi [x] keyt [y]
n[x] n[x] + 1
DISK-WRITE(y)
DISK-WRITE(z)
DISK-WRITE(x)
22.9.2004
Ch. 4: B-Trees
20
Tải về để xem bản đầy đủ
46 trang
16580
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Giải thuật - Chương 4: B - Cây", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_giai_thuat_chuong_4_b_cay.ppt
