1 Physikalische Datenorganisation RecordDatensatz fester oder variabler Länge mit Feldern...

1

Physikalische DatenorganisationRecord Datensatz fester oder variabler Länge

mit Feldern bestimmten Typs

Block Speichereinheit im Hintergrundspeicher (29 - 212 Bytes)

File Menge von Blöcken

Pinned record Blockadresse + Offset

Unpinned record Blockadresse + RecordschlüsselBlockadresse + Index (Tupelidentifikator)

2

Tupelidentifikator: Verschieben innerhalb der Seite

4711 2

5001 Grundzüge ...

5041 Ethik ...

TID

1 2 3

Seite 4711

4052 Logik ...

4052 Mathematische Logik ...

3

Tupelidentifikator: Verdrängen auf andere Seite

4052 Mathematische Logik ...

4711 2

5001 Grundzüge ...

5041 Ethik ...

TID

1 2 3

Seite 4711

1 2 3

Seite 4812

4052 Mathematische Logik für Informatiker...

4812 3

4052 Mathematische Logik

4

Implementierung des E-R-Modells

• pro Entity ein Record mit den Attributen als Datenfelder

• pro Relationship ein Record mit den TIDs der beteiligten Entities

5

• INSERT: Einfügen eines Records

• DELETE: Löschen eines Records

• MODIFY: Modifizieren eines Records

• LOOKUP: Suchen eines Records

Speicher-Operationen

6

Heap-File

• INSERT: Record am Ende einfügen

• DELETE: Lösch-Bit setzen

• MODIFY: Record überschreiben

• LOOKUP: Gesamtes File durchsuchen

7

Hashing

• alle Records sind auf Buckets verteilt• ein Bucket besteht aus einer verzeigerten Liste von Blöcken• Bucketdirectory enthält Einstiegsadressen• Hashfunktion (angewandt auf Schlüssel) liefert zuständige Liste• Bei N Buckets bildet die Hashfunktion einen Schlüssel auf eine

Zahl zwischen 0 und N-1 ab.• Pro Datenrecord ein Frei/Belegt-Bit

8

1 0

1 1

1 1

1 1

Peter

Thomas

Melanie

Ute

Kurt

Fritz

Susanne

Eberhard

Karl

Beate

1 0 Eva

0

1

2

3

4

1 1 1 0

Beispiel für Hashorganisation (|v| mod 5)

9

Beispiel für Hash-Funktion

Sei N die Anzahl der Buckets. Fasse den Schlüssel v als k Gruppen von jeweils n Bits auf. Sei di die i-te Gruppe als natürliche Zahl interpretiert:

dk dk-1 d2 d1

h(v) = (dk + dk-1 + . . . + d2 + d1) mod N

10

Hash-Operationen für Schlüssel v

• LOOKUP:Berechne h(v) = i. Lies den für i zuständigen Directory-Block ein, und beginne bei der für i vermerkten Startadresse mit dem Durchsuchen aller Blöcke.

• MODIFY:Falls Schlüssel beteiligt: DELETE und INSERT durchführen. Andernfalls: LOOKUP durchführen und dann überschreiben.

• INSERT:Zunächst LOOKUP durchführen. Falls Satz mit v vorhanden: Fehler. Sonst: Freien Platz im Block überschreiben und ggf. neuen Block anfordern.

• DELETE:Zunächst LOOKUP durchführen. Bei Record Löschbit setzen.

11

1 0

1 1

1 1

1 1

Peter

Thomas

Melanie

Ute

Kurt

Fritz

Susanne

Eberhard

Karl

Beate

1 0 Eva

0

1

2

3

4

1 1 1 0

Paul einfügen

Hashorganisation: Ausgangslage h(s) = |s| mod 5

12

1 0

1 1

1 1

1 1

Peter

Thomas

Melanie

Ute

Kurt

Fritz

Susanne

Eberhard

Karl

Beate

1 0 Eva

0

1

2

3

4

1 1 1 0

1 0 Paul

Hashorganisation: nach Einfügen von Paul

Kurt umbenennen nach Curdt

13

Peter

1 0

1 1

1 1

0 1

Thomas

Melanie

Ute

Fritz

Susanne

Eberhard

Karl

Beate Curdt

1 0 Eva

0

1

2

3

4

1 1 1 1

1 0 Paul

Hashorganisation: nach Umbenennen von Kurt in Curdt

14

Probleme beim Hashing

