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! | B-Caây 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 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. 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 . 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 khoùa 1001 1001 1001 nuùt 1000 1000 1000 khoùa 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 .