Emmagatzemament i mètodes d'accés a les BD

I 0 flashcards i 2 preguntes més al document.

Text del document

APUNTS BASES DE DADES Grau en Enginyeria Informàtica Universitat Politècnica de Catalunya AprenAI 2026-2027 Apunts complets d'emmagatzemament i índexs B+: gestió de pàgines i tablespaces, càlcul de costos d'E/S i tècniques d'accés directe i per rang a les bases de dades.

APREN.AI Índex 1 Arquitectura física i virtual d'emmagatzemament Jerarquia de nivells d'emmagatzemament Característiques de la memòria externa i interna La pàgina com a unitat física mínima Estructura del camp i tipus de pàgines Extensions, fitxers i gestió d'E/S Tipologies d'espais virtuals (Tablespaces) 2 Mètodes d'accés i estructures d'índex en arbre B+ Mètodes d'accés bàsics Estructura d'un índex arbre B+ Propietats d'equilibri i dimensionament òptim Cerca directa, seqüencial i índexs agrupats Consultes multiatribut i comandes SQL Solucions de les preguntes de repàs Aquests apunts poden contenir errors o omissions.

Són un material de suport i no substitueixen el temari oficial ni el professorat: contrasta la informació important. Emmagatzemament i mètodes d'accés a les BD 1 1 Arquitectura física i virtual d'emmagatzemament EN ACABAR SABRÀS Distingir els nivells lògic, virtual i físic en l'arquitectura d'un SGBD. Identificar els components interns d'una pàgina i el rol del vector d'adreces. Classificar els diferents tipus d'espais virtuals segons les necessitats d'accés a les dades. PENSA-HI ABANS DE LLEGIR 1 Per què un gestor de base de dades no treballa directament sobre registres solts en disc en comptes de carregar pàgines senceres?

Els sistemes gestors de bases de dades (SGBD) organitzen l'emmagatzemament mitjançant una jerarquia que garanteix la independència física de les dades respecte a l'usuari. Això permet reestructurar la disposició interna sense alterar la visió lògica de les consultes. Jerarquia de nivells d'emmagatzemament L'arquitectura es divideix en tres estrats ben diferenciats: Nivell lògic: comprèn les estructures visibles com taules, files i atributs. Nivell virtual: actua de passarel·la o correspondència (mapping) entre el món lògic i el físic mitjançant espais virtuals (tablespaces). Nivell físic: gestiona els dispositius d'emmagatzemament extern (fitxers, extensions i pàgines).