durch dynamisch sich ändernden Datenbestand:• Blocklisten werden immer länger• Reorganisation erforderlich

15

Erweiterbares Hashing

• Hashfunktion liefert Binärstring• verwende geeigneten Prefix des Binärstring als Adresse

16

Beispiel für erweiterbares Hashing

MatNr Name Hashwert2125 Sokrates 1011001000012126 Russel 0111001000012127 Kopernikus 1111001000012129 Descartes 100010100001

Hashwert = umgekehrte Binärdarstellung von Matrikelnummer

Ein Datenblock enthalte zwei Records

17

Beispiel für erweiterbares Hashing

x

212521262127

1 011001000010 111001000011 11100100001

d p

h(x)

0

(2126, Russel, C4, 232)

(2125, Sokrates, C4, 226)

(2127, Kopernikus, C3, 310)

1

t = 1

t´= 1

t´= 1

2125 Sokrates1011001000012126 Russel0111001000012127 Kopernikus1111001000012129 Descartes100010100001Sokrates, Russel, Kopernikus einfügen

Descartes einfügen Bucket 1 läuft über Setze globale Tiefe t:=2

18

Beispiel für erweiterbares Hashing

x

2125212621272129

10 1100100001 01 110010000111 110010000110 0010100001

d p

h(x)

00

(2126, Russel, C4, 232)

(2125, Sokrates, C4, 226)

(2127, Kopernikus, C3, 310)

01t´= 2

t´= 1

t = 2

10

11

(2129, Descartes, C3, 312)

t´= 2

2125 Sokrates1011001000012126 Russel0111001000012127 Kopernikus1111001000012129 Descartes100010100001

19

Defizite beim Hashing

• Keine Sortierung

• Keine Bereichsabfragen

20

ISAM (Index sequential access method)

• Index-Datei mit Verweisen in die Hauptdatei.• Index-Datei enthält Tupel < Schlüssel,Blockadresse>,

sortiert nach Schlüsseln.• Liegt < v, a > in der Index-Datei, so sind alle Record-Schlüssel

im Block, auf den a zeigt, größer oder gleich v.

21

ISAM-Operationen für Record mit Schlüssel v

• LOOKUP (für Schlüssel v):Suche in Index-Datei den letzten Block mit erstem Eintrag v2 v. Suche in diesem Block das letzte Paar (v3, a) mit v3 v. Lies Block mit Adresse a und durchsuche ihn nach Schlüssel v.

• MODIFY:Zunächst LOOKUP. Falls Schlüssel an Änderung beteiligt: DELETE + INSERT. Sonst: Record ändern, Block zurückschreiben.

• INSERT:Zunächst LOOKUP. Falls Block noch Platz für Record hat: einfügen. Falls Block voll ist: Nachfolgerblock oder neuen Block wählen und Index anpassen.

• DELETE:Analog zu INSERT

22

1 1 1 1 Anton Doris Karl Paul

1 1 0 0 Sabine Theo

1 1 Anton Berta

1 1 Doris Emil

1 1 Karl Norbert

1 1 Paul Peter

1 0 Sabine

1 1 Theo Ute

Manfred einfügen

Index-Organisation: Ausgangslage

23

1 1 1 1 Anton Doris Karl Norbert

1 1 1 0 Paul Sabine

1 1 Anton Berta

1 1 Doris Emil

1 1 Karl Manfred

1 0 Norbert

1 1 Paul Peter

1 1 Sabine

Theo

1 1 Theo Ute

Index-Organisation: nach Einfügen von Manfred

24

Sekundär-Index

Sekundärindex besteht aus Index-File mit Einträgen der Form <Attributwert, Adresse>.

25

Sekundär-Index für Gewicht

68 71 72 78 83

26

Beispiel zur physikalischen Speicherung

Gegeben seien 300.000 Records mit folgenden Angaben:

Die Blockgröße betrage 1024 Bytes.

AttributAttribut BytesBytesPers-Nr. 15Vorname 15Nachname 15Straße 25PLZ 5Ort 25

Platzbedarf pro Record: 100 Bytes.

27

Fragen zur Zahl der Records

Wieviel Daten-Records passen in einen zu 100% gefüllten Datenblock?

1024 / 100 = 10

Wieviel Daten-Records passen in einen zu 75% gefüllten Datenblock?

10 * 0,75 = 7-8

Wieviel Schlüssel / Adresspaare passen in einen zu 100% gefüllten Indexblock?

1.024 / (15+4) = 53

