Significato delle componenti•Gestore memoria permanente•Gestore buffer•Gestore delle strutture di memorizzazione•Gestore d’accesso•Gestore affidabilità•Gestore concorrenza•Ottimizzatore•Esecutore piani d’accesso•Gestore autorizzazioni•Gestore catalogo

Riferimenti:

– P. Atzeni, S. Ceri, S. Paraboschi, R. Torlone. Basi di dati: concetti, linguaggi e architetture, McGraw-Hill, 1999 (Cap. 9.3 e Cap. 9.5) oppure Basi di dati:

architetture e linee di evoluzione, McGraw-Hill, 2003 (Cap. 1)

– A. Albano. Costruire sistemi per basi di dati, Addison Wesley Longman, Milano, 2001 (su cui sono essenzialmente basati questi lucidi) – Simulazioni dei B-tree on-line

Sull’organizzazione fisica delle basidi dati (1)

Architettura Centralizzata di un SGBD Relazionale

BaseDati

Gestore accesso Gestore strutture dimemorizzaz.

Gestore memoria permanente Gestore

concorrenza

Gestore affidabilità Ottimizzatore Esecutore piani

d’accesso Gestore

autorizzazioni Gestore

catalogo SGBD =

Sistema di Gestione di Basi di Dati

Gestore buffer buffer

Significato delle componenti

• Gestore memoria permanente

• Gestore buffer

• Gestore delle strutture di memorizzazione

• Gestore d’accesso

• Gestore affidabilità

• Gestore concorrenza

• Ottimizzatore

• Esecutore piani d’accesso

• Gestore autorizzazioni

• Gestore catalogo

Gestore di buffer e interazione con il SO

buffer pool

memoria temporanea

tabella pag. residenti:

<id_pag, posiz. buffer>

memoria gestore

buffer

pagina fisica

- pincount - dirty/nondirty - pag. fisica

Gestore della memoria permanente

• la memoria permanente è un insieme di basi di dati

• una base dati è un insieme di file

• un file è un insieme di blocchi, o pagine fisiche, numerati progressivamente e di lunghezza prefissata in cui viene memorizzata una collezione di record (tabella o indice)

• un file logico può essere realizzato come un file fisico o è la componente di un sgbd che si occupa del trasferimento dei dati persistenti dal buffer in memoria temporanea alla memoria permanente e viceversa, e “riveste” la memoria fisica permanente con una astrazione secondo cui:

• scrittura di una pagina da memoria temp. a permanente :

§ per sostituzione, quando si deve fare spazio nel buffer ad una nuova pagina richiesta da qualche applicativo

§ per gestire in modo sicuro le modifiche fatte da una transazione o la sua fine, cioè per via di commit o end_transaction

•modifica di pagina:

§ fatta direttamente sulle pagine del buffer_pool dalle componenti del sgbd di livello superiore rispetto al buffer mgr

§ la componente che ha eseguito la modifica chiede al buffer mgr di aggiornare la proprietá dirty/nondirtydella pagina modificata

•rilascio di una pagina, per fine applicativo o transazione:

§ provoca il decremento del pincount

• richiesta di una pagina

§se la pagina si trova nel buffer pool il buffer_mgr incrementa il pincount di quella pagina e restituisce alla componente che ha richiesto la pagina il riferimento a questa nel pool

§altrimenti il buffer_mgr sostituisce una pagina residente nel buffer pool:

Øtra le pagine con pincount=0 sceglie^#una pagina da eliminare, naturalmente scrivendola prima in mem. permanente se è dirty;

segnala errore se non ci sono celle con pincount a 0;

Øscrive nella cella di buffer pool la pagina fisica richiesta, il pincount a 0 e la proprietà dirty a false

Øaggiorna la tabella delle pagine residenti con la coppia

<cella_scelta, Id_pagina_fisica>

§incrementa il pincount di quella pagina e restituisce alla componente che ha richiesto la pagina il riferimento a questa nel pool

#: scelta guidata da una strategia di sostituzione (al limite LRU, LeastRecentlyUsed , sperimentalmente la migliore in caso di accessi concorrenti, ma solo in media)

Struttura interna delle pagine

intestazione o header di pagina contiene: quantità di spazio libero

riferimento all’inizio dello spazio utilizzab.

riferimento prossima pag. libera del file

vettore di indirizzamento (possibile) contiene offset ai record nella pagina

Struttura interna delle pagine

Pid, offset_in_pg

Pid, j

record

header k

riferimento ad un record o RID

• diretto j