Característiques de la memòria externa i interna La memòria secundària (discs o SSD) aporta persistència i capacitat teòricament il·limitada a cost baix, però té el desavantatge d'un temps d'accés variable i lent (de l'ordre de ). En contraposició, la memòria principal és volàtil, cara i de capacitat reduïda, amb temps ràpids i constants ( a ). La pàgina com a unitat física mínima La pàgina constitueix el bloc atòmic de transferència entre el disc i la memòria interna, amb una mida fixa habitual de 4 KB o 8 KB. Mai no és possible llegir una fracció de pàgina: qualsevol acció transfereix el bloc complet. A més, cada pàgina té assignat un número propi com a unitat d'adreçament.

10 s 3 10 s 6 10 s 9 Emmagatzemament i mètodes d'accés a les BD 2 Esquema d'estructura d'una pàgina amb vector d'adreces de fila. A l'interior de la pàgina, les files s'organitzen mitjançant un vector d'adreces de fila situat al final de l'espai, el qual apunta a l'inici de cada registre per aprofitar millor l'espai buit restant. ERROR FREQÜENT Fragmentar registres entre pàgines diferents de manera innecessària penalitza greument el rendiment del sistema. Tot i que una fila pot ocupar més que la capacitat d'una pàgina, l'adreçament múltiple obliga a fer accessos de disc addicionals molt costosos.

Estructura del camp i tipus de pàgines Dins d'una fila, cada camp consta d'una capçalera (on s'indica si el valor és nul i la seva longitud) i el propi contingut. Els formats d'emmagatzemament habituals inclouen tipus com smallint (2 bytes), integer (4 bytes), float (8 bytes en coma flotant), char(n) (n bytes en ASCII), varchar (longitud real més bytes descriptius), decimal(p,s) calculat segons i dates (4 bytes amb format aaaammdd ). A banda de les pàgines ordinaries de dades, els SGBD gestionen pàgines de catàleg, pàgines d'índex i pàgines d'objectes grans (com ara BLOBs o vídeos), les quals tenen tractament diferenciat i mai no es barregen directament amb registres convencionals.

COMPROVA-HO 2 Quina conseqüència té que la pàgina sigui la unitat de transferència mínima quan es vol llegir un sol camp d'una fila? Extensions, fitxers i gestió d'E/S Una extensió (extent) és una seqüència de pàgines contigües sol·licitada al sistema operatiu, dissenyada específicament perquè les lectures seqüencials resultin òptimes i ràpides. Al seu torn, un fitxer físic agrupa diverses extensions.

(p + 1)/2 Emmagatzemament i mètodes d'accés a les BD 3 El gestor de la base de dades pren el control directe de les entrades i sortides (E/S) en comptes de delegar-les al sistema operatiu, garantint la coordinació de transaccions (operacions de fixació com COMMIT , desfer amb ROLLBACK i escriptura al fitxer de diari o log). Per minimitzar accessos a disc, s'apliquen estratègies com el double buffering, la lectura anticipada (prefetching) i la retenció de blocs freqüents en memòria. Tipologies d'espais virtuals (Tablespaces) L'espai virtual permet desacoblar els objectes lògics del sistema de fitxers. Cada element té una correspondència física concreta sense generar redundància de dades.

Destaquen quatre configuracions: Tipus d'espai virtual Propòsit principal Comportament EV de taules Taules petites o independents Proporciona selecció individual ràpida, però alenteix reunions (joins) si les dades estan disperses. EV d'agrupació Taules estretament relacionades Intercala registres relacionats a la mateixa pàgina física per accelerar reunions, empitjorant consultes d'una sola taula. EV fragmentat Taules d'elevat volum Distribueix registres en fitxers distints mitjançant criteris de rang, hash o aleatoris. EV d'objectes grans Dades voluminoses (BLOB, fitxers) Aïlla els continguts pesants en blocs independents encadenats per evitar interferir amb camps ordinaris.

Emmagatzemament i mètodes d'accés a les BD 4 Diagrama de col·locació de files intercalades en un espai d'agrupació. Finalment, cada registre s'identifica de forma unívoca mitjançant el RID (Record Identifier), format pel parell identificador de pàgina i ranura ( page_id, slot_id ). La fila pot reubicar-se dins de la pàgina, però roman immòbil (pinned) respecte a l'exterior per mantenir les referències estables. IDEES CLAU L'arquitectura en tres nivells (lògic, virtual i físic) atorga independència física a les dades. La pàgina és el bloc físic mínim indivisible de lectura i escriptura entre disc i memòria.

El RID (page_id, slot_id) permet referenciar registres sense que calgui canviar-ne la identitat si es mouen dins la mateixa pàgina. Els espais virtuals organitzen el mapping físic segons convingui: taules independents, agrupació per afavorir reunions o fragmentació per a taules grans. COMPROVA EL QUE HAS APRÈS 3. En què consisteix un espai virtual d'agrupació i quin avantatge ofereix? 4. Com està constituït el RID d'una fila i per què és important que quedi clavada a la pàgina? Emmagatzemament i mètodes d'accés a les BD 5 Test Encercla la resposta correcta. Les solucions són al final. 5. Quina és la unitat física mínima de transferència entre el disc i la memòria interna? 6.

Per què els SGBD gestionen directament les entrades i sortides? 7. Quin inconvenient principal presenta un espai virtual d'agrupació? 8. Quina informació conté l'identificador de registre (RID)? 2 Mètodes d'accés i estructures d'índex en arbre B+ EN ACABAR SABRÀS Descriure el funcionament intern i les propietats d'un índex en arbre B+. Diferenciar els costos i característiques entre índexs agrupats i no agrupats. Avaluar mètodes de resolució de consultes amb múltiples atributs mitjançant intersecció de RIDs o índexs compostos. PENSA-HI ABANS DE LLEGIR 9 Per què s'utilitzen arbres B+ en lloc d'arbres binaris convencionals per gestionar índexs en bases de dades?

El registre o fila a) La pàgina de disc b) El fitxer físic complet c) L'extensió de pàgines d) Per delegar la gestió del log al sistema operatiu a) Per controlar quan escriure a disc davant commits i fallades b) Per forçar que cada camp ocupi una pàgina sencera c) Perquè el maquinari no admet adreçament de memòria virtual d) Impedeix que es facin reunions entre taules relacionades a) No admet fitxers que superin els 4 KB b) Obliga a duplicar les dades físicament c) Empitjora el rendiment de les consultes sobre una sola taula d) Identificador de pàgina i posició de ranura a) Valor de la clau primària en text pla b) Adreça d'extensió i sector físic del disc c) Nom de la taula i mida del bloc d) Emmagatzemament i mètodes d'accés a les BD 6 Mètodes d'accés bàsics El cost de qualsevol operació d'accés a la base de dades s'avalua fonamentalment pel nombre de pàgines físiques transferides.

