Datenbanksysteme für FÜ WS 2004/2005Speicher - 1

WorzykFH Anhalt

Speicherverwaltung

• Bereitstellen von Speicherplatz bei insert und update

• Logische Dateneinheiten• Auskunft über Speicherplatz• Indizes• Bäume• Hash-Funktionen

Datenbanksysteme für FÜ WS 2004/2005Speicher - 2

WorzykFH Anhalt

Speicherverwaltung

Angebots#

Kunden#

Erstelldatum

Bearbeiter Angebot_bis_datum

Angebotstext

ta_angebot

CREATE TABLE ta_angebot (angebots# CHAR(7), kunden# NUMBER(4), erstelldatum DATE, bearbeiter CHAR(5), angebot_bis_datum DATE, angebotstext char(120));

Datenbanksysteme für FÜ WS 2004/2005Speicher - 3

WorzykFH Anhalt

Was passiert im Speicher?

insert into ta_angebot (Angebots#, Kunden#, Erstelldatum, Bearbeiter)

values ('W040/94', 0002, sysdate, 'RF');

update ta_angebot set Angebot_bis_Datum = to_date(940530,'YYMMDD'), Angebotstext = 'Dieses Angebot ist kein Aprilscherz';

Datenbanksysteme für FÜ WS 2004/2005Speicher - 4

WorzykFH Anhalt

Logische Dateneinheiten

• Datenblock, in unserem Fall 4 Kbytes groß, entspricht einer Page im Hauptspeicher

• Extent

• Segment

• Tablespace

Datenbanksysteme für FÜ WS 2004/2005Speicher - 5

WorzykFH Anhalt

DatenblockHeader

Tabellenverzeichnis

Zeilenverzeichnis

FreierSpeicherplatz19940530| Dieses Angebot ist kein Aprilscherz

ZeilendatenW039/94|0001|19940322|MWW040/94|0002|19940401|RF

Datenbanksysteme für FÜ WS 2004/2005Speicher - 6

WorzykFH Anhalt

Extent• besteht aus mehreren

zusammenhängenden Datenblöcken. • ist die Einheit, in der neuer

Speicherplatz zugewiesen wird. • wird erst wieder freigegeben, wenn

das dazugehörende Schema mit DROP gelöscht wird.

• Beim Anlegen wird der vorhandenen freien Speicherplatz optimal ausgenutzt.

Datenbanksysteme für FÜ WS 2004/2005Speicher - 7

WorzykFH Anhalt

EXTENT

Extent

Header

Tabellenverzeichnis

Zeilenverzeichnis

FreierSpeicherplatz

Zeilendaten

Header

Tabellenverzeichnis

Zeilenverzeichnis

FreierSpeicherplatz19940530| Dieses Angebot ist kein

ZeilendatenW039/94|0001|19940322|MWW040/94|0002|19940401|RF

Datenbanksysteme für FÜ WS 2004/2005Speicher - 8

WorzykFH Anhalt

Segment

Ein Segment ist die Zusammenfassung aller Extents einer logischen Speicherstruktur.

Datenbanksysteme für FÜ WS 2004/2005Speicher - 9

WorzykFH Anhalt

Segment

Header

Tabellenverzeichnis

Zeilenverzeichnis

Freier Speicherplatz

Zeilendaten

Header

Tabellenverzeichnis

Zeilenverzeichnis

Freier Speicherplatz

Zeilendaten

Extent Extent Extent

Segment für ta_angebot

Datenbanksysteme für FÜ WS 2004/2005Speicher - 10

WorzykFH Anhalt

Segmentarten

• Datensegmente

• Indexsegmente

• Rollback-Segmente

• temporäre Segmente

Datenbanksysteme für FÜ WS 2004/2005Speicher - 11

WorzykFH Anhalt

temporäre Segmente

• Bei der Bearbeitung können Zwischenergebnisse anfallen, die in temporären Segmenten gespeichert werden. Beispiele:

• CREATE INDEX• SELECT ... ORDER BY• SELECT ... DISTINCT• SELECT ... GROUP BY• Joins• Unterabfragen

Datenbanksysteme für FÜ WS 2004/2005Speicher - 12

WorzykFH Anhalt

Tablespace• steuert die Belegung von Plattenspeicher• ordnet Benutzern bestimmte

Speicherplatzquoten zu• steuert die Verfügbarkeit von Daten,

indem bestimmte Tablespaces OFFLINE gesetzt werden.

• ermöglicht, Teilsicherungen und -wiederherstellungen durchzuführen.

• verteilt Daten und Indizes unter Performance-Gesichtspunkten

Datenbanksysteme für FÜ WS 2004/2005Speicher - 13

WorzykFH Anhalt

Tablespace

Header

Tabellenverzeichnis

Zeilenverzeichnis

FreierSpeicherplatz

Zeilendaten

Header

Tabellenverzeichnis

Zeilenverzeichnis

FreierSpeicherplatz

Zeilendaten

Extent Extent Extent

Segment für ta_probe

Index SegmentRollbackSegment

Table space

Datenbanksysteme für FÜ WS 2004/2005Speicher - 14

WorzykFH Anhalt

Abfrage nach Tablespaces

select substr(file_name,1,45) "file",

bytes,

substr(tablespace_name,1,15) "tablespace"

from sys.dba_data_files;

Datenbanksysteme für FÜ WS 2004/2005Speicher - 15

WorzykFH Anhalt

vorhandene Tablespaces

file BYTES tablespace

--------------------------------------------- --------- --------------

/applications/oracle/oradata/prod/system01.db 183500800 SYSTEM

/applications/oracle/oradata/prod/oemrep01.db 5242880 OEM_REPOSITORY

/applications/oracle/oradata/prod/rbs01.dbf 31750144 RBS

/applications/oracle/oradata/prod/temp01.dbf 10485760 TEMP

/applications/oracle/oradata/prod/users01.dbf 10485760 USERS

/applications/oracle/oradata/prod/indx01.dbf 10485760 INDX

/applications/oracle/oradata/prod/reposi01.db 419430400 TS_REPOSITORY

/applications/oracle/oradata/prod/drsys01.dbf 83886080 DRSYS

/applications/oracle/oradata/prod/rs_temp.dbf 62914560 TS_TEMP

/applications/oracle/oradata/prod/system02.db 41943040 SYSTEM

/applications/oracle/oradata/prod/lehre01.dbf 41943040 TS_LEHRE

Datenbanksysteme für FÜ WS 2004/2005Speicher - 16

WorzykFH Anhalt

Indizes

• Zur Unterstützung von Suchvorgängen

• nach einem Auswahlkriterium sortiert und enthalten die Adresse des entsprechenden Datensatzes

• werden als B*-Bäume abgelegt

Datenbanksysteme für FÜ WS 2004/2005Speicher - 17

WorzykFH Anhalt

Bäume Definition

Ein Baum ist eine Menge von Punkten (Knoten) und gerichteten Verbindungen (Kanten), die eine Vorgänger-Nachfolger Relation definieren mit:

genau einem Knoten, der keinen Vorgänger und beliebig viele Nachfolger hat

beliebig vielen Knoten, die genau je genau einen Vorgänger und beliebig viele Nachfolger haben

Datenbanksysteme für FÜ WS 2004/2005Speicher - 18

WorzykFH Anhalt

Bäume Definition

Wurzel: erstes Element des Baumes

Sohn: Nachfolger eines Knoten

Vater: Vorgänger eines Knoten

innerer Knoten: hat sowohl Vorgänger als

auch Nachfolger

Blatt oder Blattknoten: hat keine

Nachfolger

Datenbanksysteme für FÜ WS 2004/2005Speicher - 19

WorzykFH Anhalt

Bäume Definition

Geordneter Baum: Die Söhne eines jeden Knotens sind angeordnet

Ordnung: Maximale Anzahl der Söhne eines Knotens

Binärer Baum: geordneter Baum mit der Ordnung 2

Datenbanksysteme für FÜ WS 2004/2005Speicher - 20

WorzykFH Anhalt

Bäume Definition

Pfad: Folge von Knoten, die der Vater-Sohn Beziehung genügen

Länge eines Pfades: Anzahl der Kanten entlang eines Pfades

Höhe: Maximale Pfadlänge zwischen Wurzel und Blättern

Tiefe: Pfadlänge eines Knotens zur WurzelNiveau: Alle Knoten mit gleicher Tiefe

Datenbanksysteme für FÜ WS 2004/2005Speicher - 21

WorzykFH Anhalt

Bäume Definition

WurzelInnerer Knoten

Nachfolger

Vorgänger

Pfad der Länge 3

Blätter

Ordnung > 2B-Baum

Ordnung = 2Binär-Baum

Höhe desBaumes

Datenbanksysteme für FÜ WS 2004/2005Speicher - 22

WorzykFH Anhalt

Binäre Bäume Beispiel

106

62 115

12

9

6

46

58

33

88

127

47

71

73

102

94

131

45

24

Nullzeiger

Datenbanksysteme für FÜ WS 2004/2005Speicher - 23

WorzykFH Anhalt

Bäume suchen

Algorithmus:gibt es noch einen Teilbaum zu durchsuchen

nein -> nicht gefunden

ist der Schlüssel kleiner als die Wurzel (des Teilbaumes)ja -> linken Teilbaum durchsuchen

ist der Schlüssel größer als die Wurzel (des Teilbaumes)ja -> rechten Teilbaum durchsuchen

gefunden

Datenbanksysteme für FÜ WS 2004/2005Speicher - 24

WorzykFH Anhalt

Bäume einfügen

Algorithmus:Nullzeiger (= Noch keine Wurzel vorhanden)

ja -> Schlüssel einfügen, linker u. rechter Sohn = Nullzeiger

ist der Schlüssel kleiner als die Wurzel (des Teilbaumes)ja -> im linken Teilbaum einfügen

ist der Schlüssel größer als die Wurzel (des Teilbaumes)ja -> im rechten Teilbaum einfügen

Schlüssel schon vorhanden

Datenbanksysteme für FÜ WS 2004/2005Speicher - 25

WorzykFH Anhalt

Binäre Bäume entfernen

Algorithmus

Kein Sohn vorhanden -> entfernen

einen Knoten als Sohn -> den zu

entfernenden Knoten durch den Sohn

ersetzen

zwei Teilbäume als Söhne -> durch das

Minimum des rechten Teilbaumes ersetzen

Datenbanksysteme für FÜ WS 2004/2005Speicher - 26

WorzykFH Anhalt

Binäre Bäume Beispiel

106

62 115

9

6

46

58

33

88

127

47

71

73

102

94

131

45

24

Nullzeiger

72

12

Datenbanksysteme für FÜ WS 2004/2005Speicher - 27

WorzykFH Anhalt

Binäre Bäume Anwendungsbeispiel

Syntax:=

x /

+

-

b

a

2

a

-

2

0.5

*

*

b

4

c*

x:=(-b+(-b2-4*a*c)0.5)/(2*a)

Datenbanksysteme für FÜ WS 2004/2005Speicher - 28

WorzykFH Anhalt

Binäre Bäume Anwendungsbeispiel

Index

19231

19126

19237

19214

18155

19438

19348

1 2 3 4 5 6 7 8 9Codd Dijkstra Floyd Lehmann Lovelace Turing Weizenbaum Wirth Zuse1923 1930 1943 1921 1815 1912 1923 1934 1910

19302

19109

Datenbanksysteme für FÜ WS 2004/2005Speicher - 29

WorzykFH Anhalt

Binäre Bäume Anwendungsbeispiel

Spielbaum

A.K. Dewdney: Der Turing Omnibus

Datenbanksysteme für FÜ WS 2004/2005Speicher - 30

WorzykFH Anhalt

B-Bäume

Ein B-Baum mit N-1 Schlüsseln hat N Blätter

Höhe

I S1 I S2 . . . Sn I

Höhe h:

Höhe 1:

I S1 I S2 . . . Sn I

I S1 I S2 . . . Sn I I S1 I S2 . . . Sn I I S1 I S2 . . . Sn I

Datenbanksysteme für FÜ WS 2004/2005Speicher - 31

WorzykFH Anhalt

B*-BäumePrinzip

• B*-Bäume:– nur Datenblöcke mit höchstem

Rang enthalten Schlüssel + Daten– alle anderen Datenblöcke

Schlüssel und Zeiger, aber keine weiteren Daten

Datenbanksysteme für FÜ WS 2004/2005Speicher - 32

WorzykFH Anhalt

HashverfahrenBerechnung des Speicherplatzes

aus dem Schlüssel

Beispiel: die erste Ziffer gibt den Speicherplatz an

Es gibt mehrfach belegte Speicherplätze

106 62 12 9 58 71 46 115 45 6 73 24 131 47 102 33 127 94 88

10612

115131102127

24 33 464547

58 662

7173

88 994

Datenbanksysteme für FÜ WS 2004/2005Speicher - 33

WorzykFH Anhalt

HashverfahrenDivisions-Rest-Methode

h(k) = k mod(N)

Für N haben sich Primzahlen ausgezeichnet bewährt

106 62 12 9 58 71 46 115 45 6 73 24 131 47 102 33 127 94 88

N=20 62102

24 45 106466

47127

88 9 7111

12 7333

94 115 18

N=29 58 88 6233

6 94 9 127 12 71 73131102

45 46 47 106 24 115

Datenbanksysteme für FÜ WS 2004/2005Speicher - 34

WorzykFH Anhalt

Zusammenfassung

• Speichereinheiten– Datenblock– Extent– Segment– Tablespace

• Suchen über Index• Index wird als Baum gespeichert