tailieunhanh - Bài giảng Phân tích thiết kế và giải thuật - Chương 5: B-Tree

Bài giảng "Phân tích thiết kế và giải thuật - Chương 5: B-Tree" cung cấp cho người học các kiến thức: Giới thiệu, định nghĩa B-Tree, các phép toán trên B-Tree. Đây là một tài liệu hữu ích dành cho các bạn sinh viên và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu. | Bài giảng Phân tích thiết kế và giải thuật - Chương 5 B-Tree B-TREE 1 1 B-Tree Giới thiệu Định nghĩa B-Tree Các phép toán trên B-Tree 2 Giới thiệu Cây 2-3-4 là một ví dụ về cây nhiều nhánh trong cây nhiều nhánh mỗi node sẽ có nhiều hơn hai node con và nhiều hơn một mục dữ liệu. Một loại khác của cây nhiều nhánh là B-tree là cây rất hiệu quả khi dữ liệu nằm trong bộ nhớ ngoài. 3 Định nghĩa B-Tree Một B-tree bậc n có các đặc tính sau i Mỗi node có tối đa 2 n khoá. ii Mỗi node không là node gốc có ít nhất là n khoá. iii Mỗi node hoặc là node lá hoặc có m 1 node con m là số khoá của trang này iv Các khóa được sắp tăng dần từ trái sang phải v Các nút lá nằm cùng một mức 4 Định nghĩa B-Tree Ví dụ B-tree bậc 2 có 3 mức 5 Ưu điểm B-Tree B-Tree là dạng cây cân bằng phù hợp với việc lưu trữ trên đĩa B_Tree tiêu tốn số phép truy xuất đĩa tối thiểu cho các thao tác Có thể quản lý số phần tử rất lớn 6 Các phép toán trên B-Tree Tìm 1 phần tử có khóa bằng X trong cây Thêm 1 khoá vào vào B Tree Xóa 1 khoá trong 1 nút 7 Tìm kiếm phần tử có khóa X trên cây Khoá cần tìm là m đủ lớn ta sử dụng phương pháp tìm kiếm nhị phân nếu m nhỏ ta sử dụng phuơng pháp tìm kiếm tuần tự. Nếu X không tìm thấy sẽ có 3 trường hợp sau xảy ra i Ki lt X lt Ki 1. Tiếp tục tìm kiếm trên cây con Ci ii Km lt X. Tiếp tục tìm kiếm trên Cm iii X lt K1. tiếp tục tìm kiếm trên C0 Quá trình này tiếp tục cho đến khi node đúng được tìm thấy. Nếu đã đi đến node lá mà vẫn không tìm thấy khoá việc tìm kiếm là thất bại. C 1 8 Thêm 1 nút vào B-Tree Tính chất B-Tree một node có ít nhất một nữa số khóa Thêm 1 nút có khóa X vào B-Tree Thêm X vào 1 nút lá Sau khi thêm nếu nút lá đầy Tách nút lá ra làm đôi Chuyển phần tử giữa lên nút cha và lan truyền ngược về gốc. Nếu gốc bị tách cây được đặt ở mức sâu hơn 9 Thêm 1 nút vào B-Tree Nếu số khóa lớn hơn 2n thì tách node Đưa phần tử giữa lên node cha Tạo thêm node mới Chuyển dời một nửa phần tử sang node mới Tiếp tục lan truyền ở node cha nếu node cha sau khi thêm gt 2n .

• Kỹ thuật lập trình
• Bài giảng Phân tích thiết kế
• Phân tích thiết kế dữ liệu
• Thiết kế giải thuật
• Định nghĩa B Tree
• Các phép toán trên B Tree
• phân tích thiết kế hệ thống
• giáo trình phân tích thiết kế hệ thống
• bài giảng phân tích thiết kế hệ thống
• bài tập phân tích thiết kế hệ thốn
• tài liệu phân tích thiết kế hệ thốngg
• Phân tích thiết kế giải thuật
• Kỹ thuật thiết kế giải thuật
• Bài giảng thiết kế giải thuật
• Kỹ thuật phân tích thiết kế giải thuật
• Bài giảng phân tích thiết kế giải thuật
• Thiết kế hệ thống
• Thiết kế cơ sở dữ liệu
• Phân tích cơ sở dữ liệu
• Cơ sở dữ liệu
• Thiết kế CSDL logic
• Bài giảng Phân tích thiết kế hệ thống TMĐT
• Phân tích thiết kế hệ thống thương mại điện tử
• Phân tích hệ thống thương mại điện tử
• Thiết kế tổng thể hệ thống thương mại điện tử
• Thiết kế chi tiết hệ thống thương mại điện tử
• Thiết kế phân đoạn trình diễn
• Thiết kế tổng thể hệ thống
• Kiểm tra thiết kế tổng thể
• Mục đích thiết kế hệ thống thông tin
• Thiết kế giao diện
• Thiết kế các tài liệu ra
• Thiết kế mẫu thu thập thông tin
• Phân tích thiết kế thuật toán
• Phân tích thuật toán
• Thiết kế thuật toán
• Bài giảng Phân tích thiết kế thuật toán
• Bài giảng Phân tích thiết kế hướng đối tượng
• Phân tích thiết kế hướng đối tượng
• Thiết kế hướng đối tượng
• Phân tích và thiết kế hệ thống ở trạng thái tĩnh
• Thiết kế hệ thống ở trạng thái tĩnh
• Phân tích và thiết kế hệ thống ở trạng thái động
• Thiết kế hệ thống ở trạng thái động
• Phương pháp phân tích thuật toán
• Vai trò của phân tích thuật toán
• Quá trình phân tích thuật toán
• Thiết kế bài giảng Giải tích 12
• Thiết kế bài giảng Giải tích
• Bài giảng Giải tích
• Thiết kế bài giảng
• Bài giảng Nguyên hàm
• Bài giảng Tích phân
• Thiết kế chương trình
• Thiết kế cấu trúc
• Lập lược đồ chương trình
• tài liệu phân tích thiết kế hệ thống
• Phân tích chức năng của hệ thống
• Mô hình khung cảnh
• Mô hình dòng dữ liệu
• Mô hình phân rã chức năng