Els accessos es divideixen segons el criteri de localització: Accés per posició: pot ser directe (calculant la pàgina física a partir de la posició virtual, amb cost d'1 lectura) o seqüencial (recorrent totes les pàgines). És recomanable en taules petites o quan cal processar la totalitat dels registres. Accés per valor: cerca registres a partir del contingut d'un atribut utilitzant estructures auxiliars com els índexs, evitant exploracions seqüencials costoses. Estructura d'un índex arbre B+ Un arbre B+ és una estructura balancejada dissenyada per reduir al mínim les operacions d'entrada/sortida a disc. El cost teòric d'accés és proporcional a l'alçada de l'arbre, és a dir, .

Diagrama de l'estructura jeràrquica d'un arbre B+ amb nodes interns i fulles. Tot arbre B+ es caracteritza pel seu ordre , el qual determina la capacitat mínima i màxima dels nodes: Nodes interns: contenen com a màxim valors i apuntadors a nodes fills. La seva missió exclusiva és guiar la cerca; no emmagatzemen RIDs ni dades completes. Nodes fulla: contenen parells [valor, RID] (denotats sovint com a entrades ) i dos apuntadors addicionals per enllaçar de forma bidireccional amb la fulla prèvia i la posterior.

PER RECORDAR-HO A diferència d'altres arbres de cerca, en un arbre B+ totes les claus reals de cerca es troben sempre repetides als nodes fulla, mentre que els nodes interns només contenen valors de partició per dirigir el camí. N log (registres) d d 2d 2d + 1 v Emmagatzemament i mètodes d'accés a les BD 7 Estructura d'un node fulla amb claus, RIDs i enllaços anterior i següent.

Propietats d'equilibri i dimensionament òptim L'eficiència dels arbres B+ es manté mitjançant dues propietats essencials: Com que cada node equival a una pàgina de memòria, el càlcul de l'ordre òptim es fa respectant la mida màxima de bloc: COMPROVA-HO 10 Quants accessos a node d'índex calen per a una cerca directa per valor si l'arbre té alçada h i l'arrel és a la memòria principal? Cerca directa, seqüencial i índexs agrupats En un accés directe per valor, es baixa des de l'arrel fins a la fulla corresponent i es recupera el RID per accedir a la pàgina de dades.

En un accés per rang (seqüencial), es troba la primera fulla i es recorre la cadena d'apuntadors horitzontals entre fulles consecutives. Es distingeixen dues grans modalitats segons com es disposen les dades físiques: Tipus d'índex Organització física de les dades Cost d'accés seqüencial per rang Índex agrupat (cluster) Les files estan físicament ordenades segons la clau de l'índex. Molt baix: , on és el nombre de pàgines contigües de dades. Índex no agrupat Les dades no tenen cap ordre físic vinculat a l'índex. Elevat: requereix un accés a disc per cada registre coincident si estan dispersos.

Ocupació mínima: tots els nodes de l'arbre (a excepció del node arrel) han d'estar plens com a mínim al 50 % de la seva capacitat. 1 Arbre equilibrat: totes les fulles es troben exactament al mateix nivell de profunditat. 2 d 2d × (mida valor + mida RID) + 2 × (mida apuntador fulla) mida p gina a ˋ h + D D R Emmagatzemament i mètodes d'accés a les BD 8 Comparativa gràfica entre índex no agrupat i índex agrupat sobre dades físiques. ERROR FREQÜENT Creure que una taula pot tenir múltiples índexs agrupats. Com que les dades físiques només es poden ordenar d'una única forma al disc, només pot existir un índex agrupat per cada taula.

Consultes multiatribut i comandes SQL Quan una consulta conté diversos predicats (com WHERE a >= X AND b = Y ), l'SGBD pot emprar dues estratègies principals: Intersecció de RIDs: s'avalua cada condició mitjançant un índex independent, s'obtenen els conjunts de RIDs respectius en memòria, se'n fa la intersecció i finalment només s'accedeix a les pàgines de dades resultants. Índex compost (multiatribut): es construeix un índex sobre una tupla de camps. Requereix ordre lineal lexicogràfic (primer per l'atribut principal, i en cas d'empat pel segon).

En SQL, la creació d'aquestes estructures es gestiona mitjançant sentències DDL específiques: CREATE INDEX idx_despatx ON empleats (despatx); CREATE INDEX idx_desc ON empleats (despatx DESC); CREATE INDEX CLUSTER idx_agrup ON empleats (despatx); CREATE UNIQUE INDEX idx_unic ON empleats (despatx); CREATE INDEX idx_multi ON empleats (despatx, sou); Emmagatzemament i mètodes d'accés a les BD 9 PROCÉS Cerca directa per valor en arbre B+ 1 Accés a l'arrel Comprovació de l'interval de la clau cercada 2 Descens per nodes interns Seguiment de punters segons els valors divisoris 3 Localització de la fulla Cerca del parell [valor, RID] corresponent 4 Lectura a pàgina física Accés directe a la fila mitjançant el RID IDEES CLAU El cost dels accessos s'expressa mitjançant el nombre de pàgines físiques transferides entre disc i memòria.

Els nodes interns d'un arbre B+ només contenen valors de separació per encaminar la cerca, mentre que les fulles guarden totes les dades i RIDs. Un arbre B+ sempre està equilibrat i els seus nodes mantenen una ocupació d'almenys el 50 %. L'índex agrupat alinea l'ordre físic de les dades amb l'índex, optimitzant dràsticament les consultes per rang. COMPROVA EL QUE HAS APRÈS 11. En què es diferencia un node intern d'un node fulla en un arbre B+? 12. Com funciona l'estratègia d'intersecció de RIDs quan es disposa de dos índexs per a atributs diferents? Test Encercla la resposta correcta. Les solucions són al final. 13. Quina propietat manté sempre un arbre B+? 14.

Quin és el nombre màxim d'índexs agrupats que pot allotjar una taula? 15. Quin és el percentatge mínim d'ocupació dels nodes d'un arbre B+? Els nodes interns guarden els RIDs directes a) L'arrel conté totes les dades de la taula b) Tots els registres tenen ordre aleatori c) Totes les fulles estan al mateix nivell d) Tants com columnes tingui a) Cap, només s'admeten no agrupats b) Només un c) Exactament dos d) El 50 % a) El 75 % b) El 25 % c) El 100 % d) Emmagatzemament i mètodes d'accés a les BD 10 16. Com es formula la cerca per rang en un arbre B+ una vegada trobada la primera fulla?