Wieviel Schlüssel / Adresspaare passen in einen zu 75% gefüllten Indexblock?

1.024 / (15+4)*0,75 40

28

Heapfile versus ISAM

Welcher Platzbedarf entsteht beim Heapfile?

300.000 / 10 = 30.000 Blöcke

Wieviel Blockzugriffe entstehen im Mittel beim Heapfile?

30.000 / 2 = 15.000

Welcher Platzbedarf entsteht im Mittel bei ISAM?

300.000 / 7,5 40.000 zu 75% gefüllte Datenblöcke +

40.000 / 40 1.000 zu 75% gefüllte Indexblöcke

Wieviel Blockzugriffe entstehen im Mittel bei ISAM?

log2(1.000) + 1 11 Blockzugriffe

29

B*-Baum

• Jeder Weg von der Wurzel zu einem Blatt hat dieselbe Länge.• Jeder Knoten außer der Wurzel und den Blättern hat

mindestens k Nachfolger.• Jeder Knoten hat höchstens 2 • k Nachfolger.• Die Wurzel hat keinen oder mindestens 2 Nachfolger.

30

B*-Baum-Adressierung

Ein Knoten wird auf einem Block gespeichert

Ein Knoten mit j Nachfolgern (j 2•k)speichert j Paare von Schlüsseln und Adressen (s1, a1), . . . , (sj, aj).

Es gilt s1 s2 . . . sj.

Eine Adresse in einem Blattknoten führt zum Datenblock mit den restlichen Informationen zum zugehörigen Schlüssel

Eine Adresse in einem anderen Knoten führt zu einem Baumknoten

31

Einfügen in B*Baum

eingefügt werden soll: 45

312217

774217

79774742 6153

32

Einfügen in B*Baum

eingefügt werden soll: 45

Block anfordern

312217

774217

79774742 6153

Überlaufblock verteilen

33

Einfügen in B*Baum

eingefügt werden soll: 45

Vorgänger korrigieren

312217

774217

79774742

6153

34

Einfügen in B*Baum

eingefügt wurde: 45

312217

534217 77

79774542

6153

47

35

27 55 12 94 37 88 72 39 25 88 74 58 64

Sequenz für B*-Baum mit k=2

36

27

27

37

27

27 55

38

27 55

27 55

39

27 55

27 55 12

40

12 27 55

27 55 12

41

12 27 55

27 55 12 94

42

12 27 55 94

27 55 12 94

43

12 27 55 94

27 55 12 94 37

44

12 27 55 94

27 55 12 94 37

45

12 27 37 55 94

27 55 12 94 37

46

12 27 37 55 94

12 55

27 55 12 94 37

47

12 27 37 55 94

12 55

27 55 12 94 37 88

48

12 27 37 55 88 94

12 55

27 55 12 94 37 88

49

12 27 37 55 88 94

12 55

27 55 12 94 37 88 72

50

12 27 37 55 72 88 94

12 55

27 55 12 94 37 88 72

51

12 27 37 55 72 88 94

12 55

27 55 12 94 37 88 72 39

52

12 27 37 39 55 72 88 94

12 55

27 55 12 94 37 88 72 39

53

12 27 37 39 55 72 88 94

12 55

27 55 12 94 37 88 72 39 25

54

12 27 37 39 55 72 88 94

12 37 55

27 55 12 94 37 88 72 39 25

55

12 25 27 37 39 55 72 88 94

12 37 55

27 55 12 94 37 88 72 39 25

56

12 25 27 37 39 55 72 88 94

12 37 55

27 55 12 94 37 88 72 39 25 91

57

12 25 27 37 39 55 72 88 94

12 37 55 88

27 55 12 94 37 88 72 39 25 91

58

12 25 27 37 39 55 72 88 91 94

12 37 55 88

27 55 12 94 37 88 72 39 25 91

59

12 25 27 37 39 55 72 88 91 94

12 37 55 88

27 55 12 94 37 88 72 39 25 91 74

60

12 25 27 37 39 55 72 74 88 91 94

12 37 55 88

27 55 12 94 37 88 72 39 25 91 74

61

12 25 27 37 39 55 72 74 88 91 94

12 37 55 88

27 55 12 94 37 88 72 39 25 88 74 58

62

12 25 27 37 39 55 58 72 74 88 91 94

12 37 55 88

27 55 12 94 37 88 72 39 25 88 74 58

63

12 25 27 37 39 55 58 72 74 88 91 94

12 37 55 88

