Bài giảng Cấu trúc dữ liệu: Chương 5 B-Tree, cung cấp cho người học những kiến thức như: B-Cây; Thêm phần tử vào B-Cây; Xóa phần tử khỏi B-Cây. Mời các bạn cùng tham khảo! | 11 07 2020 11 07 2020 1 1 B-Cây Thêm phần tử vào B-Cây Xóa phần tử khỏi B-Cây 11 07 2020 2 2 1 11 07 2020 Giới thiệu B-cây B-Trees xử lý tốt trên đĩa hoặc các thiết bị lưu trữ ngoài 11 07 2020 3 3 B-Cây Mỗi node có thể chứa n khóa các khóa này sắp xếp theo thứ tự tăng dần Mỗi node trong có n 1 con trỏ trỏ tới các node con Node lá không có node con và có cùng mức 22 32 24 28 37 4242 9 12 17 20 11 07 2020 4 4 2 11 07 2020 B-Cây Một B-Cây bậc t t 2 Mỗi node trừ node gốc có tối thiểu t khóa và có tối thiểu t con Mỗi node có tối đa 2t khóa vì vậy một node trong có tối đa 2t 1 con Một node gọi là đầy khi chứa 2t khóa Ví dụ B-tree đơn giản nhất có t 2 mỗi node trong có hoặc 3 4 5 con 11 07 2020 5 5 Thêm phần tử Thao tác thêm phần tử Insert thêm 1 khóa x vào cây Thêm v vào 1 nút lá Nếu nút lá đầy tách nút lá ra làm đôi và chuyển phần tử giữa lên nút cha 11 07 2020 6 6 3 11 07 2020 Thêm phần tử Thêm các phần tử sau vào B-cây bậc t 2 22 42 12 32 17 37 9 28 20 24 7 44 15 48 29 10 34 40 26 47 27 Thêm 22 22 Thêm 42 22 42 Thêm 12 12 22 42 Thêm 12 12 22 32 42 11 07 2020 7 7 Thêm phần tử 22 42 12 32 17 37 9 28 20 24 7 44 15 48 29 1012 34 40 26 47 27 22 32 42 Thêm 12 Thêm 17 thì trang này bị đầy một trang B-cây cấp 2 chứa tối đa bốn phần tử . Dãy các khóa là 12 17 22 32 42 nên trang này bị tách ra thành hai trang Một trang chứa khóa 12 17 và một trang chứa khóa 32 42 và cấp phát thêm trang mới chứ khóa 22 trang cha . 11 07 2020 8 8 4 11 07 2020 Thêm phần tử 22 42 12 32 17 37 9 28 20 24 7 44 15 48 29 10 34 40 26 47 27 Thêm 17 12 1212 17 1722 2237 32 3242 42 42 11 07 2020 9 9 Thêm phần tử 22 42 12 32 17 37 9 28 20 24 7 44 1 5 48 29 10 34 40 26 47 27 Thêm 37 9 28 20 24 22 32 3237 4242 12 17 Phạm 37 9 28 20 24 11 07 2020 10 10 5 11 07 2020 Thêm phần tử 22 42 12 32 17 37 9 28 20 24 7 44 15 48 29 10 34 40 26 47 27 Kết quả thêm 24 22 32 24 28 37 4242 9 12 17 20 11 07 2020 11 11 Thêm phần tử 22 42 12 32 17 37 9 28 20 24 7 44 15 48 29 10 34 40 26 47 27 Thêm 7 - gt Phạm 22 32 24 28 37 4242