Tornant a l'arrel per a cada clau a) Fent una exploració seqüencial de tota la taula b) Seguint els enllaços horitzontals entre fulles c) Reiniciant l'arbre de dalt a baix d) Emmagatzemament i mètodes d'accés a les BD 11 Solucions de les preguntes de repàs 1. Perquè els discs físics transfereixen dades en blocs atòmics de mida fixa, fent inviable accedir a un registre sense llegir la pàgina que el conté. 2. El SGBD està obligat a llegir del disc i carregar en memòria la pàgina sencera (de 4 KB o 8 KB), augmentant el cost d'entrada/sortida independentment de la petitesa de la dada cercada. 3.

Consisteix a col·locar registres de diferents taules relacionades dins de les mateixes pàgines físiques, millorant enormement el rendiment de les operacions de reunió (join). 4. Està format per l'identificador de pàgina i el número de ranura (page_id, slot_id); mantenir la fila lligada a la seva pàgina assegura que les referències externes de l'índex continuïn sent vàlides. 5. b) La pàgina de disc. La pàgina és la unitat atòmica de transferència, i mai no és possible transferir menys d'una pàgina sencera. 6. b) Per controlar quan escriure a disc davant commits i fallades. El gestor necessita garantir la consistència de transaccions com commit, rollback i el registre de logs. 7.

d) Empitjora el rendiment de les consultes sobre una sola taula. Com que barreja dades de diverses taules a les mateixes pàgines, recórrer només una d'elles requereix llegir més blocs innecessaris. 8. a) Identificador de pàgina i posició de ranura. El RID està constituït habitualment per page_id i slot_id. 9. Perquè els arbres B+ tenen un factor de ramificació molt elevat que redueix l'alçada a pocs nivells, minimitzant dràsticament els costosos accessos de lectura a disc. 10. Calen exactament h - 1 accessos a disc per a l'índex, ja que l'arrel ja està resident a la memòria interna. 11.

El node intern conté només valors de referència i punters a nodes inferiors per canalitzar la cerca, mentre que el node fulla conté totes les entrades reals de cerca (valor i RID) i punters d'enllaç entre fulles veïnes. 12. Es recuperen per separat els RIDs que compleixen cada condició a través dels seus índexs respectius, es calcula la intersecció d'aquests conjunts en memòria i es fa l'accés a disc únicament per als registres que compleixen totes dues condicions. 13. d) Totes les fulles estan al mateix nivell. L'arbre B+ és estrictament equilibrat, de manera que totes les seves fulles comparteixen la mateixa alçada. 14. c) Només un.

Les dades físiques només poden disposar-se ordenades en disc segons un únic criteri físic a la vegada. 15. a) El 50 %. Tots els nodes de l'arbre, llevat de l'arrel, han d'estar plens com a mínim al 50 % de la seva capacitat. 16. c) Seguint els enllaços horitzontals entre fulles. Com que les fulles estan interconnectades seqüencialment, el rang es recupera recorrent directament els nodes fulla veïns. Emmagatzemament i mètodes d'accés a les BD 12