27 55 12 94 37 88 72 39 25 88 74 58 64

64

12 25 27 37 39 72 74 88 91 94

12 37 72 88

27 55 12 94 37 88 72 39 25 88 74 58 64

55 58

65

12 25 27 37 39 72 74 88 91 94

12 37 72 88

27 55 12 94 37 88 72 39 25 88 74 58 64

55 58 64

66

12 25 27

12 37

37 39 55 58 64 72 74 88 91 94

55 72 88

27 55 12 94 37 88 72 39 25 88 74 58 64

67

12 25 27

12 37

37 39 55 58 64 72 74 88 91 94

55 72 88

12 55

27 55 12 94 37 88 72 39 25 88 74 58 64

68

12 25 27

12 37

37 39 55 58 64 72 74 88 91 94

55 72 88

12 55

27 55 12 94 37 88 72 39 25 88 74 58 64

Sequenz eingefügt

69

Löschen in B*Baum

312217

774217

7977534742 61

Entferne 53

70

Löschen in B*Baum

312217

774217

7977614742

Entferne 79

71

Löschen in B*Baum

2217

613117

77614731

Entferne 47

72

Löschen in B*Baum

312217

7717

7977

Entferne 77

73

Löschen in B*Baum

2217

3117

7931

Entferne 22

74

Löschen in B*Baum

793117

75

Fragen zum B*Baum

Wie groß ist k ?Blockgröße / (Schlüssel / Adresspaar-Größe) =

1024 / (15+4) / 2 = 26

Wieviel Söhne hat eine zu 50 % gefüllte Wurzel ?

26

Wieviel Söhne hat ein zu 75 % gefüllter Knoten ?

39

Wieviel zu 75 % gefüllte Datenblöcke sind erforderlich ?

300.000 / 7,5 40.000

76

Platzbedarf B*Baum

Wieviel Blöcke belegt der B*Baum ?

Höhe Knoten Zeiger aus Knoten0 1 261 26 26 * 39 = 1.0142 26*39 26*39*39 = 39.546

drei Ebenen reichen aus Platzbedarf = 1 + 26 + 26*39 + 39.546 40.000 Blöcke

Wieviel Blockzugriffe sind erforderlich ?

4

77

Hashing versus B*Baum

Welcher Platzbedarf entsteht beim Hashing, wenn dieselbe Zugriffszeit erreicht werden soll wie beim B*Baum?

4 Blockzugriffe = 1 Directory-Blockzugriff + 3 Datenblockzugriffe. Buckets bestehen im Mittel aus 5 Blöcken. von 5 Blöcken sind 4 voll und der letzte halb voll. 4,5 * 10 = 45 Records pro Bucket 300.000 / 45 = 6666 Buckets erforderlich 6666 / (1024 / 4) = 26 Directory-Blöcke Platzbedarf = 26 + 5 * 6.666 = 33.356

78

B*Baum versus Hashing

B*Baum Hashing

Vorteile Dynamisch SchnellSortierung möglich platzsparend

Nachteile Speicheroverhead keine Sortierungkompliziert Neuorganisation

79

Mehrdimensionale Suchstrukturen

Alter zwischen 20 und 30

Einkommen zwischen 2000 und 3000

PLZ zwischen 40000 und 50000

80

Query-Rechteck

y2

y1

y

xx1 x2

E

D

C

B

G

F H I

K

AJ

81

k-d-Baum

zur Verwaltung von mehrdimensionalen Datenpunkten

Verallgemeinerung des binären Suchbaumsmit k-dimensionalem Sortierschlüssel

Homogene Variante: Baumknoten enthält Datenrecord + Zeiger

Inhomogene Variante: Baumknoten enthält Schlüssel + ZeigerBlätter enthalten Zeiger auf Datenrecord

Ebene i modulo k diskriminiert bzgl. Dimension i

x

y

z

82

2-d-Baum

Im 2-dimensionalen Fall gilt für Knoten mit Schlüssel [x/y]:

im linken Sohn im rechten Sohn

Auf ungerader Ebene alle Schlüssel x alle Schlüssel > x

Auf gerader Ebene alle Schlüssel y alle Schlüssel > y

83

2-d-Baum

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1

2

3

4

5

6

7

8

9

10

A

C

B

D

E

FG

H

84

Beispiel für 2-d-Baum

D 6/2 H 8/5

C 9/4

B14/3B 14/3

A 5/6

G 1/8 F 12/7

E 7/9

bzgl. y kleiner

