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! | 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 .

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
5    437    2    29-03-2024
27    8    1    29-03-2024
153    77    4    29-03-2024
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.