Tema 7 Flashcards
(19 cards)
Explicació Índexs
- Accessos a disc són lents. No podem estar llegint cada bloc (pàgina) de dades fins a trobar el registre buscat.
- Necessitat d’estructures que ens permetin fer les cerques més ràpides. Necessitat dels índexs.
- Índex. Són estructures formades per registres (anomenats entrades) amb dos camps: el camp que indexen i un apuntador (RID) al número de pàgina on hi ha les dades que busquem.
Quins mètodes d’accés a les taules tenim?
- Una de les funcions dels SGBD és proporcionar l’accés a les dades que gestionen. Les dades sempre estan en les taules (fitxers dins el disc dur) que el SGBD veu a través d’un espai virtual.
- Per simplificar suposarem que tots els accessos es fan a una única taula. No considerarem el cas en que prèviament s’han de reunir vàries taules.
- Distingim dos tipus d’accessos:
● Accessos per posició.
● Accessos per valor.
Explicació accessos per posició directes
- Els accessos per posició es fan a partir d’un número de pàgina virtual. Poden ser de dos tipus: directes i seqüencials.
- Accessos directes per posició. Consisteix en obtenir una pàgina de la qual sabem el seu número de pàgina.
Exemple:
INSERT INTO ALUMNES (111,’Pere’,’Pi’,’Nou 23’,’Girona’). Aquesta sentència es realitza molt ràpidament ja que el SGBD manté el número de pàgina on hi ha espai lliure per inserir files. Si suposem que és la pàg 5, el SGBD converteix el número de pàgina virtual a la direcció física on es troba dins el disc dur. Amb un sol accés el SO fa una operació de E/S accedint a la plana.
Explicació accessos per posició Seqüencials
- Els accessos per posició es fan a partir d’un número de pàgina virtual. Poden ser de dos tipus: directes i seqüencials.
- Accessos seqüencials per posició. Consisteix en anar obtenint les pàgines seguint l’ordre definit pels seus números de pàgina virtual Exemple:
SELECT * FROM ALUMNE. S’accedeix a la primera pàgina virtual, el SGBD converteix el número de pàgina virtual a la direcció física on es troba dins el disc dur i es realitza un accés directe per posició en aquesta pàgina. Una vegada obtinguts tots els registres de la pàgina 1, seqüencialment s’accedeix a la pàgina virtual 2 i es van realitzant les mateix operacions que hem fet per la pàgina 1.
Com s’implementen els accessos per posició?
- Per la implementació dels accessos per posició els SGBD es valen del Sistema Operatiu.
- Accés directe per posició. Només cal que el SGBD transformi el número de pàgina virtual en adreces de pàgines reals del disc dur per tal de que el SO pugui fer l’operació d’ES de la pàgina.
- Accés seqüencial per posició. El mateix procés anterior serveix per anar accedint a totes les pàgines, des de la primera fins la darrera
Expliscació accessos per valor directes
- Els accessos per valor consisteixen en obtenir totes les files que contenen un valor determinat en un cert camp. Poden ser de dos tipus: directes i seqüencials.
- Accessos directes per valor. Consisteix en fer un accés directe a totes aquelles files que un dels seus atributs compleix una condició.
Exemples:
SELECT * FROM ALUMNE WHERE Població=“Girona”.
UPDATE EMPLEAT SET Sou=25000 WHERE Dept=5
DELETE FROM EMPLEAT WHERE Dept=10
-L’accés directe per valor és molt més complex. Ja veurem com s’implementa.
Explicació accessos per valor seqüencials
- Els accessos per valor consisteixen en obtenir totes les files que contenen un valor determinat en un cert camp. Poden ser de dos tipus: directes i seqüencials.
- Accessos seqüencials per valor. Consisteix en obtenir diverses files per l’ordre dels valors d’un atribut:
SELECT * FROM ALUMNE ORDER BY Cognom1
SELECT * FROM EMPLEAT WHERE Numdep >10 and Numdep <20
UPDATE EMPLEAT SET Sou=25000 WHERE Numdep >10 and Numdep <20 DELETE FROM EMPLEAT WHERE Numdep >10 and Numdep <20 - L’accés seqüencial per valor és molt més complex. Ja veurem com s’implementa
Explicació accessos per diversos valors
- A més d’aquest accessos simples per valor podem considerar altres casos
- Accés directe per varis valors.
Exemple
SELECT * FROM ALUMNE WHERE Nom=‘Pere’ and Cognom1=‘Pi’ - Accés seqüencial per varis valors.
Exemple
SELECT * FROM ALUMNE ORDER BY Cognom1, cognom2, nom - Els accessos per diferents valors poden ser mixtos, o sigui directes per algun valor i seqüencials per un altre.
Exemple
SELECT * FROM EMPLEAT WHERE Numdep=5 and sou>=25000
SELECT * FROM EMPLEAT WHERE Numdep=5 ORDER BY Cognom1
Implementació dels accessos per valor. Índexs
- La implementació dels accessos per valor és més complexa que els accessos per posició. Per implementar-los d’una manera eficient els SGBD fan servir unes estructures anomenades índex. Analogia amb l’índex d’un llibre.
- Justificació de la necessitat dels índexs. Exemples:
● SELECT * FROM empleat WHERE Numdep=5
Manera no eficient. Accedir seqüencialment per posició des de la primera a la darrera pàgina comprovant si compleix la condició.
● SELECT * FROM alumne ORDER BY cognom1
Si les files estiguessin ordenades per cognom1 es podria fer un accés seqüencial per posició, accedint des de la primera fins a l’última pàgina. Ara bé per qualsevol altre ORDER BY caldria llegir totes les files, collocar-les en una taula temporal, ordenar-les i retornar el resultat.
➢ Els índexs que utilitzen els SGBD són unes estructures de dades auxiliars que faciliten la cerca sobre les dades.
➢ Les files (tuples) que contenen les dades generalment tenen molts de camps (Nummat, Dni, Nom, Cog1, ….) i ocupen bastant d’espai. Les files (tuples) que contenen els índexs normalment consten de parelles de camps (anomenades entrades de l’índex) formades pel valor del camp d’indexació i un RID. El fet que les entrades de l’índex ocupin poc espai ens facilita la cerca.
➢ Quan es faci un INSERT, la nova fila s’inserirà en la pàgina de dades corresponent. A més caldrà actualitzar tots els possibles fitxers índexs definits per aquesta taula.
➢ Una cerca consistirà en buscar un valor a l’índex per tal de conèixer el seu RID (pàgina/posició). Amb aquest RID farem un accés directe per posició per obtenir la pàgina de dades.
➢ Veurem el índexs arbres B+ i els basats en funcions de dispersió. En hi ha d’altres, per exemple els multidimensionals que els veureu en l’assignatura optativa “Sistemes de Gestió de BD”
Arbre B+. Definició
- Arbres de cerca. Els nodes fulla tenen una estructura diferent dels nodes intern i de l’arrel.
- Són arbres balancejats que tots els nodes terminals estan en el mateix nivell.
- Són arbres de pocs nivells i de molts nodes a cada nivell.
- Nodes arrel i interns: serveixen per guiar la cerca.
- Nodes fulla: contenen tots els valors a indexar juntament amb el RID que ens
indiquen la pàgina de dades en que es localitzen. - Tots els nodes es guarden en el disc dur com una pàgina de l’espai virtual índex.
- Només explicarem el seu funcionament. Molt semblants als arbres balancejats de
EDA.
Esteuctura dels nodes arrels i interns dels Arbres B+
- Comencen i acaben amb un apuntador. O sigui si tenim n valors tindrem n+1 apuntadors
- Els valors estan ordenats de menor a major.
- Els nodes arrel/interns mai contenen cap RID. Els RID’s solament en els nodes fulla.
- No contenen tots els valors a indexar, solament uns quants que ens guien en la cerca.
Accessos directes per valor amb un arbre B+
- Per fer un accés directe per valor d’un camp del qual disposem d’un índex del tipus arbre B+, partim del node arrel (1 accés a disc). Es sol disposar d’una còpia a memòria interna del node arrel per tal d’estalviar-nos aquest accés.
- Dins aquest node busquem la pàgina del nivell 2 de l’arbre en la que hem de seguir la cerca. Anirem accedint als nodes interns fins arribar al node fulla.
- En arribar al node fulla, trobarem el valor que busquem i el RID que ens indica la pàgina de l’espai de dades on trobarem tot el registre (tota la fila) de les dades que busquem.
- Caldrà fer tants accessos a disc com nivells tingui l’arbre més un accés per accedir a la plana de dades.
- Exemple: SELECT * FROM Alumne WHERE Dni= 4
Accessos seqüencials per valor amb un arbre B+
- Per fer un accés seqüencial per valor d’un camp del qual disposem d’un índex del tipus arbre B+, partim directament del primer node fulla i anem accedint a la pàgina de dades de cadascun dels registres a través del RID corresponent.
- Una vegada hem accedit a tots els registres del primer node fulla accedim a través del apuntador al següent node fulla i anem repetint el que hem fet en el punt anterior. I així successivament fins recórrer tots els nodes fulla.
- Si l’accés seqüencial és en ordre descendent, cal primer accedir al darrer node fulla i repetir tot el procés anterior fins arribar al primer node fulla.
- Exemple. SELECT * FROM Alumne ORDER BY Dni
Arbres B+ amb camps no claus
- Si el camp que indexem no és clau els valors que tindrà es poden repetir. Com seria l’arbre B+ en aquest cas?
Opció 1. Permetre entrades diferents amb el mateix valor en l’arbre. En nodes fulla diferents podrem tenir el mateix valor amb el seu RID corresponent. Caldria modificar l’algorisme d’accés a l’arbre per tal de que sempre accedeixi a l’entrada de més a l’esquerra i llavors anés accedint a tots els elements que tinguin el mateix valor.
Opció 2. Una altra possibilitat és tenir una sola entrada que contingui varis RID’s, un per cada aparició del valor. Aquesta possibilitat fa que la mida de les entrades sigui variable la qual cosa complica l’algoritme. Per contra com que els valors iguals no es repeteixen estalvia espai i conseqüentment entrades/sortides.
Índexs basats en la dispersió (Hash)
- En aquest tipus d’índex, una funció de dispersió és una funció que a partir del valor del camp d’indexació ens retorna el número de pàgina de l’espai virtual índex on trobem l’entrada d’aquest valor.
- S’anomenen també funció de hash (índex a partir d’una funció de hash).
- Aquesta funció de hash al aplicar-la al valor a indexar k retorna un número de pàgina: h(k) -> [0..N-1] (o entre 1 i N).
- Caldrà que el fitxer índex tingui tantes pàgines índex com valors ens pugui retornar la funció de hash.
- Les pàgines índexs es guarden en el disc dur, igual que les pàgines que contenien un node en els arbres B+.
- La funció de Hash ha de distribuir bé els valors dins el rang de valors a retornar. Exemple dni (suma dígits) no seria una bona funció.
Explicació funcionament dels índexs basats en la dispersió (Hash)
- Al fer un INSERT el SGBD assigna un RID (pàgina/posició) per la nova fila. Exemple: INSERT INTO ALUMNES (40125768, ‘Pere’, …. ) Suposem que el RID assignat és el 543/2 (això vol dir que aquest registre ha anat a parar a la pàgina virtual de dades 543, posició 2).
- Sobre el valor del camp que volem indexar mitjançant hash es calcula en quina pàgina virtual índex li correspon a aquell valor.
- Exemple: si el camp a indexar és el dni i la funció de hash és mod 1000 tindrem que: Pàg_índex=40125768 mod 1000= 768
- Si la funció de Hash és mod 1000 tindrem tantes pàgines índex com valors diferents ens pot retornar, o sigui de la 000 a la 999= 1000 pàgines índex.
- En la pàgina 768 de l’índex s’inserirà una entrada tal com:
Tractament de sinònims en dispersions de hash
- Sinònim: Es diuen sinònims als valors diferents d’un atribut que al aplicar la funció de hash ens retornen el mateix valor, o sigui (kx ≠ ky) però (h(kx) = h(ky)). També reben el nom de collisions.
- El nombre de valors que pot agafar un atribut sol ser molt gran mentre que l’espai de pàgines és limitat, això fa que hi hagin molts sinònims. Tots els sinònims van a parar a la mateixa plana de l’índex.
Exemple suposant una funció de hash dni mod 100, tot els acabats en les dues mateixes xifres serien sinònims (40125978, 77915078, 35321178, …)
- Els problemes dels índexs basats en la dispersió apareixen quan una pàgina de l’índex queda plena d’entrades. En aquest cas es creen pàgines d’overflow (excedents) lligades amb la pàgina de l’índex.
Implementació dels accesssos per diversos valors
- Implementació accessos directes per varis valors
SELECT * FROM EMPLEAT WHERE NumDep=5 and Sou=1000
● Dependrà dels índexs que tinguem. Per exemple si disposem d’un índex B+ per NumDep i un per Sou podem obtenir a través dels arbres B+ els Rid’s que NumDep=5 i els que Sou=1000. Fent la intersecció dels dos obtenim els Rid’s
demanats.
● Si solament tenim un arbre B+ per Numdep. A través de l’arbre accedirem a
tots els registres que NumDep=5 i llavors haurem de mirar un per un si
Sou=1000
● Es poden donar moltes situacions
- Implementació accessos seqüencials per varis valors SELECT * FROM EMPLEAT ORDER BY Cog1,Cog2,nom
● Es poden fer índex compostes per varis atributs. Per exemple podríem fer un arbre B+ amb camp indexació el format per [cog1,cog2,nom]. En aquest cas simplement caldria anar seguint els nodes fulla per fer l’ORDER BY Cog1,Cog2,nom. Els valor guardats en el nodes serien Cog1,Cog2, Nom.
● Si no disposem d’aquest arbre B+ caldria accedir a cada pàgina, obtenir els tres camps i fer una ordenació. Si hi ha pocs registres segurament es podria fer una ordenació interna (tots els element caben en memòria interna) altrament caldria fer una ordenació externa.
- Implementació accessos mixtes
SELECT * FROM EMPLEAT WHERE NumDep=5 and Sou>1000
● Si solament tenim un índex per Numdep. A través de l’índex accedirem a tots
els registres que NumDep=5 i llavors haurem de mirar un per un si Sou>1000
● Si fos una consulta molt habitual podíem fer un índex compost.
La clau principal d’una taula CLIENTS és el camp Nif. També té un altre camp clau
(candidata) que és CodiClient. Aquesta taula disposa d’un sistema d’indexació basat
en un arbre B+ de 4 nivells que indexa pel camp Nif. Aquest arbre B+ té 1000 nodes
terminals (nodes fulla). La taula CLIENTS té 100.000 pàgines de dades i un milió
(1.000.000) de clients. Es demana:
A1) Explica què farà el SGBD per accedir a les dades quan fem una SELECT *
FROM CLIENTS WHERE Nif = 40500600A ?. Quants accessos a disc haurà de
fer (*)?. Justificar la resposta. (0,25p)
A2) Explica què farà el SGBD per accedir a les dades quan fem una SELECT Nif
FROM CLIENTS ORDER BY Nif ?. Quants accessos a disc haurà de fer (*)?.
Justificar la resposta. (0,5p)
A3) Explica què farà el SGBD per accedir a les dades quan fem una SELECT *
FROM CLIENTS ORDER BY Nif ?. Quants accessos a disc haurà de fer (*)?.
Justificar la resposta. (0,5p)
A4) Explica què farà el SGBD per accedir a les dades quan fem una SELECT *
FROM CLIENTS WHERE Nif>=40500600A and NIF<=50600700H?. Quants
accessos a disc haurà de fer (*) ?. Justificar la resposta. (0,5p)
A5) Explica què farà el SGBD per accedir a les dades quan fem una SELECT *
FROM CLIENTS WHERE CodiClient= 12345 ?. Quants accessos a disc haurà de
fer (*)?. Justificar la resposta. (0,5p)
A6) Explica què farà el SGBD per accedir a les dades quan fem una SELECT *
FROM CLIENTS WHERE Població=’Girona’ ?. Quants accessos a disc haurà de
fer (*)?.. Justificar la resposta. (0,5p)
Considereu que en la mateixa taula CLIENTS anterior (100.000 pàgines de dades i
un milió de clients) ara es crea un índex pel camp clau candidata CodiClient basat
en una bona funció de hash en la que podeu considerar que mai hi haurà overflow.
Es demana:
A7) Explica què farà ara el SGBD per accedir a les dades quan fem una SELECT *
FROM CLIENTS WHERE CodiClient= 12345 ?. Quants accessos a disc haurà de
fer? (*) . Justificar la resposta. (0,25p)
A8) Explica què farà el SGBD per accedir a les dades quan fem una SELECT
CodiClient FROM CLIENTS ORDER BY CodiClient ?. Quants accessos a disc
haurà de fer? (*) . Justificar la resposta. (0,5p)
(*) en cas de no poder determinar amb exactitud quants accessos haurà de fer,
la resposta pot ser “ tants accessos com …..”
A1)Es tracta d’un accés directe per valor. Com que pel camp nif es té un índex
B+, primer s’accedirà al node arrel de l’arbre i s’anirà accedint a un node de cada
nivell baixant fins arribar als nodes fulla. En el node fulla trobarem el nif 40500600A
juntament amb el seu RID. Llavors accedeix a la plana de dades que li indica el RID per
obtenir la resta d’informació.
En total, farem 5 accessos a disc un a cada nivell de l’arbre més un cinquè a la pàgina
de dades.
A2) es tracta d’un accés seqüencial per valor. Com que pel camp nif es té un
índex B+ i com que solament hem de retornar el camp Nif, hem d’accedir
directament al primer node fulla i anar mostrant els nif’s en l’ordre que estan en
aquest primer node fulla. Una vegada hem obtingut els nif’s del primer node fulla
hem d’anar seguint amb la resta de nodes fulla fins arribar al darrer node fulla i anar
mostrant els nif’s.
En total farem 1000 accessos a disc, o sigui tants com nodes fulla té l’arbre.
A3) es tracta d’un accés seqüencial per valor. Com que pel camp nif es té un
índex B+ hem d’accedir directament al primer node fulla i anar seguint els nif’s en
l’ordre que estan en aquest primer node fulla. Com que ens demanen tota la
informació (Select ) de cada nif una vegada hem obtingut el primer nif d’aquest
primer node fulla hem d’accedir a la pàgina de dades que ens indica el RID per
obtenir la resta de la informació. Això ho anirem repetint per cada entrada del
primer node fulla. Una vegada mostrada aquesta informació accedim al segon node
fulla i anem a buscar la informació corresponent a cada nif i hem de repetir aquest procés fins arribar al darrer node fulla.
En total farem:
‐ 1000 accessos a disc, o sigui tants com nodes fulla té l’arbre
‐ més un accés a la pàgina de dades per cada registre que tinguem.
Si tenim 1.000.000 de clients faríem 1.001.000 accessos a disc (tot i que és possible que al anar a fer algun accés ja tinguéssim la pàgina de dades carregada al buffer i no ens calgués fer l’accés físic al disc*).
Una altra possible resposta seria anar directament a les pàgines de dades, llegir tots els registres guardant‐los en una taula i després fer una ordenació. Com que
probablement tots els registres no ens cabrien a memòria haurien de fer una
ordenació externa i això pot ser molt costós en nombre d’accessos.
A4) es tracta d’un accés directe per valor pel Nif 40500600A i després accedir
seqüencialment dins els nodes fulla de l’arbre . Primer s’accedirà al node arrel de
l’arbre i s’anirà accedint a un node de cada nivell de l’arbre, baixant fins arribar als
nodes fulla. En el node fulla trobarem el nif 40500600A juntament amb el seu RID.
Llavors accedeix a la plana de dades que li indica el RID per obtenir la resta
d’informació. Una vegada hàgim obtingut aquesta informació anirem llegint
seqüencialment en els nodes fulla el següents valors del nif, comprovant que siguin menors que el 50600700H. Per cada valor de nif obtingut haurem d’accedir a la seva pàgina de dades on trobarem la resta de la informació. Una vegada acabats els nif
del node fulla accedit passarem al següent node fulla i repetirem el mateix procés
per cadascun d’ells i així successivament fins obtenir en algun node fulla un valor
més gran que el 50600700H.
En total farem:
‐ 4 accessos, un per cada nivell de l’arbre fins arribar al primer node fulla, que
serà on trobarem (o no) el Nif 40500600A.
‐ farem tants accessos a disc com nodes fulla continguin entrades amb nif’s
compresos entre el 40500600A i el 50600700H
‐ més un accés a la pàgina de dades per cada registre que tingui un Nif entre
40500600A i el 50600700H.
A5) com que pel camp CodiClient NO tenim cap índex, no ens quedarà cap
altra solució que anar buscant aquest valor dins les pàgines de dades. Accedirem a la
primera pàgina de dades i buscarem aquest valor en cadascun dels registres de la
pàgina. Repetirem aquest procés per les següents pàgines fins a trobar un registre
que contingui aquest valor. Al tractar‐se d’un camp clau, quan en trobem un ja
podrem parar la cerca ja que no en hi haurà cap més amb aquest valor.
Farem tants accessos a disc com calgui fins a trobar la pàgina que contingui aquest
valor. En el cas més favorable el trobarem en la primera pàgina de dades, la 1, en el
cas més desfavorable el trobarem en la darrera pàgina de dades, la 100.000. Per
terme mig, ni el més favorable ni el més desfavorable, o sigui (1+100000)/2 , aprox
50.000 accessos.
A6) com que pel camp Població NO tenim cap índex, no ens quedarà cap altra
solució que anar buscant aquest valor dins les pàgines de dades. Accedirem a la
primera pàgina de dades i buscarem aquest valor, Població = ‘Girona’, en cadascun
dels registres de la pàgina. Al tractar‐se d’un camp NO clau, haurem d’accedir i mirar
si és o no de Girona per cadascun dels registres de la taula. Com que la taula té
100.000 pàgines, haurem de fer 100.000 accessos un a cada pàgina de dades de la
taula.
A7) es tracta d’un accés directe per valor. Com que ara pel camp CodiClient
tenim un índex basat en la dispersió, al fer aquesta cerca primer s’aplicarà la funció
de hash corresponent al valor 12345. Amb el valor retornat per la funció de hash
s’accedirà a la pàgina de l’índex que tingui aquest valor. En aquesta pàgina,
trobarem, si existeix, el valor 12345 amb el seu corresponent RID. Llavors s’accedeix
a la pàgina de dades que li indica el RID per obtenir la resta d’informació.
En total, farem 2 accessos a disc, un a una pàgina índex més un altre a la pàgina de
dades.
A8) es tracta d’un accés seqüencial per valor. Com que l’índex pel camp
CodiClient és un índex basat en la dispersió, NO ens serveix per fer accessos
seqüencials per valor ja que l’índex no manté cap ordre. Llavors com que solament
hem de retornar el Codiclient, la solució és accedir a cadascuna de les pàgines de
l’index i col∙locar els valors de CodiClient en una taula i després ordenar‐la. Com que
haurem d’accedir a cadascuna de les pàgines de l’índex haurem de fer tants accessos com pàgines tingui el fitxer índex hash.