bzgl. x kleiner

bzgl. y kleiner

bzgl. y grösser

bzgl. y grösser

bzgl. x grösserbzgl. x grösser

Ebene 0

85

Beispiel für 2-d-Baum

D 6/2 H 8/5

C 9/4

B14/3B 14/3

A 5/6

G 1/8 F 12/7

E 7/9

bzgl. y kleiner

bzgl. x kleiner

bzgl. y kleiner

bzgl. y grösser

bzgl. y grösser

bzgl. x grösserbzgl. x grösser

Insert z.B. füge Record [3/9]

I 3/9

86

Beispiel für 2-d-Baum

D 6/2 H 8/5

C 9/4

B14/3B 14/3

A 5/6

G 1/8 F 12/7

E 7/9

bzgl. y kleiner

bzgl. x kleiner

bzgl. y kleiner

bzgl. y grösser

bzgl. y grösser

bzgl. x grösserbzgl. x grösser

Exact Match z.B. finde Record [15/5]

87

Beispiel für 2-d-Baum

D 6/2 H 8/5

C 9/4

B14/3B 14/3

A 5/6

G 1/8 F 12/7

E 7/9

bzgl. y kleiner

bzgl. x kleiner

bzgl. y kleiner

bzgl. y grösser

bzgl. y grösser

bzgl. x grösserbzgl. x grösser

Partial Match z.B. finde alle Records [x/y] mit x=7

88

Beispiel für 2-d-Baum

D 6/2 H 8/5

C 9/4

B14/3B 14/3

A 5/6

G 1/8 F 12/7

E 7/9

bzgl. y kleiner

bzgl. x kleiner

bzgl. y kleiner

bzgl. y grösser

bzgl. y grösser

bzgl. x grösserbzgl. x grösser

Range-Query z.B. finde alle Records [x/y] mit 8 x 13, 5 y 8

89

Beispiel für 2-d-Baum

D 6/2 H 8/5

C 9/4

B14/3B 14/3

A 5/6

G 1/8 F 12/7

E 7/9

bzgl. y kleiner

bzgl. x kleiner

bzgl. y kleiner

bzgl. y grösser

bzgl. y grösser

bzgl. x grösserbzgl. x grösser

Best Match z.B. finde nächsten Nachbarn zu [7/3]

90

2-d-Baum

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1

2

3

4

5

6

7

8

9

10

A

C

B

D

E

FG

H

91

Inhomogene Variante

92

Partitionierungen

93

Gitterverfahren mit konstanter Gittergröße

94

Grid File

Alternative zu fester Gittergröße

1981 vorgestellt von Hinrichs & Nievergelt

2-Platten-Zugriffsgarantie

Bei k-dimensionalen Tupeln:

• k Skalen zum Einstieg ins Grid-Directory (im Hauptspeicher)

• Grid Directory zum Finden der Bucket-Nr. (Hintergrundspeicher)

• Bucket für Datensätze (Hintergrundspeicher)

95

Grid File im 2-dimensionalen Fall

Alle Records der roten Gitterzelle sind im Bucket mit Adresse G[1,2]

0

y[i],i=0,.. max_y

3030

2500

2050

800

y

30 40 85 120 x

x x[i],i=0,.. max_x0 30 40 85 120

y0 800 2050 2500 3030

Region: benachbarte Gitterzellen

Gitterzelle: rechteckiger Teilbereich

Bucket: speichert Records einer Region

96

Bucket Directory

0 30 40 85 120

0 1 2 3 4

43210

303025002050

8000

Suche Record [35 / 2400]

Befrage Skalen

asp07nk99jh056509

aasdf0cß03j400d0v

9v8asßfimo98csi98a

dxcvß98dspa0s9fxc0

wi00808ß3jsßsa9ßß

Lade G[1,2] vom Bucketdirectory

Lade Datenblock

97

1.000.000 Datenrecords

4 Datenrecords passen in ein Bucket

X-Achse und Y-Achse habe 500 Unterteilungen

250.000 Einträge im Bucketdirectory

4 Bytes pro Adresse + 1.024 Bytes pro Block

250 Zeiger pro Directory-Block

1.000 Directory-Blöcke

i 249: G[i,j] befindet sich auf Block 2*j als i-te Adresse

i > 249: G[i,j] befindet sich auf Block 2*j+1 als (i-250)-te Adresse

Beispiel für Bucket Directory

....................................

.

0 249 499

....................................

.

....................................

.

....................................

.....................................

.

