Database Systems Index Structures Overview

csce 608 database systems n.w
1 / 94
Embed
Share

Discover the fundamentals of B+ trees, their insertion/deletion processes, index structures, and search techniques in database systems. Learn about the main purposes, rules, and range searches in B+ trees for efficient data retrieval and management.

  • Database
  • B+ trees
  • Index structures
  • Search techniques
  • Data management
rayaanacharya
ama_m Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. CSCE-608 Database Systems Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 26: B+ trees: insertion and deletion

  2. in tables (relations) lock table DDL language DDL complier database administrator concurrency control file logging & recovery manager transaction manager index/file manager buffer manager DML (query) language query execution engine database programmer DML complier main memory buffers secondary storage (disks) DBMS

  3. The Main Purpose of Index Structures Speedup the search process quickly figure out blocks containing the desired tuples index a=6(R) otherwise have to scan the entire R disks But also need to handle dynamic changes of R 3

  4. B+tree rules A B+tree node of order n k2 p2 k1 k1 k2 kn pn pn+1 p1 kn p3 p1 p2 p3 pn+1 pn Rule 1. All leaves are at same lowest level (balanced tree) Rule 2. Pointers in leaves point to records except for sequence pointer Rule 3. Number of keys/pointers in nodes: Max. # pointers n+1 n+1 n+1 Max. # keys n n n Min. # pointers (n+1)/2 (n+1)/2 +1 2 Min. # keys (n+1)/2 1 (n+1)/2 1 Non-leaf Leaf Root 4

  5. Search in a B+tree 1. Start from the root 2. Search in a leaf block 3. May not have to go to the data file Search(ptr, k); \\ search a record of key value k in the subtree rooted at ptr \\ assume the B+tree is a dense index of order n Case 1. ptr is a leaf \\ pn+1 is the sequence pointer IF (k = ki) for a key ki in *ptr THEN return(pi); ELSE return(Null); Case 2. ptr is not a leaf find a key ki in *ptr such that ki-1 k < ki; return(Search(pi, k)); 5

  6. Range Search in B+tree To research all records whose key values are between k1 and k2: Range-Search(ptr, k1, k2) 1. Call Search(ptr, k1); 2. Follow the sequence pointers until the search key value is larger than k2. 6

  7. Insert into B+tree Basic idea: 1. Find the leaf L where the record r should be inserted; 2. If L has further room, then insert r into L, and return; 3. If L is full, spilt L plus r into two leaves (each is about half full): this causes an additional child for the parent P of L, thus we need to add a child to P; 4. If P is already full, then we have to split P and add an additional child to P s parent (recursively) 7

  8. Insert into B+tree Simple case (space available for new child) Leaf overflow Non-leaf overflow New root 8

  9. Insert into B+tree Simple case (space available for new child) Leaf overflow Non-leaf overflow New root Idea: when there is no space for a new child (all pointers are in use), split the node into two nodes, with both at least half full. 9

  10. Complication: Leaf overflow q p k k p ? + 1 /2 +1 p1 k1 p k --- p** ? + 1 /2 pk pn kn pn+1 kn+1 --- p* ? + 1 /2 +1 ? + 1 /2 +1 ? + 1 /2 p k p k pn kn p* ? + 1 /2 +1 p1 k1 p kp ? + 1 /2 ? + 1 /2 +1 ? + 1 /2 pn+1kn+1 10

  11. Leaf overflow: Insert key 7 (order n = 3) 100 30 30 31 3 5 11 11

  12. Leaf overflow: Insert key 7 (order n = 3) 100 30 7 30 31 3 5 11 12

  13. Leaf overflow: Insert key 7 (order n = 3) 100 30 7 11 30 31 3 5 13

  14. Leaf overflow: Insert key 7 (order n = 3) 100 30 7 11 30 31 3 5 3 5 11 7 14

  15. Leaf overflow: Insert key 7 (order n = 3) 100 30 7 11 30 31 3 5 3 5 11 7 15

  16. Leaf overflow: Insert key 7 (order n = 3) 100 30 7 11 30 31 3 5 3 5 11 7 16

  17. Leaf overflow: Insert key 7 (order n = 3) 100 30 7 11 30 31 3 5 3 5 11 7 17

  18. Leaf overflow: Insert key 7 (order n = 3) 100 7 30 7 11 30 31 3 5 3 5 11 7 18

  19. Complication: nonleaf overflow 19

  20. Complication: nonleaf overflow pk p p1 k1 p pk pnkn pn+1 (? + 1)/2 +1 (? + 1)/2 +1 k pk (? + 1)/2 kn+1pn+2 (? + 1)/2 -1 (? + 1)/2 -1 (? + 1)/2 20

  21. Complication: nonleaf overflow q k(? + 1)/2 pk p p1 k1 p2 k2 p k p (? + 1)/2 -1 k pnkn pn+1kn+1pn+2 (? + 1)/2 +1 p (? + 1)/2 -1 (? + 1)/2 +1 (? + 1)/2 pk p p1 k1 p pk pnkn pn+1 (? + 1)/2 +1 (? + 1)/2 +1 k pk (? + 1)/2 kn+1pn+2 (? + 1)/2 -1 (? + 1)/2 -1 (? + 1)/2 21

  22. Complication: nonleaf overflow q k(? + 1)/2 pk p p1 k1 p2 k2 p k p (? + 1)/2 -1 k pnkn pn+1kn+1pn+2 (? + 1)/2 +1 p (? + 1)/2 -1 (? + 1)/2 +1 (? + 1)/2 pk p p1 k1 p pk pnkn pn+1 (? + 1)/2 +1 (? + 1)/2 +1 k pk (? + 1)/2 kn+1pn+2 (? + 1)/2 -1 (? + 1)/2 -1 (? + 1)/2 22

  23. Complication: nonleaf overflow q k(? + 1)/2 pk p p1 k1 p2 k2 p k p (? + 1)/2 -1 k pnkn pn+1kn+1pn+2 (? + 1)/2 +1 p (? + 1)/2 -1 (? + 1)/2 +1 (? + 1)/2 pk p p1 k1 p pk pnkn pn+1 (? + 1)/2 +1 (? + 1)/2 +1 k pk (? + 1)/2 kn+1pn+2 (? + 1)/2 -1 (? + 1)/2 -1 (? + 1)/2 23

  24. Complication: nonleaf overflow q k(? + 1)/2 pk p ? What is the key here? p1 k1 p2 k2 p k p (? + 1)/2 -1 k pnkn pn+1kn+1pn+2 (? + 1)/2 +1 p (? + 1)/2 -1 (? + 1)/2 +1 (? + 1)/2 pk p p1 k1 p pk pnkn pn+1 (? + 1)/2 +1 (? + 1)/2 +1 k pk (? + 1)/2 kn+1pn+2 (? + 1)/2 -1 (? + 1)/2 -1 (? + 1)/2 24

  25. Complication: nonleaf overflow q k(? + 1)/2 pk p ? What is the key here? p1 k1 p2 k2 p k p (? + 1)/2 -1 k pnkn pn+1kn+1pn+2 (? + 1)/2 +1 p (? + 1)/2 -1 (? + 1)/2 +1 (? + 1)/2 pk p not used p1 k1 p pk pnkn pn+1 (? + 1)/2 +1 (? + 1)/2 +1 k pk (? + 1)/2 kn+1pn+2 (? + 1)/2 -1 (? + 1)/2 -1 (? + 1)/2 25

  26. Complication: nonleaf overflow q k k (? + 1)/2 pk p (? + 1)/2 p1 k1 p2 k2 p k p (? + 1)/2 -1 k pnkn pn+1kn+1pn+2 (? + 1)/2 +1 p (? + 1)/2 -1 (? + 1)/2 +1 (? + 1)/2 pk p p1 k1 p pk pnkn pn+1 (? + 1)/2 +1 (? + 1)/2 +1 k pk (? + 1)/2 kn+1pn+2 (? + 1)/2 -1 (? + 1)/2 -1 (? + 1)/2 26

  27. Complication: nonleaf overflow q k k (? + 1)/2 pk p (? + 1)/2 k (? + 1)/2 (? + 1)/2 p1 k1 p2 k2 p k p (? + 1)/2 -1 k pnkn pn+1kn+1pn+2 (? + 1)/2 +1 p (? + 1)/2 -1 (? + 1)/2 +1 (? + 1)/2 pk p p1 k1 p pk pnkn pn+1 (? + 1)/2 +1 (? + 1)/2 +1 k pk (? + 1)/2 kn+1pn+2 (? + 1)/2 -1 (? + 1)/2 -1 (? + 1)/2 27

  28. Nonleaf overflow: Insert key 160 (order n = 3) 100 120 150 180 160 150 156 179 180 210 28

  29. Nonleaf overflow: Insert key 160 (order n = 3) 100 120 150 180 150 156 180 210 160 179 150 156 179 160 29

  30. Nonleaf overflow: Insert key 160 (order n = 3) 100 120 150 180 150 156 180 210 160 179 150 156 179 160 30

  31. Nonleaf overflow: Insert key 160 (order n = 3) 100 120 150 180 160 150 156 180 210 160 179 150 156 179 160 31

  32. Nonleaf overflow: Insert key 160 (order n = 3) 100 no room! 120 150 180 160 150 156 180 210 160 179 150 156 179 160 32

  33. Nonleaf overflow: Insert key 160 (order n = 3) 120 150 180 160 100 160 180 120 150 150 156 180 210 160 179 150 156 179 160 33

  34. Nonleaf overflow: Insert key 160 (order n = 3) 120 150 180 160 100 160 180 120 150 150 156 180 210 160 179 150 156 179 160 34

  35. Nonleaf overflow: Insert key 160 (order n = 3) 120 150 180 160 100 150 160 180 120 150 150 156 180 210 160 179 150 156 179 160 35

  36. Nonleaf overflow: Insert key 160 (order n = 3) 100 150 160 180 120 150 156 180 210 160 179 36

  37. Insert into B+tree Simple case (space available for new child) Leaf overflow Non-leaf overflow New root 37

  38. Insert into B+tree Simple case (space available for new child) Leaf overflow Non-leaf overflow New root 38

  39. New root: Insert key 45 (order n = 3) 39

  40. New root: Insert key 45 (order n = 3) 10 20 30 45 1 2 3 10 12 20 25 30 32 40 40

  41. New root: Insert key 45 (order n = 3) 10 20 30 1 2 3 10 12 40 45 20 25 30 32 30 32 40 45 41

  42. New root: Insert key 45 (order n = 3) 10 20 30 no room 40 1 2 3 10 12 40 45 20 25 30 32 30 32 40 45 42

  43. New root: Insert key 45 (order n = 3) 10 20 30 40 10 20 30 40 1 2 3 10 12 40 45 20 25 30 32 30 32 40 45 43

  44. New root: Insert key 45 (order n = 3) new root 30 10 20 30 40 10 20 40 1 2 3 10 12 40 45 20 25 30 32 30 32 40 45 44

  45. New root: Insert key 45 (order n = 3) 30 40 10 20 1 2 3 10 12 40 45 20 25 30 32 45

  46. Pseudo Code for Insertion in B+tree Insert(pt, (p, k), (p', k')); \\ technically, the smallest key kmin in pt is also returned \\ (p, k) is a pointer-key pair to be inserted into the subtree rooted at pt; p' is a new sibling \\ of pt, if created, and k' is the smallest key value in p' ; Case 1.pt = (p1, k1, ..., pi, ki, --, pn+1) is a leaf \\ pn+1 is the sequence pointer IF (i < n) THEN insert (p, k) into pt; return(p' = Null, k' = 0); ELSE re-arrange (p1, k1), ..., (pn, kn),and (p, k) into ( 1, 1, ..., n+1, n+1); create a new leaf p''; put ( r+1, r+1, , n+1, n+1, --, pn+1) in p''; \\ r = (n+1)/2 put ( 1, 1, ..., r, r, --, p'') in pt; \\ pn+1 and p'' are sequence pointers in p'' and pt. IFpt is the root THEN create a new root with children pt and p'' (and key r+1) ELSE return(p' = p'',k' = r+1); Case 2.pt is not a leaf find a key ki in pt such that ki-1 k < ki; Insert(pi , (k, p), (k", p")); IF (p" = Null) THEN return(k' = 0, p' = Null); ELSE IF there is room in pt, THEN insert (k", p") into pt; return(k' = 0, p' = Null); ELSE re-arrange the content in pt and (k", p") into ( 1, 1, ..., n+1, n+1, n+2); create a new node p''; put ( r+1, r+1, , n+1, n+1, n+2, -- ) in p''; \\ r = (n+1)/2 leave ( 1, 1, ..., r-1, r-1, r , -- ) in pt; IFpt is the root THEN create a new root with children pt and p'' (and key r) ELSE return(p' = p'',k' = r ). 46

  47. Pseudo Code for Insertion in B+tree insert in a leaf Insert(pt, (p, k), (p', k')); \\ technically, the smallest key kmin in pt is also returned \\ (p, k) is a pointer-key pair to be inserted into the subtree rooted at pt; p' is a new sibling \\ of pt, if created, and k' is the smallest key value in p' ; Case 1.pt = (p1, k1, ..., pi, ki, --, pn+1) is a leaf \\ pn+1 is the sequence pointer IF (i < n) THEN insert (p, k) into pt; return(p' = Null, k' = 0); ELSE re-arrange (p1, k1), ..., (pn, kn),and (p, k) into ( 1, 1, ..., n+1, n+1); create a new leaf p''; put ( r+1, r+1, , n+1, n+1, --, pn+1) in p''; \\ r = (n+1)/2 put ( 1, 1, ..., r, r, --, p'') in pt; \\ pn+1 and p'' are sequence pointers in p'' and pt. IFpt is the root THEN create a new root with children pt and p'' (and key r+1) ELSE return(p' = p'',k' = r+1); Case 2.pt is not a leaf find a key ki in pt such that ki-1 k < ki; Insert(pi , (k, p), (k", p")); IF (p" = Null) THEN return(k' = 0, p' = Null); ELSE IF there is room in pt, THEN insert (k", p") into pt; return(k' = 0, p' = Null); ELSE re-arrange the content in pt and (k", p") into ( 1, 1, ..., n+1, n+1, n+2); create a new node p''; put ( r+1, r+1, , n+1, n+1, n+2, -- ) in p''; \\ r = (n+1)/2 leave ( 1, 1, ..., r-1, r-1, r , -- ) in pt; IFpt is the root THEN create a new root with children pt and p'' (and key r) ELSE return(p' = p'',k' = r ). 47

  48. Pseudo Code for Insertion in B+tree insert in a leaf Insert(pt, (p, k), (p', k')); \\ technically, the smallest key kmin in pt is also returned \\ (p, k) is a pointer-key pair to be inserted into the subtree rooted at pt; p' is a new sibling \\ of pt, if created, and k' is the smallest key value in p' ; Case 1.pt = (p1, k1, ..., pi, ki, --, pn+1) is a leaf \\ pn+1 is the sequence pointer IF (i < n) THEN insert (p, k) into pt; return(p' = Null, k' = 0); ELSE re-arrange (p1, k1), ..., (pn, kn),and (p, k) into ( 1, 1, ..., n+1, n+1); create a new leaf p''; put ( r+1, r+1, , n+1, n+1, --, pn+1) in p''; \\ r = (n+1)/2 put ( 1, 1, ..., r, r, --, p'') in pt; \\ pn+1 and p'' are sequence pointers in p'' and pt. IFpt is the root THEN create a new root with children pt and p'' (and key r+1) ELSE return(p' = p'',k' = r+1); Case 2.pt is not a leaf find a key ki in pt such that ki-1 k < ki; Insert(pi , (k, p), (k", p")); IF (p" = Null) THEN return(k' = 0, p' = Null); ELSE IF there is room in pt, THEN insert (k", p") into pt; return(k' = 0, p' = Null); ELSE re-arrange the content in pt and (k", p") into ( 1, 1, ..., n+1, n+1, n+2); create a new node p''; put ( r+1, r+1, , n+1, n+1, n+2, -- ) in p''; \\ r = (n+1)/2 leave ( 1, 1, ..., r-1, r-1, r , -- ) in pt; IFpt is the root THEN create a new root with children pt and p'' (and key r) ELSE return(p' = p'',k' = r ). no overflow 48

  49. Pseudo Code for Insertion in B+tree insert in a leaf Insert(pt, (p, k), (p', k')); \\ technically, the smallest key kmin in pt is also returned \\ (p, k) is a pointer-key pair to be inserted into the subtree rooted at pt; p' is a new sibling \\ of pt, if created, and k' is the smallest key value in p' ; Case 1.pt = (p1, k1, ..., pi, ki, --, pn+1) is a leaf \\ pn+1 is the sequence pointer IF (i < n) THEN insert (p, k) into pt; return(p' = Null, k' = 0); ELSE re-arrange (p1, k1), ..., (pn, kn),and (p, k) into ( 1, 1, ..., n+1, n+1); create a new leaf p''; put ( r+1, r+1, , n+1, n+1, --, pn+1) in p''; \\ r = (n+1)/2 put ( 1, 1, ..., r, r, --, p'') in pt; \\ pn+1 and p'' are sequence pointers in p'' and pt. IFpt is the root THEN create a new root with children pt and p'' (and key r+1) ELSE return(p' = p'',k' = r+1); Case 2.pt is not a leaf find a key ki in pt such that ki-1 k < ki; Insert(pi , (k, p), (k", p")); IF (p" = Null) THEN return(k' = 0, p' = Null); ELSE IF there is room in pt, THEN insert (k", p") into pt; return(k' = 0, p' = Null); ELSE re-arrange the content in pt and (k", p") into ( 1, 1, ..., n+1, n+1, n+2); create a new node p''; put ( r+1, r+1, , n+1, n+1, n+2, -- ) in p''; \\ r = (n+1)/2 leave ( 1, 1, ..., r-1, r-1, r , -- ) in pt; IFpt is the root THEN create a new root with children pt and p'' (and key r) ELSE return(p' = p'',k' = r ). no overflow with overflow 49

  50. Pseudo Code for Insertion in B+tree insert in a leaf Insert(pt, (p, k), (p', k')); \\ technically, the smallest key kmin in pt is also returned \\ (p, k) is a pointer-key pair to be inserted into the subtree rooted at pt; p' is a new sibling \\ of pt, if created, and k' is the smallest key value in p' ; Case 1.pt = (p1, k1, ..., pi, ki, --, pn+1) is a leaf \\ pn+1 is the sequence pointer IF (i < n) THEN insert (p, k) into pt; return(p' = Null, k' = 0); ELSE re-arrange (p1, k1), ..., (pn, kn),and (p, k) into ( 1, 1, ..., n+1, n+1); create a new leaf p''; put ( r+1, r+1, , n+1, n+1, --, pn+1) in p''; \\ r = (n+1)/2 put ( 1, 1, ..., r, r, --, p'') in pt; \\ pn+1 and p'' are sequence pointers in p'' and pt. IFpt is the root THEN create a new root with children pt and p'' (and key r+1) ELSE return(p' = p'',k' = r+1); Case 2.pt is not a leaf find a key ki in pt such that ki-1 k < ki; Insert(pi , (k, p), (k", p")); IF (p" = Null) THEN return(k' = 0, p' = Null); ELSE IF there is room in pt, THEN insert (k", p") into pt; return(k' = 0, p' = Null); ELSE re-arrange the content in pt and (k", p") into ( 1, 1, ..., n+1, n+1, n+2); create a new node p''; put ( r+1, r+1, , n+1, n+1, n+2, -- ) in p''; \\ r = (n+1)/2 leave ( 1, 1, ..., r-1, r-1, r , -- ) in pt; IFpt is the root THEN create a new root with children pt and p'' (and key r) ELSE return(p' = p'',k' = r ). no overflow new child to parent with overflow 50

Related


No related presentations.

More Related Content