Bài giảng Cơ sở dữ liệu - Chương 5: Xác định khóa - Đỗ Thị Kim Thành

Nguyễn Hà Giang - 2008 1 Tree Structure ThS. Nguyễn Hà Giang Hutech - FIT Nguyễn Hà Giang - 2008 2 Nội dung  Cấu trúc cây  Cây nhị phân  Cây nhị phân tìm kiếm  Cây nhị phân tìm kiếm cân bằng AVL  Phần mở rộng (cây đa phân)  Cây Top-Down  B-Tree Nguyễn Hà Giang - 2008 3 Phần mở rộng Cây đa phân Top-down, B-Tree Nguyễn Hà Giang - 2008 4 Phần mở rộng  Cây đa phân/cây đa nhánh  Có 1 nút là nút gốc  Mỗi nút có thể có n nút con  Cây đa phân tìm kiếm  Mỗi nút trên cây đa phân tìm kiếm có nhiều khoá và nhiều nhánh con  Số khoá ít hơn nhánh con là 1  VD: có 3 khoá thì sẽ có 4 nhánh con Nguyễn Hà Giang - 2008 5 Phần mở rộng  Cây đa phân tìm kiếm k1 kn-1 Cây con S1 Cây con S2 Cây con Sn k2 Cấu trúc của một nút Nguyễn Hà Giang - 2008 6 Cây đa phân tìm kiếm  Định nghĩa cây đa phân tìm kiếm  Tại mỗi nút phải thoả điều kiện  Tất cả khoá trên nhánh s1 nhỏ hơn hay bằng k1  Tất cả khóa trên nhánh cây con si (1≤ i ≤n-1) đều lớn hơn khoá ki-1 và nhỏ hơn hay bằng ki  Tất cả khóa trên nhánh cây con sn đều lớn hơn khóa kn-1  Cây nhị phân tìm kiếm là cây đa phân tìm kiếm có bậc là 2! Nguyễn Hà Giang - 2008 7 Cây đa phân tìm kiếm 120 150 180 k ≤ 120 120 < k ≤ 150 150 < k ≤ 180 k > 180 Nút cha Nguyễn Hà Giang - 2008 8 Cây đa phân tìm kiếm  Cây đa phân tìm kiếm bậc 3/cây tam phân tìm kiếm 50 100 10 30 60 150 200 15 204 40 120 130 160 210 >100≤ 50 Nguyễn Hà Giang - 2008 9 Cây đa phân tìm kiếm  Cây đa phân tìm kiếm thông dụng  Cây top-down  B-tree  Cây top-down  Là cây đa phân tìm kiếm  Tất cả các nút ko đủ (hay ko đầy) đều là nút lá! Nguyễn Hà Giang - 2008 10 Cây Top-Down  Cây Top-down bậc 3 50 100 10 30 60 150 200 15 204 40 120 130 160 210 Nút không đầy phải là nút lá Nguyễn Hà Giang - 2008 11 Cây Top-Down  Cây Top-Down ? 50 100 10 30 60 150 200 15 204 40 120 130 160 21055 88 Nguyễn Hà Giang - 2008 12 Cây Top-Down  Thêm phần tử vào cây Top-Down  Xác định nút lá phù hợp để chèn khóa  Nếu nút không đầy:  Chèn khóa vào vị trí thích hợp  Nếu nút đầy:  Cấp phát nút lá mới chứa khoá cần chèn  Nút mới này là con của nút cũ. Nguyễn Hà Giang - 2008 13 Cây Top-Down  Chèn 18 vào cây? 50 100 10 30 60 150 200 15 204 40 120 130 160 210 Nguyễn Hà Giang - 2008 14 Cây Top-Down  Chèn 18 vào cây 50 100 10 30 60 150 200 15 204 40 120 130 160 210 18 Nguyễn Hà Giang - 2008 15 Cây Top-Down  Chèn 75 vào cây? 50 100 10 30 60 150 200 15 204 40 120 130 160 210 18 Nguyễn Hà Giang - 2008 16 Cây Top-Down  Chèn 75 vào cây 50 100 10 30 60 75 150 200 15 204 40 120 130 160 210 18 Chèn vào danh sách khoá Nút bây giờ đã đầy Nguyễn Hà Giang - 2008 17 Cây Top-Down  Mô tả cấu trúc dữ liệu cho cây Top-down  Gọi ORDER là bậc của cây top-down  Với mỗi nút p trên cây  NumTrees là số nhánh cây con nút p: nút sẽ có NumTrees-1 khoá!  Mảng Key chứa khoá của nút  Mảng con trỏ Son trỏ đến các nhánh con Nguyễn Hà Giang - 2008 18 Cây Top-Down  Khai báo cấu trúc nút cho cây Top-Down #define ORDER typedef struct node { int NumTrees; DataType Key[ORDER-1]; struct node * Son[ORDER]; } NODE; typedef NODE * NodePtr; NodePtr pTopDownTree; Nguyễn Hà Giang - 2008 19 Cây Top-Down  Các thao tác  CreateNode: cấp phát một nút mới có khoá k, và khởi tạo danh sách các cây con trỏ đến NULL  SearchNode: Trả về vị trí nhỏ nhất của khoá trong nút p lớn hơn hay bằng k  Search: duyệt từ gốc, đi xuống các nút thích hợp để kiểm tra xem khóa k có trong nút nào đó trên cây hay không  ShowTree: duyệt cây  Insert: chèn một khoá vào cây Nguyễn Hà Giang - 2008 20 Cây Top-Down  CreateNode: tạo nút mới cho cây NodePtr CreateNode(int k){ NodePtr p; p = NewNode(); p->NumTrees=2; //có 2 nhánh cây con p->Key[0]=k; //nút mới chưa có nút con for(int i=0; i < ORDER; i++) p->Son[i]=NULL; return p; } Nguyễn Hà Giang - 2008 21 Cây Top-Down  SearchNode:  Trả về vị trí nhỏ nhất của khoá trong nút p bắt đầu lớn hơn hay bằng k.  Trường hợp k lớn hơn tất cả các khoá trong nút p thì trả về vị trí p->NumTrees – 1 int SearchNode(NodePtr p, int k){ int i = 0; while ( iNumTrees-1 && p->Key[i] <k) i++; return i; } Nguyễn Hà Giang - 2008 22 Cây Top-Down  NodePtr Search(NodePtr Tree, int k, int &pos, int &found)  Trường hợp tìm thấy  found = true  Hàm trả về địa chỉ của nút chứa khoá k  Pos là vị trí của k trong nút p  Không tìm thấy  found = false  Hàm trả về vị trí con trỏ của nút lá có thể thêm k vào  Biến pos trả về vị trí có thể chèn khoá k vào nút lá q Nguyễn Hà Giang - 2008 23 Cây Top-Down NodePtr search(NodePtr pTree, int k, int &pos, int &found){ int i; NodePtr p,q; q = NULL; p = pTree; while(p != NULL){ i = SearchNode(p, k); if(i NumTrees-1 && k==p->Key[i]) {//found found = TRUE; pos = i; return p; } q = p; p = p->Son[i]; // xuống cây con thứ i } found = FALSE; pos = i; return q; } Nguyễn Hà Giang - 2008 24 Cây Top-Down  ShowTree: duyệt cây  Duyệt theo thứ tự xen kẻ: cây con và khoá void ShowTree(NodePtr pTree){ int i, nt; if(pTree ==NULL) return; else{ nt = pTree->NumTrees; for(i=0; i< nt-1; i++){ ShowTree(pTree->Son[i]); printf("%8d", pTree->Key[i]); } ShowTree(pTree->Son[nt-1]); } } Nguyễn Hà Giang - 2008 25 Cây Top-Down  InsertLeaf: chèn 1 khoá vào nút lá chưa đầy void InsertLeaf(NodePtr p, int k, int pos){ int i, nt; nt=p->NumTrees; p->NumTrees=nt+1; for(i=nt-1;i>pos ;i--){ p->Key[i]= p->Key[i-1]; } p->Key[pos] = k; } Nguyễn Hà Giang - 2008 26 Cây Top-Down  Insert: chèn 1 khóa vào cây Top-Down  Nếu cây rỗng: tạo nút mới là gốc của cây  Nếu cây đã chứa khóa thì thoát  Trường hợp chưa chứa khoá  Xác định nút thích hợp để chèn vào  Nút đã đầy thì tạo nút con mới chứa khoá cần thêm  Nếu nút chưa đầy, chèn khóa vào danh sách khoá của nút Nguyễn Hà Giang - 2008 27 Cây Top-Down NodePtr Insert(NodePtr pTree, int k){ NodePtr s, p; int position,found; if(ptree==NULL){ // cây rỗng tạo nút gốc của cây ptree=CreateNode(k); return ptree; } s=Search(pTree, k, position, found); if(found==TRUE){ printf("\n Khoa da ton tai"); return s; } if(s->NumTrees<ORDER){ // chèn vào danh sách khoá InsertLeaf(s, k, position); return s; } p=CreateNode(k); // tạo nút mới s->Son[position] = p; // nút mới trở thành nút con của s return p; } Nguyễn Hà Giang - 2008 28 Nguyễn Hà Giang - 2008 29 B-Tree  Cây B-Tree bậc m là cây đa phân tìm kiếm thoả  Tất cả nút lá có cùng một mức  Tất cả các nút trên cây trừ nút gốc có ít nhất (m-1)/2 khoá  Đặc điểm  B-Tree là cây cân bằng và chiều sâu của cây nhỏ nên việc tìm kiếm B-Tree được thực hiện nhanh!  Vì tất cả các nút đều đầy hơn một nửa do đó tối ưu  Dùng B-Tree để truy xuất dữ liệu lưu ở bộ nhớ ngoài Nguyễn Hà Giang - 2008 30 B-Tree  Tác giả là Rudolf Bayer và Ed McCreight  Chữ B có thể viết tắt:  Balance: do tất cả nút lá cùng mức  Bayer: tên tác giả  Branching Tree  Boeing: do các tác giả làm việc Boeing Scientific Research Labs Nguyễn Hà Giang - 2008 31 B-Tree  Minh họa B-Tree bậc 5 50 10 30 150 200 15 17 202 3 4 8 40 44 60 70 130 160 180 210 250 Có tối thiểu 2 khoá Trừ nút gốc Nguyễn Hà Giang - 2008 32 B-Tree  Thao tác chèn khoá x vào cây  Xác định vị nút lá thích hợp để chèn khoá mới vào nút lá này.  Nếu nút lá chưa đầy: thêm khoá mới vào  Nếu nút lá đầy: đã tồn tại ORDER-1 khoá và ORDER nhánh con.  Giả sử ta thêm khoá x vào nút lá này khi đó nút sẽ có ORDER khóa  Thực hiện tách nút này thành hai nút bằng nhau như sau:  Nút nửa trái nLeft gồm các khoá nhỏ từ vị trí 0 đến midkey-1  Nút nửa phải nRight gồm các khoá lớn từ midkey+1 đến ORDER  Khoá MidKey và nút con nRight được chèn vào nút cha. Quá trình xử lý tương tự với nút MidKey và các khoá trong nRight khi chèn vào nút cha. Nguyễn Hà Giang - 2008 33 B-Tree  Chèn khoá 45 vào cây 50 10 30 150 200 15 17 202 3 4 8 40 44 60 70 130 160 180 210 250 Nguyễn Hà Giang - 2008 34 B-Tree  Chèn khoá 45 vào cây 50 10 30 150 200 15 17 202 3 4 8 40 44 45 60 70 130 160 180 210 250 Chèn 45 vào nút {40,44} chưa đầy Chèn bình thường, bổ sung vào vị trí Thích hợp trong danh sách khoá Nguyễn Hà Giang - 2008 35 B-Tree  Chèn khoá 5 vào cây 50 10 30 150 200 15 17 202 3 4 8 40 44 45 60 70 130 160 180 210 250 Nguyễn Hà Giang - 2008 36 B-Tree  Chèn khoá 5 vào cây 50 10 30 150 200 15 17 202 3 4 5 8 40 44 45 60 70 130 160 180 210 250 Phải tách nút: MidKey là 4, nLeft ={2 3}, nRight = {5 8} Nguyễn Hà Giang - 2008 37 B-Tree  Chèn khoá 5 vào cây 50 10 30 150 200 15 17 202 3 40 44 45 60 70 130 160 180 210 250 4 5 8 Đưa nhóm nút này lên nút {10 30} Nguyễn Hà Giang - 2008 38 B-Tree  Chèn khoá 5 vào cây 50 4 10 30 150 200 15 17 202 3 40 44 45 60 70 130 160 180 210 250 5 8 Đưa nhóm nút {5 8} này lên nút {10 30} Nguyễn Hà Giang - 2008 39 B-Tree  Chèn khoá 5 vào cây 50 4 10 30 150 200 15 17 202 3 40 44 45 60 70 130 160 180 210 2505 8 {5 8} trở thành cây con thứ 2 của nút {4 10 30} Nguyễn Hà Giang - 2008 40 B-Tree  Chèn khoá 41 vào cây 50 4 10 30 150 200 15 17 202 3 40 44 45 60 70 130 160 180 210 2505 8 Nguyễn Hà Giang - 2008 41 B-Tree  Chèn khoá 41 vào cây 50 4 10 30 150 200 15 17 202 3 40 41 44 45 60 70 130 160 180 210 2505 8 Nguyễn Hà Giang - 2008 42 B-Tree  Chèn khoá 43 vào cây 50 4 10 30 150 200 15 17 202 3 40 41 44 45 60 70 130 160 180 210 2505 8 Nguyễn Hà Giang - 2008 43 B-Tree  Chèn khoá 43 vào cây 50 4 10 30 150 200 15 17 202 3 40 41 43 44 45 60 70 130 160 180 210 2505 8 Tách nút Nguyễn Hà Giang - 2008 44 B-Tree  Chèn khoá 43 vào cây 50 4 10 30 43 150 200 15 17 202 3 40 41 60 70 130 160 180 210 2505 8 44 45 Nguyễn Hà Giang - 2008 45 B-Tree  Chèn khoá 46, 48 vào cây 50 4 10 30 43 150 200 15 17 202 3 40 41 60 70 130 160 180 210 2505 8 44 45 Nguyễn Hà Giang - 2008 46 B-Tree  Chèn khoá 46, 48 vào cây 50 4 10 30 43 150 200 15 17 202 3 40 41 60 70 130 160 180 210 2505 8 44 45 46 48 Nguyễn Hà Giang - 2008 47 B-Tree  Chèn khoá 47 vào cây 50 4 10 30 43 150 200 15 17 202 3 40 41 60 70 130 160 180 210 2505 8 44 45 46 47 48 Chia nút Nguyễn Hà Giang - 2008 48 B-Tree  Chèn khoá 47 vào cây 50 4 10 30 43 46 150 200 15 17 202 3 40 41 60 70 130 160 180 210 2505 8 44 45 47 48 Chia nút Nguyễn Hà Giang - 2008 49 B-Tree  Chèn khoá 47 vào cây 30 50 4 10 150 200 15 17 202 3 40 41 60 70 130 160 180 210 2505 8 44 45 47 48 43 46 Nguyễn Hà Giang - 2008 50 B-Tree  Nhận xét về cân bằng:  B-Tree: upward split  BST: downward split  B-Tree  Tốt cho việc: exact match search  Không tốt: range search  cải tiến với B+-Tree  Ứng dụng  Tổ chức dữ liệu lưu bộ nhớ ngoài khi dữ liệu quá lớn  Ổn định, truy xuất nhanh với số lần truy xuất thấp Nguyễn Hà Giang - 2008 51 B-Tree  Các loại B-Tree cải tiến để tối ưu bộ nhớ  B*-Tree bậc m  Là B-Tree bậc m, tất cả nút trừ gốc đầy hơn 2/3  Hiệu suất dùng bộ nhớ là hơn 67%  Compact B*-Tree  Tất cả nút đều đầy (ngoại trừ một số nút lá ở cuối)  Ít dùng vì giải thuật thêm khoá vào cây phức tạp, chi phí chuyển cây về compact Btree rất lớn Nguyễn Hà Giang - 2008 52 B-Tree  B+-Tree  Tất cả khóa có mặt ở nút lá  Các nút lá được liên kết với nhau từ trái sang phải dạng DSLK 41 15 22 32 49 58 4 12 15 18 22 25 27 30 32 35 38 41 45 49 51 55 58 60 63 Các khoá đều nằm ở nút lá Nguyễn Hà Giang - 2008 53 Đọc thêm  Tài liệu tham khảo    html  ree.html