8  Physiche Datenorganisation und Baeume

8.1 Seiten und Saetze

1. Satzlaenge twitter_user

   Attribute	Typ	Satzlaenge
   id	bigint	8 byte
   follower_count	integer	4 byte
   tweet_count	integer	4 byte
   typ	char(11)/char(5) “politician”/“lobby”	12 byte (1 byte Overhead)
   created_at	timestamp	8 byte
   twitter_name	text	12 byte
   real_name	text	18 byte
   —	—	—
   \(\sum\)		54 byte

2. Speicherplatz der Header

   • Jede Page hat 24 Byte Header
   • Jedes Tupel hat 23 Byte Header

   D.h. jedes Tupel hat 54 Byte Nutzdaten + 23 Byte Header = 77 Byte.

3. Groesse der Bloecke im PostgreSQL:

select current_setting('block_size');

block size

current_setting
8192

select count(*)
from twitter_user

Anzahl der Tupel in der Relation twitter user

count
1825

Anzahl der Tupel pro Seite ca.:

round(8192 / 77)

[1] 106

Somit ist die Anzahl der Seiten ungefaehr:

round(1825 / 106)

[1] 17

4. Anzahl der Seiten der Relation `twitter_user’:

select relname, relpages 
from pg_class
where relname = 'twitter_user'

Anzahl der Seiten fuer twitter user

relname	relpages
twitter_user	22

Also in Wirklichkeit werden 22 Seiten gebraucht statt 17 Seiten. D.h. mehr Speicher. Die Gruende dieser Abweichung sind u.a. mehr Speicher fuer:

• Pageheader
• Zeiger auf die Tupel
• Special-/Free Space in Pages
• Optionalen Zusatzelementen wie Null Bitmap in den Tuples

8.2 B-Baeume

1. B-Baum 1.1 Figure 8.1

Figure 8.1: B-Baum: A2.1

2. B-Baum 1.2 Figure 8.2

Figure 8.2: B-Baum: A2.1

8.3 \(\text{B}^{+}\)-Baeume

1. B+-Baum 3.1 Figure 8.3

Figure 8.3: B-Baum: A2.1

2. Die Elemente in der sortierten Reihenfolge in den B+ Baum einfuegen, aber nicht durch ein normales Insert, sondern direkt an das Blatt ganz rechts einfuegen. Dadurch spart man sich die look-up Operation \(\mathcal{O}(\log_m(n))\) des insert, die ein groeseres Element als die bisherigen sowieso ganz rechts in Baum ablegen wuerde.

8.4 Feedback

Punkte: 19.5/24.0
- A1: 5.0/8.0
- A2: 6.5/8.0
- A3: 8.0/8.0          

Zur Aufgabe 1:

1. typ hat Länge 4, da enum => -0.5 P.

2. Tupel Header richtig, Attribut-Größe fehlt => -0.5 P.

3. So war die Aufgabe nicht gemeint, man sollte aus den Werten der 1. und 2. das Ausrechnen => -2 P.

4. Richtig

Zur Aufgabe 2:

1. Richtig 2. Beide Varianten nicht ganz richtig:

Grundstruktur teilweise richtig: Links sehr nah an ML man müsste nur 43 und 37 tauschen (der angesprochene Leichtsinnsfehler), rechts bei Löschen eines Nicht-Blattknotens wird Element durch (längen-)lexikographisch nächst kleineres Element ersetzt, in diesem Fall die 47. Ab dann ändert sich logischerweise auch euer Baum im Vergleich zur ML.

 => -1.5 P.

Zur Aufgabe 3:

1. Diese Woche war die ML falsch, deswegen habe ich hier einen Fehler beim Korrigieren gemacht. Nur Ma zu M wäre schön.

2. Habe ich übersehen, ist richtig.