Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 có nội dung trình bày về định nghĩa của B-cây, chiều cao của một B-cây, cấu trúc dữ liệu trong bộ nhớ ngoài, truy cập đĩa, các thao tác trên đĩa, hệ số phân nhánh,... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 B-Caây22.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 CPU22.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] 1000 khoùa 1 nuùt 1000 khoùa 1001 nhaùnh 1001 nuùt 1000 1000 1000 1.001.000 khoùa 1001 1001 1001 1.002.001 nuùt 1000 1000 1000 1.002.001.000 khoùa22.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 x  N W  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 x  N W  ci [x] ki22.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 ...