›
›

Cơ sở dữ liệu - Chapter 12: Multiway trees

pdf 44 trang vanle 3300
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở dữ liệu - Chapter 12: Multiway trees", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfco_so_du_lieu_chapter_12_multiway_trees.pdf

Nội dung text: Cơ sở dữ liệu - Chapter 12: Multiway trees

  1. Chapter 12  Lexicographic Search Trees: Tries  Multiway Trees  B-Tree, B*-Tree, B+-Tree  Red-Black Trees (BST and B-Tree)  2-d Tree, k-d Tree 1
  2. Basic Concepts 2
  3. Basic Concepts 3
  4. Trees 4
  5. Trees and Orchard 6
  6. Lexicographic Search Tree 8
  7. Multiway Trees 9
  8. M-Way Search Tree 12
  9. B-Tree 16
  10. B-Tree Insertion 18
  11. B-Tree Insertion 19
  12. B-Tree B_Node count data > branch > End B_Node B_Tree root End B_Tree 20
  13. Methods and Functions SearchTree recursiveSearchTree (calls) SearchNode Insert recursiveInsert splitNode push_in
  14. B-Tree SeachTree SearchTree (ref target ) 1. return recursiveSearchTree(root, target) End SearchTree 22
  15. B-Tree SeachTree recursiveSearchTree (val subroot , ref target ) 1. result = not_present 2. if (subroot is not NULL) 1. result = SearhNode (subroot, target, position) 2. if (result = not_present) 1. result = recursiveSearchTree ( subroot->branchposition, target) 3. else 1. target = subroot->dataposition 3. return result End recursiveSearchTree 23
  16. B-Tree SeachTree SearchNode (val subroot , val target , ref position ) 1. position = 0 2. loop (position count) AND (target>subroot->dataposition) 1. position = position + 1 // Sequential Search 3. if (position count) AND (target = subroot->dataposition) 1. return success 4. else 1. return not_present End SearchNode 24
  17. Methods and Functions SearchTree recursiveSearchTree (calls) SearchNode Insert recursiveInsert splitNode push_in
  18. B-Tree Insertion Insert (val newData ) (local variable: median , rightBranch , newroot , result ) Return duplicate_error, success 1. result = recursiveInsert (root, newData, median, rightBranch) 2. if (result = overflow) 1. Allocate newroot 2. newroot->count = 1 3. newroot->data0 = median 4. newroot->branch0 = root 5. newroot->branch1 = rightBranch 6. root = newroot 7. result = success 3. return result End Insert 26
  19. Split Node 27
  20. B-Tree Insertion recursiveInsert (val subroot , val newData , ref median , ref rightBranch ) Return overflow, duplicate_error, success 1. if (subroot = NULL) 1. median = newData 2. rightbranch = NULL 3. result = overflow 2. else 28
  21. recursiveInsert (val subroot , val newData , ref median , ref rightBranch ) (cont.) 2. // else, local variables: extraEntry, extraBranch 1. if (SearchNode (subroot, newData, position) = success) 1. result = duplicate_error 2. else 1. result = recursiveInsert (subroot->branchposition, newData, extraEntry, extraBranch) 2. if (result = overflow) 1. if (subroot->count < order-1) 1. result = success 2. push_in (subroot, extraEntry, extraBranch, position) 2. else 1. splitNode (subroot, extraEntry, extraBranch, position, rightBrach, median) 3. return result End recursiveInsert 29
  22. Push In 30
  23. B-Tree push_in (val subroot , val entry , val rightBranch , val position ) 1. i = subroot->count 2. loop ( i > position) 1. subroot->datai = subroot->datai - 1 2. subroot->branchi + 1 = subroot->branchi 3. i = i + 1 3. subroot->data position= entry 4. subroot->branch position + 1= rightBranch 5. subroot->count = -subroot->count + 1 End push_in 31
  24. B-Tree splitNode (val subroot , val extraEntry , val extraBranch , val position , ref rightHalf , ref median ) 32
  25. B-Tree Insertion 33
  26. B-Tree Insertion 34
  27. B-Tree Deletion 36
  28. B-Tree Deletion 37
  29. B-Tree Deletion 38
  30. k-d Trees  2-d Tree  k-d Tree 44