22.9.2004 Ch. 4: B-Trees 1
B-Caây
22.9.2004 Ch. 4: B-Trees 2
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 3
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 4
Caùc thao taùc leân moät ñóa
°Cho xlaø 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 xcoù theå coù nhieàu tröôøng
–Neáu xnaèm trong boä nhôù chính, truy caäp caùc tröôøng cuûa xnhö
thöôøng leä, ví duï nhö key[x], leaf [x],...
–Neáu xcoø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
...
xmoä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 5
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
1000 khoùa
1000 1000 1000
10001000 1000
1001 nhaùnh
1001
10011001
1 nuùt
1000 khoùa
1001 nuùt
1.001.000 khoùa
1.002.001 nuùt
1.002.001.000 khoùa
root[T]