Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu 2 B-Cây (B-Tree) - Nguyễn Tri Tuấn

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu 2 B-Cây (B-Tree) - Nguyễn Tri Tuấn

1. Cấutrúcdữliệu2 B-Cây(B-Tree) NguyễnTri Tuấn KhoaCNTT – ĐHKHTN –TP.HCM nttuan@fit.hcmuns.edu.vn Nộidung u Đặt vấn đề u Cây m-nhánh (m-way tree) u B-Cây (B-Tree) u Ứng dụng của B-Cây CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 2 1
2. Đặt vấn đề u Cần lưu trữ số phần tử dữ liệu rất lớn u Lưu trữ trên bộ nhớ ngoài u Tìm kiếm nhanh CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 3 Đặt vấn đề (tt) u Giải pháp: n Cây cân bằng n Phân trang dữ liệu u Tăng số nhánh của cây à giảm độ cao u Gom nhóm dữ liệu theo từng sector/block à giảm số lần truy xuất đĩa CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 4 2
3. [1] Cây m-nhánh (m-way tree) u Định nghĩa: cây m-nhánh là1 cây n Mỗi nút chứa từ 1 đến m-1 khóa cógiátrị phân biệt n Các khóa trong mỗi nút được sắp thứ tự (tăng dần) n Một nút cók khóa thìsẽcók+1 cây con, các cây con cóthể làrỗng n Cây con thứ i (0 <= i <= k) của nút chứa các khóa v thỏa: vi <= v <= vi+1 CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 5 [1] Cây m-nhánh (m-way tree) (tt) Cây 3-nhánh CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 6 3
4. [1] Cây m-nhánh (m-way tree) (tt) u Thao tác thêm phần tử (Insert): thêm 1 khóa v vào cây n Duyệt cây để tìm kiếm vị trícủa v cho đến khi gặp cây con rỗng n Thêm khóa v vào nút cha của cây con rỗng (nếu nút cha còn chỗ trống) n hoặc nếu nút cha không còn chỗ trống, tạo nút mới vàthêm khóa v vào nút đó CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 7 [1] Cây m-nhánh (m-way tree) (tt) Thêm khóa 8 vào cây (nút cha còn chỗ trống) CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 8 4
5. [1] Cây m-nhánh (m-way tree) (tt) Thêm khóa 27 vào cây (nút cha không còn chỗ trống) CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 9 [1] Cây m-nhánh (m-way tree) (tt) u Thao tác xóa phần tử (Delete): xóa 1 khóa v khỏi cây n Nếu v nằm giữa 2 cây con rỗng (v không có cây con) thìxóa v n Nếu v cócây con, thay thế v bằng: u phần tử lớn nhất trong cây con trái của v; u hoặc phần tử bénhất trong cây con phải của v CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 10 5
6. [1] Cây m-nhánh (m-way tree) (tt) Xóa khóa 8 (không cócây con) CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 11 [1] Cây m-nhánh (m-way tree) (tt) Xoákhóa 16 (cócây con) CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 12 6
7. [1] Cây m-nhánh (m-way tree) (tt) Xoákhóa 16 (cócây con) thay khóa 16 bằng khóa 6; thay khóa 6 bằng khóa 4 CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 13 [1] Cây m-nhánh (m-way tree) (tt) Xoákhóa 16 (cócây con) Delete khóa 4 (không cócây con) CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 14 7
8. [2] B-Cây (B-Tree) u Định nghĩa: B-cây là1 cây m-nhánh thỏa (m>2) n Nút gốc cóít nhất 1 khóa n Các nút nhánh cóít nhất [(m-1)/2]+1 cây con (nghĩa làcóít nhất [(m-1)/2] khóa) n Tất cả các cây con rỗng đều thuộc cùng 1 mức B-cây Không làB-cây CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 15 [2] B-Cây (B-Tree) CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 16 8
9. [2] B-Cây (B-Tree) u Ý nghĩa: n B-cây làdạng cây cân bằng, phùhợp với việc lưu trữ trên đĩa n B-cây tiêu tốn số phép truy xuất đĩa tối thiểu cho các thao tác n Cóthể quản lý số phần tử rất lớn CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 17 [2] B-Cây (B-Tree) u Độ cao của B-cây: n n: số khoá(key), n >= 1 n m: bậc của cây, m > 2 C/minh: bài tập CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 18 9
10. [2] B-Cây (B-Tree) (tt) u Thao tác thêm phần tử (Insert): thêm 1 khóa v vào cây n Thêm v vào 1 nút lá n 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 B-cây Thêm khóa 19 CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 19 [2] B-Cây (B-Tree) (tt) Thêm khóa 21 nút lábị đầy tách nút lára làm đôi, và chuyển phần tử giữa lên nút cha CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 20 10
11. [2] B-Cây (B-Tree) (tt) nút cha cũng đầy tách làm đôi, chuyển phần tử giữa lên tiếp CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 21 [2] B-Cây (B-Tree) (tt) u Thao tác xóa phần tử (Delete): xóa 1 khóa v trong cây n Thuật toán tương tự đối với cây m-nhánh n Nếu 1 nút cóít hơn [(m-1)/2] khóa: u Nósẽ“mượn”1 khóa từ nút anh em kế cận (nếu nút anh em có dư khóa); u hoặc lànósẽ“sáp nhập”với 1 nút anh em kế cận (nếu nút anh em không dư khóa), cùng với khóa tương ứng ở nút cha CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 22 11
12. [2] B-Cây (B-Tree) (tt) Xoákhóa 26 thay thế nóbằng gi ? CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 23 [2] B-Cây (B-Tree) (tt) thay thế khóa 26 bằng khóa 28, xóa khóa 28 CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 24 12
13. [2] B-Cây (B-Tree) (tt) Xoákhóa 22 thay thế bằng khóa 24 nút láthiếu phần tử CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 25 [2] B-Cây (B-Tree) (tt) “mượn”1 phần tử 28 từ nút anh em CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 26 13
14. [2] B-Cây (B-Tree) (tt) Xóa nút 18 thay thế bằng nút 8 nút láthiếu phần tử CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 27 [2] B-Cây (B-Tree) (tt) sáp nhập 2 nút lá, cùng với khóa ở nút cha nút cha thiếu khóa, nên mượn khóa 22 ở nút anh em CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 28 14
15. [2] B-Cây (B-Tree) (tt) Chuyển các cây con tương ứng CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 29 Tóm lược u Cây M-nhánh n Làm giảm độ cao cây n Thao tác thêm vào vàloại bỏ khóa khá đơn giản n Không làcây cân bằng n Phát triển về phía lá u B-Tree n Làcây M-nhánh cân bằng n Khi thêm hay loại bỏ khóa cóthể phải thực hiện thao tác tách hay gộp nút n Làm giảm đến mức tối thiểu số lần truy xuất đĩa khi lưu dữ liệu ngoài. n Phát triển về phía gốc CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 30 15
16. Ứng dụng của B-Cây u Xây dựng cấu trúc chỉ mục (Index) trong các hệ quản trị CSDL CTDL2 -B-Tree -Nguyen Tri Tuan -DHKHTN -TP.HCM Autum 2006 31 HẾT –CÁM ƠN Hỏi& Đáp 16