23.2.2004 Ch. 4: B-Trees 1
B-Cây
23.2.2004 Ch. 4: B-Trees 2
C u trúc d li u trong b nh ngoàiấ ữ ệ ộ ớ
°B-cây t ng quát hoá cây tìm ki m nh phân.ổ ế ị
–“H s phân nhánh” (branching factor)ệ ố
°B-cây là cây tìm ki m cân b ng đc thi t k đ làm vi c h u hi u ế ằ ượ ế ế ể ệ ữ ệ
trong b nh ngoài (đĩa c ng).ộ ớ ứ
–B nh chính (main memory)ộ ớ
–B nh ngoài (secondary storage)ộ ớ
°Disk
–Track
–Page
°Th i gian ch y g mờ ạ ồ
–s các truy c p vào đĩaố ậ
–th i gian CPUờ
23.2.2004 Ch. 4: B-Trees 3
Truy c p đĩaậ
°M t nút c a B-cây th ng chi m nguyên c m t disk page.ộ ủ ườ ế ả ộ
°H s phân nhánh tùy thu c vào t l gi a kích th c c a khóa và ệ ố ộ ỉ ệ ữ ướ ủ
kích th c c a disk page.ướ ủ
23.2.2004 Ch. 4: B-Trees 4
Các thao tác lên m t đĩaộ
°Cho x là m t con tr đn m t đi t ng (ví d : m t nút c a m t B-ộ ỏ ế ộ ố ượ ụ ộ ủ ộ
cây). Đi t ng ố ượ x có th có nhi u tr ngể ề ườ
–N u ếx n m trong b nh chính, truy c p các tr ng c a ằ ộ ớ ậ ườ ủ x nh ư
th ng l , ví d nh ườ ệ ụ ư key[x], leaf [x],...
–N u ếx còn n m trên đĩa thì dùng DằISK-READ(x) đ đc nó vào b ể ọ ộ
nh chính.ớ
–N u ếx đã thay đi thì dùng DổISK-WRITE(x) đ tr nó vào đĩa.ể ữ
°Cách làm vi c tiêu bi u v i m t đi t ng ệ ể ớ ộ ố ượ x
...
x m t con tr đn m t đi t ng nào đóộ ỏ ế ộ ố ượ
DISK-READ(x)
các thao tác truy c p/thay đi các tr ng c a ậ ổ ườ ủ x
DISK-WRITE(x)
các thao tác không thay đi m t tr ng c a ổ ộ ườ ủ x
...
23.2.2004 Ch. 4: B-Trees 5
H s phân nhánhệ ố
°Ví d m t B-cây mà:ụ ộ
–m i nút có 1000 khóa (s trong m i nút là s khóa nó ch a), t c ỗ ố ỗ ố ứ ứ
là B-cây có h s phân nhánh là 1001ệ ố
1000
1000 1000 1000
10001000 1000
1001
1001
10011001
1 nút
1000 khóa
1001 nút
1.001.000 khóa
1.002.001 nút
1.002.001.000 khóa
root[T]