Conceptos generales de bases de datos y organización indexada de archivos

Conceptos Generales

Deusto TEMA 1 CONCEPTOS GENERALES Asignatura BASES DE DATOS IDeusto

Reflexión en Grupos

• ¿ Qué aprendimos en Introducción a los Computadores?
• ¿ Cómo se representa la información en un computador?
• ¿ Cómo se gestiona el almacenamiento y recuperación de la información? @ 123RF (123RF 123RF" @12BRF' Bases de Datos I 2Deusto

Conceptos Básicos (1)

• Información: conjunto de símbolos que representan hechos, objetos o ideas
• Diferencia entre representación y dato
• Representación: NOMBRE
• Dato: JUAN
• Representación de la información: código binario >Bit y byte
• Bit: unidad mínima de información (valores 0-1)
• Byte: número de bits necesarios para almacenar un carácter (octeto = 8 bits) bit 00110101 byte (8-bits) Bases de Datos I 3

Conceptos Básicos (2)

• Campo (ítem) y registro
• Registro lógico (RL): conjunto de campos relacionados
• Registro físico o bloque: unidad de transferencia entre un fichero y la memoria principal (conjunto de RL).
• Factor de bloqueo (FB): nº de RL por bloque
• Ventaja de agrupación de registros en bloques » mejora el tiempo de proceso CAMPO NOMBRE Dato elemental REG. LÓGICO DNI APELLIDOS NOMBRE Conjunto de campos. Unidad de proceso para el usuario > REG. FÍSICO O BLOQUE RL1 RL2 RL3 RL4 Conjunto de registros lógicos. Depende del factor de bloqueo. 128 128 REG. LOGICO 1 REG. LOGICO 2 REG. LOGICO 3 REG. LOGICO 4 256 BYTES REG. FISICO + Bases de Datos I 4

Conceptos Básicos (3)

Deusto

• Fichero
• Conjunto de registros de longitud fija o variable
• Clave » identifica cada registro lógico dentro del fichero DNI APELLIDOS NOMBRE Bases de Datos I 5Deusto

Conceptos Básicos (4)

• Estructura física
• Disco » pistas >> registro físico/bloque Pista/ Cilindro Sector Cabezas 8 cabezas, 4 platos
• Estructura lógica
• Fichero/archivo » registro lógico » campo Campos Nombre Dirección Teléfono Registro Bases de Datos I 6Deusto

Dispositivos de Almacenamiento (1)

• Tipos de almacenamiento masivo
• Memoria principal
• Se almacenan temporalmente tanto los datos como los programas que la unidad central de proceso (CPU) está procesando
• Memoria secundaria
• Dispositivos y soportes de almacenamiento de datos auxiliares
• Cintas (magnéticas)
• Discos magnéticos
• Discos ópticos
• Discos RAID (Redundant Array of Independent Disks)
• Dispositivos USB Bases de Datos I 7

Dispositivos de Almacenamiento (2)

Deusto DISPOSITIVOS DE ALMACENAMIENTO (2) ValueRAM MEMORY Memoria Principal Cintas DVD 5 disc Discos Ópticos USB Flash Drive Discos RAID RAID 0 - A1 A2 A3 A4 B1 82 B3 B4 85 CI C2 C3 C4 C5 D1 D2 D3 D4 D5 E1 E2 E3 E4 ES Disk 1 Disk 2 Disk 3 Disk 4 Disk 5 Bases de Datos I 8 boodom Discos Magnéticos ("flexible y duro") C C USB (Universal Serial Bus)Deusto

Procesamiento de Ficheros

1. Organizaciones de ficheros
2. Métodos de acceso a los registros de un fichero
3. Operaciones con ficheros Bases de Datos I 10Deusto

Organizaciones de Ficheros

• Organización: modo de disponer los registros del fichero en el dispositivo de almacenamiento
• O. secuencial: los registros se almacenan y recuperan secuencialmente, uno detrás de otro.
• O. directa: se utiliza un algoritmo para almacenar y recuperar los registros utilizando su clave.
• O. indexada: se utilizan índices que permiten recuperar los registros conocida su clave. Bases de Datos I 11Deusto

Organización Secuencial

• Los registros se almacenan en secuencia física (unos detrás de otros)
• La secuencia puede tener algún sentido lógico (es decir, seguir un cierto orden) o no
• Ordenados vs. No ordenados
• Los nuevos registros se van incorporando siempre al final Fichero Secuencial Registro 1 Registro 2 Registro 3 . . Registro N-1 Registro N Nuevo Registro N+1 Nuevo Registro N+2 . .. Bases de Datos I 12

Ejemplo de Datos de Alumnos

Deusto EJEMPLO (Datos de Alumnos) DNI NOMBRE DATOS a organizar ► 11 Aguirre, J. 22 López, S. 25 Acha, R. 72 Ruiz, L. 81 Sainz, P. 90 Ruiz, A. representa los siguientes datos utilizando la organización secuencial Bases de Datos I 13Deusto

Organización Directa (1)

Direccionamiento Calculado

• Correspondencia entre la clave de identificación de cada registro lógico y su dirección física » función de hashing o de direccionamiento Claves posibles Función Hashing (algoritmo) Espacio de direcciones Datos Función de Hash Hashes 00 Jirafa 01 02 Elefante 03 04 León 05 .. : Tigre 15 Bases de Datos I 14

Ejemplo de Datos de Alumnos con Organización Directa

Deusto EJEMPLO (Datos de Alumnos) DNI NOMBRE DATOS a organizar ► 11 Aguirre, J. 22 López, S. 25 Acha, R. 72 Ruiz, L. 81 Sainz, P. 90 Ruiz, A. representa los siguientes datos utilizando la organización directa Algoritmo: nºbloque=último dígito de la clave Bases de Datos I 15

Organización Directa (2)

Deusto

• Algoritmos de hashing -> División Resto Extracción de 5º y 3°dígito Folding Squaring 2 Conversión de base 12
• División resto 24964 64 49 13 16 56 25936 36 69 95 49 50 32179 79 91 0 89 25 38652 52 26 38 25 58 40851 51 18 59 25 57
• Folding 53455 55 54 89 25 5 53758 58 87 95 25 0 54603 03 36 49 0 59 63388 88 83 21 44 36 81347 47 73 60 56 3 Sinónimos 0 0 2 4 0 1 Folding: sumar el número formado por 1º, 2º y 3º dígito con el formado por 4º y 5° y truncamiento por la izquierda 2 Squaring: extracción del 2º, 3º y 4º dígito, elevar al cuadrado y truncar por la izquierda
• Sinónimos
• Registros cuyas claves dan como resultado el mismo valor en la función de hash elegida. Bases de Datos I 16

Squaring

Conversión de Base

Clave

Extracción de Dígitos

Organización Directa (3)

• Problema >> colisiones/excedentes
• Sinónimos que no entran en el tamaño del bloque físico
• Resolución:
• Direccionamiento abierto > ej. Ubicar en siguiente bloque con espacio libre
• Direccionamiento cerrado > áreas de overflow (almacenamiento consecutivo o por hashing) 0 1 2 3 4 5 6 7 8 9 10 None None None None None 77 26 93 17 31 54 44 20 Sinónimo # Colisión/Excedente 55 Potenciales excedentes, dependiendo del tamaño del bloque físico (factor de bloqueo) Sinónimos Bases de Datos I 17

Organización Indexada (1)

• Utilización de índices para acceder más rápidamente a los registros de datos
• Una entrada de índice incluye una clave más un puntero
• El índice puede ser denso o no denso 5 Datos 1 3 Datos 2 2 Datos 3 4 1 Datos 5 4 Datos Índice denso 1 2 3 4 5 6 7 8 8 9 10 ... ... ... ... ... 16 16 17 ... ... ... ... ... ... 32 25 ... ... ... ... ... ... 32 40 33 ... ... ... ... ... ... 40 Índice no denso Bases de Datos I 18 Deusto 24 24Deusto

Organización Indexada (2)

• ¿ Qué tipos de accesos nos permitiría esta estructura indexada?
• Secuencial no ordenado > sin el uso de los índices (5, 3, 2, 1, 4) > Recuperar los registros según su secuencia física
• Secuencial ordenado » a través de la secuencia de índices (1, 2, 3, 4, 5) > Recuperar los registros en orden de clave
• Directo (o aleatorio) >> buscando el índice deseado (3) y accediendo al registro con el puntero > Recuperar el registro cuya clave sea X 5 Datos 1 3 Datos 2 3 2 Datos 4 1 Datos 5 4 Datos Bases de Datos I 19

Organización Indexada (3)

Deusto

• ¿ Cómo podemos optimizar el acceso a los índices? » jerarquía de índices
• ¿ Qué pasaría si insertásemos el registro 13?
• Un registro de ese bloque (FB=6) debería ir al área de overflow (bien el registro 13 o bien el 22 dependiendo la estrategia que se siga)
• Podría implicar una reorganización de índices 1 3 5 7 9 11 Punteros conecten la secuencia 11 > 12 14 … ... ... V > 22 22 33 ... ... ... ... 44 44 34 ... ... ... ... 44 Área de índices (jerarquizados) Área de datos primaria Área de overflow Bases de Datos I 20 22 13 23 33

Ejemplo de Datos de Alumnos con Organización Indexada

Deusto EJEMPLO (Datos de Alumnos) DNI NOMBRE 11 Aguirre, J. DATOS a organizar ► 22 López, S. 25 Acha, R. 72 Ruiz, L. 81 Sainz, P. 90 Ruiz, A. 1. Representa los siguientes datos utilizando la organización indexada · área de datos:3 reg/bloque · Área de índices: 2 reg/bloque 2. ¿ Cómo crecería el fichero añadiendo registros de clave 92, 96, 101, 135, 141? Bases de Datos I 21

Métodos de Acceso

• Modo de acceso > cómo localizar los registros dentro de un fichero
• Secuencial
• Directo (o aleatorio)
• Direccionamiento calculado (hashing)
• Índices Acceso secuencial .. ... 1 2 3 4 5 6 7 8 Acceso aleatorio . 1 3 7 2 8 6 4 5 Secuencial Archivo Secuencial Métodos de Acceso (Archivos) Archivo Indexado Directo/ Aleatorio I Archivo acceso directo (hash) Bases de Datos I 22Deusto

Operaciones con Ficheros

• Creación del fichero
• Apertura y cierre del fichero
• Borrado o eliminación del fichero
• Extensión del fichero (añadir más espacio para incorporar más registros)
• Actualización o mantenimiento
• Altas >> añadir registros
• Bajas » eliminar registros
• Modificaciones > cambiar el contenido de algún registro
• Recuperación: localizar y leer un registro Bases de Datos I 23Deusto

Repaso: Relaciona Conceptos

1. Organización secuencial
2. índice
3. Métodos de acceso
4. Organización directa
5. Factor de bloqueo
6. Registro físico

a Secuencial y directo (al azar) b Utiliza un algoritmo de hashing para almacenar y recuperar los registros c Número de registros lógicos por bloque d Consta de una clave y un puntero e Almacena los registros en secuencia física f Bloque Bases de Datos I 24Deusto

Preguntas de Repaso

Libro de apuntes (pág. 18)

1. Relación entre fichero, registro y campo
2. Relación entre registro lógico, registro físico, bloque y factor de bloqueo
3. Justifica cuál es el mejor método de acceso y cuál el peor
4. Qué es un puntero y para qué sirve
5. Relación entre índice y puntero Bases de Datos I 25