• indiretto, ad es. tramite vettore di indirizzamento interno alla pagina

Organizzazioni dei dati

• Per realizzare un sgbd

• Per progettare una base dati

• Per ottimizzare interrogazioni

Strutture per organizza re la memorizzazione di collezioni di record in memoria permanente:

• sequenziale oppure seriale (a heap file) : i dati sono memorizzati in pagine consecutive e ordinati secondo una chiave/ non ordinati

• per chiave con metodo procedurale: i dati sono memorizzati in pagine consecutive e ordinati secondo una chiave (hash)

• per chiave con strutture ad albero: i dati sono memorizzati in strutture indice (directory) + dati; è la più usata;

• per attributi non chiave: per la ricerca di un sottoinsieme di record in base al valore di un attributo non identificatore

• per dati multidimensionali: quando i dati sono vettori che rappresentano oggetti geometrici, immagini (GIS, CAD… )

riferimento al record

• diretto: va bene per collezioni di dati statici

• indiretto, tramite vettore di indirizzamento: va bene per collezioni di dati volatili o se la memoria è gestita con spostamento dei record nelle pagine (ad esempio per mantenere ordinamento)

Tempo medio trasferimento di un blocco da memoria permanente a temporanea dipende da:

ts: seek timeo tempo di posizionamento delle testine di lettura sul cilindro richiesto del disco; parametro che incide di piú

tr: rotation latencyo tempo di latenza è il tempo di attesa per avere un blocco sotto la testina di lettura già posizionata sulla traccia tb: tempo di trasferimento di un blocco

Tempo di accesso ai dati su disco

Due livelli di memoria, memoria perm. e memoria temp. sono la soluzione piú comune per applicazioni bd; si hanno anche applicazioni ad uno o tre livelli di memoria.

un livello: tutta la base dati è gestita in memoria centrale (piccole basi dati).

Memorizzazione di collezioni di record in memoria permanente per chiave e con strutture ad albero: dati memorizzati in forma tabellare in insiemi di coppie (chiave, record-id) (indice)

Per cui, per accedere ad un valore di chiave si ha:

<indici, dati>

Organizzazione con indici No alberi bilanciati

Non si possono usare alberi binari bilanciati perché:

1. se non si fa attenzione al modo in cui i nodi dell’albero sono memorizzati nelle paginedella memoria permanente la ricerca di un elemento dell’indice può richiedere un grande numero di accessi alla memoria permanente;

2. il bilanciamento dell’albero in memoria permanenteè troppo costoso

la ricerca di un elemento dell’indice può richiedere un grande numero di accessi alla memoria permanente

ESEMPIO

un indice di 1 milione di elementi senza ipotesi su dove sono memorizzati richiede circa 20 accessi in media:

log21.000.000 ~ 20

se invece mettiamo nella stessa pagina piú nodidi un albero riduciamo gli accessi a memoria sec.; 1 milione di elementi con l'ipotesi di avere 100 nodi di albero per pagina fisica:

log1001.000.000 = 3

punto 1: i nodi di un albero binario devono essere memorizzati opportunamente nelle pagine della memoria permanente

albero binario impaginato punto 2: il bilanciamento deve essere risolto “localmente”

dall’albero binario impaginato al B-albero autori: Bayer e McCreight, 1972

Organizzazione con B-albero o B-tree

• Sono le organizzazioni più comuni nei sgbd relazionali moderni

• Il B-tree è una struttura dai aggiuntiva che viene memorizzata in pagine e gestita con i meccanismi dei sgbd

• Autori: Bayer e McCreight, 1972

Definizione di B-tree

• Ogni nodo ha la struttura seguente [p₀(k₁,r₁)p₁...p_{j -}

1(k_j,r_j)p_j]

– riè un indirizzo al record di chiave ki

– p_iè un puntatore ad un figlio

• Le chiavi k_iin ogni nodo sono ordinate

• Ogni nodo non foglia con j chiavi ha j+1 figli

• Tutte le chiavi associate ad un figlio tramite il puntatore p_isono comprese strettamente tra k_ie k_i+1: fa parte degli alberi di ricerca

Definizione di B-tree di ordine m

• la radice ha 0 <= nodi figli <= m 1 <=nro chiavi <= m-1

• ogni nodo interno ha

m/2 <= nro_figli <=m

m/2 −1 <= nro_chiavi <= m-1

• tutte le foglie si trovano allo stesso livello

Ogni nodo di albero si fa coincidere con una pagina del file in cui è memorizzato l’albero:

nodo = pagina

Estratto di un B-tree