.

.

.210

G[280,2] auf Block 5 an Position 30

....................................

.

....................................

.

98

Bucket-Überlauf

Eine Zelle in Region

Mehrere Zellen in Region

99

Aufspalten der Regionen

8

6

4

2

2 4 6 8 10 12 14

Insert A = [5 / 6]

100

Aufspalten der Regionen

8

6

4

2

2 4 6 8 10 12 14

A

A Insert B = [14 / 3]

101

Aufspalten der Regionen

8

6

4

2

2 4 6 8 10 12 14

A

B

A B Insert C = [9 / 4]

102

Aufspalten der Regionen

8

6

4

2

2 4 6 8 10 12 14

A

C

B

B CA Insert D = [6 / 2]

103

Aufspalten der Regionen

8

6

4

2

2 4 6 8 10 12 14

A

C

B

B CA D

D

Insert E = [7 / 9]

104

Aufspalten der Regionen

B C

8

6

4

2

2 4 6 8 10 12 14

E

A

C

B

D

A E

D

Insert F = [12 / 7]

105

Aufspalten der Regionen

B C

8

6

4

2

2 4 6 8 10 12 14

E

A

C

B

FF

D

A E

D

Insert G = [1 / 8]

106

Aufspalten der Regionen

B C

8

6

4

2

2 4 6 8 10 12 14

E

A

C

B

FF

D

G A E

D

G

Insert A = [5 / 6]

107

Dynamik des Grid Directory

300

200 10 50

Insert A=[12 / 280]

3 Datenrecords pro Bucket

108

Dynamik des Grid Directory

10 50

300

200

A

10 50

300

200

300

200 10 50

Insert B=[25 / 220]

109

Dynamik des Grid Directory

10 50

300

200

A

B

10 50

300

200

300

200 10 50

Insert C=[45 / 270]

110

Dynamik des Grid Directory

10 50

300

200

A

B

C

10 50

300

200

300

200 10 50

Insert D=[22 / 275]

111

Dynamik des Grid Directory

300

200

10 30 50

300

200

A

B

C

10 50

300

200

D

10 30 50

Insert E=[24 / 260]

112

Dynamik des Grid Directory

250

200

C

300

10 30 50

A

B

10 50

300

200

D

10 30 50

300

200

E

250

Insert F=[26 / 280]

113

Dynamik des Grid Directory

10 30 50

300

200

30 50

10 20 30

250

200

A

B

CD

10 30 50

300

200

E

250

300 F

250

200

300

Directory Blockvergröbern

114

Dynamik des Grid Directory

10 20 30

250

200

A

B

C

10 30 50

300

200

D

10 30 50

300

200

E

250

300 F

30 50

300

200

115

Vereinigung von Regionen

bei zu geringer Bucketauslastung:

• Benachbarte Regionen vereinigen

• Vereinigung muß Rechteck ergeben

Vereinigung wird ausgelöst

• wenn Bucket < 30 % Auslastung

• wenn vereinigtes Bucket < 70 % Auslastung

116

Nearest Neighbor

Q

P

R

117

Verwaltung von geometrischen Objekten

Grid File unterstützt Range-Query

bisher: k Attribute

Jetzt: k-dimensionale Punkte

118

Verwaltung von Intervallen

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1

2

3

4

5

E

A

B

C

D

F

A

[Anfang / Ende]

E

A

B C

D F

Besser: [Mittelpunkt / halbe Länge]

119

Query-Punkt gegen Intervall

Punkt p liegt im Intervall mit Mitte m und halber Länge d

m-d p m+d

m-d m+dm

120

Query-Punkt gegen Intervall

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1

2

3

4

5

E

A

B

C

D

F

E

A

B C

D F

Punkt p liegt im Intervall mit Mitte m und halber Länge d

m-d p m+d p=5 m-d 5 m+d

121

Query-Intervall gegen Intervall

Intervall mit Mitte s und halber Länge t schneidet Intervall mit Mitte m und halber Länge d

m-d s+t und s-t m+d

m-d m+d

s+ts-t

122

Query-Intervall gegen Intervall

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1

2

3

4

5

E

A

B

C

D

F

E

A

B C

D F

Intervall mit Mitte s und halber Länge t schneidet Intervall mit Mitte m und halber Länge d

m-d s+t und s-t m+d s=10, t=1 m-d 11 und 9 m+d

123

Query-Rechteck gegen Rechteck

Stelle Rechteck durch vierdimensionalen Punkt dar