Bài giảng "Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu nâng cao" cung cấp cho người đọc các kiến thức: Truy xuất dữ liệu trên bộ nhớ ngoài, m-way search tree, định nghĩa B-cây, lưu trữ B-cây trên bộ nhớ ngoài, khai báo cấu trúc B-cây, . Mời các bạn cùng tham khảo. | Các cấu trúc dữ liệu nâng cao Advanced Data Structures Cây nhị phân tìm kiếm cân bằng B-Cây Bảng băm Hash Table Winter 2017 151 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt B-Cây Đặt vấn đề Truy xuất dữ liệu trên bộ nhớ ngoài m-way search tree Định nghĩa B-cây Lưu trữ B-cây trên bộ nhớ ngoài Khai báo cấu trúc B-cây Các thao tác cơ bản B-cây Winter 2017 152 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt Đặt vấn đề Các ứng dụng database Cần lưu trữ dữ liệu lớn vd. 1 000 000 1 000 000 000 phần tử Lưu trữ trên bộ nhớ ngoài Tốc độ tìm kiếm nhanh Winter 2017 153 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt Truy xuất dữ liệu trên bộ nhớ ngoài 1 Bộ nhớ ngoài HDD DVD tape Đơn vị truy xuất tối thiểu Thời gian truy xuất Winter 2017 154 203 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt Truy xuất dữ liệu trên bộ nhớ ngoài 2 Thời gian để đọc ghi một block t thời gian dịch chuyển đầu đọc đến block thời gian đọc ghi block vào bộ nhớ Winter 2017 155 203 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt Truy xuất dữ liệu trên bộ nhớ ngoài 3 Vd 1. thời gian để đọc 2 block liên tiếp mỗi block 1KB t1 20ms 5ms 5ms 30ms Vd 2. thời gian để đọc 2 block xa nhau mỗi block 1KB t2 2 20ms 5ms 50ms Winter 2017 156 203 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt m-way Search Tree 1 Cây nhị phân với các phần tử được gom thành từng block trên đĩa Winter 2017 157 203 C Nguyen Tri Tuan - Truong DHQG-HCM https tailieudientucntt m-way Search Tree 2 Định nghĩa m-way search tree là cây thỏa Mỗi node có tối đa m cây con và m-1 khóa Các khóa trong mỗi node sắp tăng dần Các khóa trong cây con thứ i đều nhỏ hơn khóa i Các khóa trong cây con thứ i 1 đều lớn hơn khóa i