(ordine 5)

.. ^{4 6} .. .. .. ..

.. ^{6 6} .. ^{7 9} .. .. ..

.. ^{5 0} .. ^{5 5} .. ^{6 0} .. ^{6 5} .. .. ^{6 8} .. ^{7 1} .. ^{7 4} .. ^{7 8} ..

Ricerca in B-tree di k

• k=k_r(1<=r<=j) nel nodo corrente: ok

• Se no, si segue p_i: – i=0 se k<k₁

– i=q se kq<k<kq+1, 1<=q<=j-1 – i=j se k>kj

• Ricerca per intervallo: si ripete l’operazione di ricerca di chiave per chiave nell’intervallo (efficiente per come sono fatti i B-alberi)

Complessità della ricerca in B-albero

• Il costo C_rdella ricerca di una chiave nell’albero è compreso tra 1 e h (altezza del B-tree)

• Se h è l’altezza di un B-tree e N è il numero di chiavi inserite, allora

– log_m(N+1) <= h <= log_m/2((N+1)/2)+1 il calcolo dettagliato è nei lucidi che seguono

• L’altezza dell’albero si approssima a log_m(N) (se N è grande)

Numero massimo di nodi, bmax, in un B-albero di ordine m, altezza h e nodi riempiti al massimo quindi con m figli:

livello 1: 1 livello 2: m livello 3: m * m livello 4: m²* m

……..

livello i: m^i-1

………….

livello h: m^h-1

Σ^h-1_i=0 ^mi= (m^h–1)/(m-1) = bmax

Numero minimo, bmin, di nodi in un B-albero di ordine m altezza h e nodi riempiti al minimo, quindi con m/2 figli :

livello 1: 1 livello 2: 2 livello 3: 2 * m/2 livello 4: 2 * m/2 * m/2

……..

livello i: 2 ( m/2 )^i-2

………….

livello h: 2 ( m/2 )^h-2

1+ 2∗Σ^h-2_{i=0 (}^m/2)i=1+ 2(((m/2)^h-1–1)/(m/2-1))= bmin

Per cui, numero di nodi:

1+ 2 (((m/2)^h-1–1)/(m/2-1))<= Nnodi<=(m^h–1)/(m-1) Numero minimo di chiavi per un B-albero:

radice+(bmin -1)*(min num chiavi per nodo)=radice + [1+ 2 (((m/2)^h-1–1)/(m/2-1)) –1] * (m/2 – 1) =

= 2 (((m/2)^h-1–1)/(m/2-1)) * (m/2 – 1) + radice =

= 2 ((m/2)^h-1–1) + radice = 2 (m/2)^h-1–2 +1 Numero massimo di chiavi per un B-albero:

bmax*(max num chiavi per nodo)=[(m^h–1)/(m-1)]*(m-1) = m^h –1 2 (m/2)^{h- 1}–1 <= N_chiavi<= m^h–1

Complessità della ricerca

(in B-albero di altezza h e numero di chiavi inserite N)

2 (m/2)^{h- 1}

–1 <= N <= m

–1

<= N + 1 <= m

§ log_m(N+1) <= h

§ 2 (m/2)^h-1<= N + 1 da cui: (m/2)^h-1<= (N + 1)/2 h-1 <= log_m/2((N+1)/2 ) e h <= 1 + log_m/2((N+1)/2)

§ log_m(N+1) <= h <= 1 + log_m/2((N+1)/2)

Complessità della Ricerca (cont.)

Il costo C_r della ricerca di una chiave nell’albero è compreso tra 1 e l’altezza h

Della formula precedente abbiamo preso i logaritmi:

log_m(N+1)<=h<=1+log_m/2((N+1)/2) Se N è grande l’altezza h del B-albero si approssima a log_mN

Altezza max, H, e min , h, di un B-albero in funzione della dimensione delle pagine: chiavi 10 bytes e rid 4 bytes

3,8 2,6 3,3 2,4 2,8 1,7 2,3 1,3 227 4096

4,3 2,9 3,7 2,4 3,1 2,0 2,5 1,5 113 2048

4,9 3,9 4,3 2,9 3,6 2,3 2,9 1,7 56 1024

6,0 4,1 5,1 3,5 4,2 2,7 3,4 2,1 28 512

H max h min H max h min H max h min H max h min m Dim pag

1M 1M 100k 100k 10k 10k 1000 1000

Inserimento in B-tree

ricordare: inserimento in foglia

• Si verifica se chiave è presente, se no si scende a foglia appropriata (alla albero ricerca)

