79
Zusatzfolien zu B- Bäumen

Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

Embed Size (px)

Citation preview

Page 1: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

Zusatzfolien zu B-Bäumen

Page 2: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

2

Page 3: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

3

Page 4: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

4

Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

Page 5: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

5

Sukzessiver Aufbau eines B-Baums vom Grad k=2

10 13 19

7

Page 6: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

6

Sukzessiver Aufbau eines B-Baums vom Grad k=2

7 10 13 19

3

Page 7: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

7

Sukzessiver Aufbau eines B-Baums vom Grad k=2

7 10 13 19

3

?

Page 8: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

8

Sukzessiver Aufbau eines B-Baums vom Grad k=2

7 10

3

13 19

?

Page 9: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

9

Sukzessiver Aufbau eines B-Baums vom Grad k=2

3 7

3

13 19

?10

Page 10: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

10

Sukzessiver Aufbau eines B-Baums vom Grad k=2

3 7 13 19

?10

Page 11: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

11

Sukzessiver Aufbau eines B-Baums vom Grad k=2

3 7 13 19

?10

1

Page 12: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

12

Sukzessiver Aufbau eines B-Baums vom Grad k=2

3 7 13 19

?10

1

Page 13: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

13

Sukzessiver Aufbau eines B-Baums vom Grad k=2

3 7 13 19

?10

1

Page 14: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

14

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 3 7 13 19

?10

1

Page 15: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

15

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 3 7 13 19

?10

2

Page 16: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

16

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 3 7 13 19

?10

2

2

Page 17: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

17

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 3 7 13 19

?10

2

2

Page 18: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

18

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 3 7 13 19

?10

4

Page 19: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

19

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 3 7 13 19

?10

4

4

Page 20: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

20

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 3 7 13 19

?10

4

4

Page 21: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

21

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 3 7 13 19

?10

4

4

Page 22: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

22

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 3 7 13 19

?3 10

4

4

Page 23: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

23

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 13 19

?3 10

4 7

Page 24: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

24

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 13 19

?3 10

11

4 7

Page 25: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

25

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 11 13 19

?3 10

4 7

Page 26: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

26

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 11 13 19

?3 10

21

4 7

Page 27: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

27

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 11 13 19

?3 10

21

4 7

Page 28: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

28

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 11 13 19 21

?3 10

12

4 7

Page 29: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

29

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 11 13 19 21

?3 10

12

4 7 12

Page 30: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

30

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 11 13 19 21

?3 10

12

4 7 12

Page 31: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

31

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 11 13 19 21

?3 10

12

4 7 12

Page 32: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

32

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 11 13 19 21

?3 10 13

12

4 7 12

Page 33: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

33

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 11 19 21

?3 10 13

12

4 7 11 12

Page 34: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

34

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 19 21

?3 10 13

12

4 7 11 12

Page 35: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

35

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 19 21

?3 10 13

14

4 7 11 12

Page 36: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

36

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 14 19 21

?3 10 13

14

4 7 11 12

Page 37: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

37

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 14 19 21

?3 10 13

15

4 7 11 12

Page 38: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

38

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 14 15 19 21

?3 10 13

20

4 7 11 12

Page 39: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

39

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 14 15 19 21

?3 10 13

20

4 7 11 12

20

Page 40: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

40

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 14 15 19 21

?3 10 13

20

4 7 11 12

20

Page 41: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

41

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 14 15 19 21

?3 10 13 19

20

4 7 11 12

20

Page 42: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

42

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 14 15

?3 10 13 19

20

4 7 11 12

20 21

Page 43: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

43

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 14 15

?3 10 13 19

5

4 7 11 12

20 21

Page 44: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

44

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 14 15

?3 10 13 19

5

4 7 11 12

20 21

Page 45: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

45

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 14 15

?3 10 13 19

5

4 5 7 11 12

20 21

Page 46: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

46

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 14 15

?3 10 13 19

6

4 5 7 11 12

20 21

Page 47: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

47

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2 14 15

?3 10 13 19

6

4 5 6 7 11 12

20 21

Page 48: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

48

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?3 10 13 19

4 5 6 7 11 12

20 21

8

Page 49: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

49

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?3 10 13 19

4 5 6 7 11 12

20 21

8

8

Page 50: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

50

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?3 10 13 19

4 5 6 7 11 12

20 21

8

8

Page 51: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

51

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?3 10 13 19

4 5 6 7 11 12

20 21

8

8

Page 52: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

52

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?3 10 13 19

6 7 11 12

20 21

8

84 5

Page 53: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

53

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?3 10 13 19

7 8 11 12

20 21

6

64 5

Page 54: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

54

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?3 10 13 19

7 8 11 12

20 21

6

4 5

Page 55: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

55

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?3 10 13 19

7 8 11 12

20 21

6

4 5

Page 56: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

56

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?3 10 13 19

7 8 11 12

20 21

6

4 5

Page 57: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

57

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?3 10 13 19

7 8 11 12

20 21

6

4 5

3 6

Page 58: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

58

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?13 19

7 8 11 12

20 21

10

4 5

3 6

Page 59: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

59

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?13 19

7 8 11 12

20 21

4 5

3 6

10

Page 60: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

60

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?13 19

7 8 11 12

20 21

4 5

3 6

10

10

Page 61: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

61

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?13 19

7 8 11 12

20 21

4 5

3 6

10B-Baum mit MinimalerSpeicherplatz-ausnutzung

Page 62: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

62

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?13 19

7 8 11 12

20 21

4 5

3 6

10

23

Page 63: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

63

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?13 19

7 8 11 12

20 21 23

4 5

3 6

10

Page 64: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

64

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?13 19

7 8 11 12

20 21 23

4 5

3 6

10

14

Page 65: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

65

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

14 15

?13 19

7 8 11 12

20 21 23

4 5

3 6

10

14

Unterlauf

Page 66: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

66

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

15

?13 19

7 8 11 12

20 21 23

4 5

3 6

10

Unterlauf

Page 67: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

67

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

15 19

?13 20

7 8 11 12

21 23

4 5

3 6

10

Page 68: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

68

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

15 19

?13 20

7 8 11 12

21 23

4 5

3 6

10

5

Page 69: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

69

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

15 19

?13 20

7 8 11 12

21 23

4 5

3 6

10

5

Unterlauf

Page 70: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

70

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

15 19

?13 20

7 8 11 12

21 23

4

3 6

10

merge

Page 71: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

71

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

15 19

?13 20

7 8 11 12

21 23

4

3 6

10

merge

Page 72: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

72

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

15 19

?13 20

11 12

21 23

4 6 7 8

3

10Unterlauf

Page 73: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

73

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

15 19

?13 20

11 12

21 23

4 6 7 8

3

10merge

Page 74: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

74

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

15 19

?13 20

11 12

21 23

4 6 7 8

3

10merge

Page 75: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

75

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

15 19

?

11 12

21 23

4 6 7 8

3 10 13 20

Page 76: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

76

Sukzessiver Aufbau eines B-Baums vom Grad k=2

1 2

15 19

?

11 12

21 23

4 6 7 8

3 10 13 20

Schrumpfung,Freie Knoten

Page 77: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

77

B+-Baum

Referenz-schlüssel

Such-schlüssel

Page 78: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

78

Page 79: Zusatzfolien zu B-Bäumen. 2 3 4 Einfügen eines neuen Objekts (Datensatz) in einen B-Baum

79