• Se foglia non è complet a (cio è contiene meno di m-1 chiavi), allora vi si può inserire il record o meglio la coppia (k_j,r_j)

• Se il nodo è completo, si crea un altro nodo (splitting) e si considera il valore mediano tra le chiavi del nodo completo piú la chiave da inserire:

– il valore mediano si inserisce nel nodo padre; se il padre è completo si esegue la suddivisione (splitting) del padre (processo ricorsivo).

Inserimento e nodo saturo

• se il nodo è saturo, cioè contiene m-1 chiavi, si esegue lo

o suddivisione del nodo p’:

– si crea un altro nodo p’’ in cui si memorizzano le chiavi > della chiave di valore mediano oppure di posto mediano k_cnella sequenza (considerando chiavi del nodo e chiave da inserire) togliendole dal nodo originario

– la chiave di valore mediano k_c si inserisce ricorsivamente nel nodo padre, o meglio si inserisce

…..p’(k_c,r_kc) p”….

e se il padre è completo si esegue la suddivisione (splitting) del padree così via fino alla radice.

Inserimento in B-tree: splitting

(inserimento della chiave 70 in B-tree della slide:

“Estratto di un B-tree (ordine 5)”)

68+ 70+ 71+ 74+ 78 = 361 media= 72,2

.. 46 .. .. .. ..

.. 66 .. 71 .. 79 .. ..

.. 50 .. 55 .. 60 .. 65 ..

.. 74 .. 78 .. .. ..

.. 68 .. 70 .. .. ..

Cancellazione da B-tree di chiave k

P0. la chiave k da cancellare sia nel nodo n;

P1. se n è una foglia, si cancella k da n e si va a P3

P2. se n NON è una foglia si sostituisce k prendendo il piú piccolo (grande) fra gli elementi maggiori (minori) di k; tale chiave sostitutiva è in una foglia f, per costruzione dell’albero.

P3. controllo numero chiavi nella foglia [NB: n, oppure f ] se m/2 −1<= numero chiavi <= m-1

allora fine cancellaz.

altrimenti bisogna P4)concatenare o P5) bilanciare

Cancellazione in B-tree

(cancellazione della chiave 66: al suo posto…)

.. ⁴⁶ .. .. .. ..

.. ⁶⁶ .. ⁷⁹ .. .. ..

.. ⁵⁰ .. ⁵⁵ .. ⁶⁰ .. ⁶⁵ ..

.. ⁶⁸ .. ⁷¹ .. ⁷⁴ .. ⁷⁸ ..

…questa

…o questa

Concatenazione di nodi (P4)

processo opposto allo splitting perché unisce due nodi in un solo nodo

num. chiavi in n (al piú) = (m+1)/2 –2

Cerco un nodo q adiacente ad n nell’albero tale che num. chiavi in q (al piú) = (m+1)/2 –1

(m+1)/2 –2 +(m+1)/2 –1 + 1 = m+1-3 + 1= m–1 (ricordiamo che questo è il max num di chiavi possibile)

+1: chiave dal nodo padre

Concatenazione (cont.)

nodo padre: [… (k_j-1, r_j-1) p_j-1(k_j,r_j) p_j(k_j+1, r_j+1) p_j+1…]

nodo-1 da conc: [p₀(k₁, r₁) p₁… p_e-1(k_e, r_e) p_e] nodo-2 da conc: [p’₀(k_e+1, r_e+1) … ]

p_j-1e p_j sono puntatori ai nodi 1 e 2 i nodi 1 e 2 sono concatenati in

[p₀(k₁, r₁) p₁… p_e-1(k_e, r_e) p_e (k_j,r_j) p’₀(k_e+1, r_e+1) … ]

e nel nodo padre: [… (k_j-1, r_j-1) p_j-1(k_j+1, r_j+1) p_j+1…]

Cancellazione in B-tree: concatenazione

.. ⁴⁶ .. .. .. ..

.. ⁶⁵ .. ⁷⁰ .. ⁷⁹ .. ..

.. ⁵⁰ .. ⁵⁵ .. ⁶⁰ .. ⁶³ ..

.. ⁷⁴ .. ⁷⁸ .. .. ..

.. ⁶⁶ .. ⁶⁸ .. .. ..

.. ⁶⁵ .. ⁷⁹ .. .. ..

.. ⁶⁶ .. ⁷⁰ .. ⁷⁴ .. ⁷⁸ ..

B-tree di ordine 5 per cui: 2 <=num. chiavi<=4 cancellazione della chiave 68

prima dopo

Bilanciamento (P5)

Se non si puo fare la concatenzione(se si supera m-1).

Dati due nodi adiacenti in un B-albero, bilanciamento vuol dire ridistribuire le chiavi tra i due nodi in modo da bilanciare i nodi medesimi.

Q (padre): […, kf, …]

Q1: [p0(k1, r1)p1, …, pe-1(ke,re)pe] Q2: [p’0(k’1, r’1)p’1, …, p’j-1(k’j,r’j)pj] con j<parte-int(m/2)-1.

Si lasciano parte-int((e+j)/2) chiavi nel nodo sx, si sost. nel padre kfcon kparte-int((e+j)/2) +1e si inseriscono kfe le rimanenti chiavi nel nodo dx

Cancellazione in B-tree: bilanciamento

(cancellare la chiave 70)

.. ⁶⁵ .. ⁷¹ .. ⁷⁹ .. ..

.. ⁵⁰ .. ⁵⁵ .. ⁶⁰ .. ..

.. ⁷² .. ⁷³ .. ⁷⁴ .. ⁷⁸ ..

.. ⁶⁸ .. ⁷⁰ .. .. ..

.. ⁶⁰ .. ⁷¹ .. ^{7 9} .. ..

.. ⁶⁵ .. ⁶⁸ .. .. ..

.. ⁵⁰ .. ⁵⁵ .. .. ..

Dalla sequenza: 50, 55, 60, 65, 68, 70 ho la sequenza: 50, 55, 60, 65, 68 distribuita:

nodo padre: 60 nodo-figlio-1: 50, 55 nodo-figlio-2: 65, 68 prima

dopo

Struttura di un B-albero

Dipende dall’ordine con cui si caricano le chiavi. Si parla di densità di riempimento di un indice

Esercizio: costruire il B-albero di ordine m= 5, numero massimo figli, relativo alle due sequenze di chiavi

1) 10, 15, 30, 27, 35, 40, 45, 37, 20, 50, 55, 46, 71, 66, 74, 85, 90, 79, 78, 95, 25, 81, 68, 60, 65

2) 10, 15, 20, 25, 27, 30, 35, 37, 40, 45, 46, 50, 55, 60, 65, 66, 68, 71, 74, 78, 79, 81, 85, 90, 95

Per chiavi ordinate, sequenza 2 sopra, si ottiene un B-albero con foglie di (m+1)/2 chiavi tranne al più l’ultima:

in caso di caricamento di una sequenza ordinata si preferisce una strategia di trattamento del nodo saturo attraverso bilanciamento (invece di

Prestazioni dei B-tree

• log_m(N+1)<=h<=1+log_m/2((N+1)/2)

• Occupazione di memoria : dipende dall’ordine e da quanto sono riempiti i nodi

• Costo ricerca per chiave : tra 1 e h

• Costo ricerca per intervallo (v₁<=k<=v₂): ricerca della prima + ricerca della seconda +…+ricerca dell’ultima à in media (considerando distr. uniforme dei valori)

proporzionale a: [(v_2-v_1)/(k_max -k_min)]*N Caso piu ’ favorevole: se sono tutte nella pagina gia` in

mem.

Caso peggiore: chiave successiva a una in radice N numero

chiavi

Prestazioni dei B-tree (cont.)

Inserimento:

• se non c’è split: h letture e 1 scrittura

• se c’è split del nodo: nel caso peggiore quando si risale fino alla radice (h letture e 1+2h scritture).

Costo medio pero` inferiore è poco probabile che si arrivi fino alla radice

Prestazioni dei B-tree (cont.)

• Cancellazione:

– Se chiave e` in foglia + no bil/conc: h letture e 1 scrittura

– Se chiave e` in nodo interno + no bil/conc: h letture e 2 scritture

– Caso peggiore: per tutti i nodi del cammino si ha conc/bil: letture proporzionali a 2h e scritture a h

Indici e sgbd

•La definizione di una chiave primaria al momento di una create table di solito genera automaticamente un indice B+-albero che serve a controllare l’unicità dei valori della chiave;

• La dichiarazione di una chiave esterna non crea automaticamente un indice, ma un tale indice puo`

essere utile per verificare il vincolo referenziale corrispondente

Scelta dell’organizzazione

• L’organizzazione dipende dal sgbd

• Una volta nota l’organizzazione è necessario analizzare i suoi elementi per poter ottenere una base dati realmente efficiente

• L’efficienza deve generalmente essere

valutata sulla base delle applicazioni utente

che accedono alla base dati