- Resumen teorico
- 馃Ь Listas
- 馃摎 Vectores
- 馃尦 Arboles
- 馃搧 Archivos
- 馃搧 Archivos Parcial
- Practica 1
- Practica 2
- Practica 3
- Practica 4
- PARCIALES RESUELTOS DE ARCHIVOS
- MUCHAS PREGUNTAS PARA EL FINAL
Important
Todas las preguntas van a estar justificadas segun el libro Introducci贸n a las Bases de Datos y mi sentido com煤n
Es un archivo residentes en la memoria secundaria y es administrado por el sistema operativo
Es el archivo utilizado desde el algoritmo. Cuando el algoritmo necesita operar, con un archivo, se genera una conexi贸n con el sistema operativo, el cual sera responsable de la administraci贸n. Esta acci贸n se denomina independencia fisica
- Secuencial: Se accede a cada elemento despues de haber accedido a su predecesor
- Secuencial Indizado: El acceso a los elementos de un archivo se realiza teniendo presente alg煤n tipo de organizaci贸n previa, sin tener en cuenta el orden fisico
- Directo: Es posible recuperar un elemento de dato de un archivo con un solo acceso, conociendo sus caracteristicas, mas alla de que exista un orden fisico o logico predeterminado
Es aquel que resume informaci贸n sobre un dominio del problema especifico. Por ejemplo, el archivo de productos de una empresa que contiene el stock actual de cada producto.
Es aquel que contiene novedades o movimientos realizados sobre la informaci贸n almacenada en el maestro. Por ejemplo, el archivo con todas las ventas de los productos de la empresa realizadas en un dia particular.
- No es necesario que los archivos detalle y maestro tengan la misma estructura.
- Es posible que no se procesen todos los registros del archivo maestro
- Siempre se procesan todos los registros del archivo detalle
- Para realizar la actualizaci贸n no me importa el orden de NADA
Se denomina proceso de baja a aquel proceso que permite quitar informaci贸n de un archivo.
- Baja f铆sica Consiste en borrar efectivamente la informaci贸n del archivo, recuperando el espacio f铆sico
- Baja l贸gica Consiste en borrar la informaci贸n del archivom pero sin recuperar el espacio fisico respectivo
- Igual para archivos con registros de longitud variable y longitud fija
Dado un archivo organizado con una lista invertida interna al mismo archivo
- La operaci贸n de FileSize del archivo siempre es mayor o igual a 1
- El registro cabecera nunca se elimina
- La lista invertida interna puede estar vacia (Si no se eliminaron elementos)
- El registro en la posici贸n 0 se considera el registro cabecera
- Nunca se recoore de forma secuencial (Solo para busquedas?)
- Ante una alta no es necesario actualizar la lista interna de espacio libre
- Ante una baja, siempre se modifica el registro cabecera.
- Lista encadenada invertida con los elementos borrados.
- La informaci贸n siempre es homogenea
- Altas, Bajas, y Modificaciones son mucho mas faciles ya que todos los registros tiene el mismo tama帽o.
- Es ineficiente en cuanto a memoria
- La utilizaci贸n del espacio en disco es optimizada
- Insertar y eliminar elementos es mas dificil
- Utiliza delimitadores
Es lo mismo tanto en registros de longitud fija como variable.
Al igual que los registros de longitud fija, se usa una lista encadenada invertida para los elementos borrados. Pero en este caso como tenemos los registros con distinto tama帽o, tenemos que aplicar una politica para elegir el mejor lugar.
- Primer Ajuste Consite en seleccionar el primer espacio disponible donde quepa el registro a insertar
- Mejor Ajuste Consiste en seleccionar el espacio m谩s adecuado para el registro. Se considera el espacio m谩s adecuado com aquel de menor tama帽o donde quepa el registro.
- Peor Ajuste Consiste en selecccionar el espacio de mayor tama帽o asignado para el registro solo los bytes necesarios.
Es aquella que se produce cuando un elemento de dato se le asigna mayor espacio del necesario
- Se puede producir con registros de longitud fija y con registros de longitud variable para con las tecnicas de primer ajuste y mejor ajuste.
Es aquel espacio disponible entre dos registros, pero que es demasiado peque帽o para poder ser reutilizado
- Solo se produce con registros de longitud variable con la tecnica de peor ajuste.
La caracteristica fundamental de un indice es que posibilita imponer un orden en un archivo sin que realmente se reacomode
- Tiene registros de longitud fija
- Altas Se agrega al final
- Modificaciones Si el archivo esta organizando por registros de longitud fija, el indice no se toca, si se cambia de tama帽o, se reubica
La principal ventaja radica en las bajas
Al ser de menor tama帽o que el archivo asociado y tener registros de longitud fija, posibilita mejorar la performance de busqueda, se pueden realizar busquedas binarias
Son claves primarias que por algun motivo, no se usaron
Es una estructura de datos adicional que permite relacionar una clave secundaria con una o m谩s claves primarias. Varios registros pueden contener la misma clave secundaria
- Primero se accede a un indice primario por una clave secundaria
Cualquier alta en el archivo de datos genera una inserci贸n en el 铆ndice secundario, que implica reacomodar el archivo en el cual se almacena.
Cuando se elimina un registro del archivo de datos, esta operaci贸n implica elminar la referencia a ese registro en el indice primario m谩s todas las referencias en indices secundarios.
Es una estructura de datos din谩mica no lineal, en la cual cada nodo puede tener a los sumo dos hijos
Una ventaja en la organizaci贸n mediante 谩rboles binarios est谩 dada en la inserci贸n de nuevos elementos, mientras que en un archivo se desordena cuando se agrega un nuevo dato, si la organizaci贸n se realiza con la politica de arbol binario, la operatoria resulta m谩s sensilla en terminos de complejidad computacional.
- Agregar el nuevo elemento de datos al final de archivo.
- Busca al padre de dicho elemento. Para ello se recorre el archivo desde la raiz hasta llegar a un nodo terminal.
- Actualiza el padre, haciendo referencia a la direcci贸n del nuevo hijo.
Borrado es casi lo mismo
La desventaja Es que tengo que crear un arbol por cada campo que quiero ordenar.
Se entiende por arbol balanceado a aquel arbol donde la trayectoria de la ra铆z a cada una de las hojas est谩 representada por igual cantidad de nodos. Es decir, todos los nodos hoja se encuentran a igual distancia del nodo raiz.
Son arboles binarios cuya construcci贸n se determina respetando un precepto muy simple: La diferencia entre el camino m谩s corto y mas largo entre un nodo terminal y la raiz no puede diferir en mas de un determinado delta y dicho delta es el nivel de balanceo en altura del 谩rbol.
Es una estructura de datos en la cual cada nodo puede contener k elementos y k+1 hijos.
Se define el concepto de orden de un 谩rbol multicamino como la m谩xima cantidad de descendientes posibles de un nodo
Estas reglas son las que comparten los 3 tipos de arboles
- CADA NODO del arbol puede contener como maximo M descendientes y M-1 Elementos
- LA RAIZ no posee descendientes directos o posee al menos dos.
- UN NODO CON x descendietes directos directos contiene x-1 elementos
- TODOS LOS NODOS TERMINALES Se encuentran al mismo nivel
Son arboles multicamino con una construcci贸n especial que permite mantenerlos balanceados a bajo costo
- NODOS TERMINALES Tienen como
- minimo [M/2]-1 Elementos y como
- maximo M-1 Elementos
Inserci贸n
Todos los elementos de datos se insertan en los nodos terminales. Por ese motivo es necesario realizar H lecturas para poder encontrar el nodo donde el elemento ser谩 almacenado (desde la raiz hasta un nodo temrinal)
Si tengo lugar en el nodo, se inserta normal (siempre ordenado)
Si no se produce overflow, solo hago una escritura. En caso de overflow, como se divide el nodo, se necesita la escritura de dos nodos en el nivel terminal, mas la escritura de la raiz.
Si se produce overflow
- Se crea un nodo nuevo..
- La primera mitad de las claves se mantienen en el nodo viejo.
- La segunda mitad de las claves se trasladan al nodo nuevo.
- La menor de las claves de la segunda mitad se promociona al nodo padre.
Busqueda
El procceso de busqueda realiza el mismo proceso que la inserci贸n
- Se comienza desde el nodo raiz, se procede a buscar el elemento en cuesti贸n
Eficiencia de busqueda: Consiste en contar los accesos al archivo de datos, que se requieren para localizar un elemento o para determinar que el elemento no se encuentra.
El resultado es un valor acotado en el rango entero [1, H], siendo H la altura del 谩rbol, tal como fuera definida previamente.
Si el elemento se encuentra ubicado en el nodo ra铆z, la cantidad de accesos requeridos es 1. En caso de localizar al elemento en un nodo terminal, (o que el elemento no se encuentre), ser谩n requeridos H accesos
Eliminaci贸n
Para poder eliminar un elemento el mismo debe estar en un nodo terminal.
Si es un nodo interno, se intercambia con el mayor de sus claves menores, o la menor de sus claves menores.
Existes dos situaciones
- Si se elimina un elemento del nodo terminal y los elementos restantes no est谩n por debajo de la cantidad minima [M/2]-1, no se genera underflow
- Cuando se produce underflow por tener menos que el minimo
- La opci贸n m谩s inmediata es la concatenaci贸n, pero el nodo no puede superar la cantidad maxima de elementos.
- La otra opci贸n es la redistribuci贸n plantea que algun nodo adyacente hermano ceda elementos al nodo que precenta insuficiencia (La ventaja es que no cambia la cantidad de nodos)
Eficiencia en la eliminaci贸n
- Mejor caso Cuando se borra un elemento del nodo y no tiene insuficiencia
- H Lecturas y 1 Escritura
- Peor caso Cuando se borra un elemento del nodo y tiene insuficiencia
- 2*H-1 Lecturas y H-1 Escrituras
Actualizaci贸n
Es pensar en una baja mas un alta de un elemento.
Son aquellos nodos que tienen el mismo nodo padre
Son aquellos nodos que, siendo hermanos, son adem谩s dependientes de punteros consecutivos del padre.
Es casi igual al arbol B pero en lugar de dividir y generar un nuevo nodo en los casos de overflow, este mismo distribuye en esos casos. Al crear menos nodos, el arbol tarda m谩s en aumentar de altura.
En saturaci贸n reubica sus elementos en un nodo adyacente hermano. Cuando no sea posible esta redistribuci贸n, se estar谩 en una situaci贸n donde tanto el nodo que genera overflow como su adyacente hermano est谩n completos. Esto abre la posibilidad de dividir partiendo de dos nodos completos en dos terceras partes (2/3)
- NODOS TERMINALES Tienen, como
- minimo [(2M-1)/3]-1 Elementos y como
- maximo M-1 Elementos
- NODOS NO TERMINALES NI RAIZ Tienen, como
- minimo (2M-1)/3 Descendientes
*Busqueda
Es igual que el arbol B
Baja
Es igual que el arbol B
Inserci贸n
Tenemos diferentes formas de aplicar la redistribuci贸n
- Politica de un lado
- Politica de un lado u otro lado
- Politica de un lado y otro lado
Es aquel que permite dos formas de visualizar la informaci贸n
- Indizada: El archivo puede verse como un conjunto de registros, ordenados por una clave o llave.
- Secuencial: Se puede acceder secuencialmente al archivo, con registros f铆sicamente contiguos y ordenados nuevamente por una clave o llave
Los arboles anteriores nos permiten recuperar elementos en forma ordenada a bajo costo, sin necesitad de reacomodamientos fisicos costosos.
Ahora necesitamos un mecanismo que nos permita localizar los datos contenidos en los nodos a bajo costo
La estructura intermedia se denomina arbol B e incorpora las caracteristicas discutidas para 谩rboles B, ademas del tratamiento secuencial ordenado del archivo.
Importante: Se pueden realizar busquedas aleatorias rapidas de informaci贸n, en conjunto con acceso secuencial eficiente
SOLO ACCESO SECUENCIAL NO BUSQUEDA
- Los nodos terminales representan un conjunto de datos y son enlazados entre ellos.
Insetar
- Sin Overflow no pasa nada
- Con Overflow el nodo se divide, y se crea una copia de la menor de las claves del hijo derecho. Solo ante la saturaci贸n de un nodo terminal se promociona una copia, en caso contrario, se promociona el elemento normal.
Es un arbol B+ donde los separadores estar representados por la m铆nima expresi贸n posible de la clave, que permite decidir si la busqueda se realiza hacia la izquierda o hacia la derecha
LOS ARBOLES SON IMPORTANTES PARA BUSQUEDAS ALEATORIAS Y ACCESO SECUENCIAL
Definiciones
- Tecnica para generar direcci贸n base 煤nica para una clave dada. La dispersi贸n se usa cuando se requiere acceso r谩pido mediante una clave.
- T茅cnica que convierte la clave asociada a un registro de datos en un numero aleatorio, el cual posteriormente es utilizado para determinar d贸nde se almacena dicho registro.
- T茅cnica de almacenamiento y recuperaci贸n que usa una funci贸n para mapear registros en direcciones de almacenamiento secundario.
Ventajas
- Inserci贸n y Borrado m谩s eficientes (en promedio un acceso)
- Para busquedas lo mismo, en promedio es 1
Desventajas
- No es posible aplicar HASHING sobre registros de longitud variable
- No es posible obtener un orden logico de los datos. Los indices imponen la propiedad de orden, esto en hashing no es posible.
- No es posible tratar con claves duplicadas( No se puede aplicar una funci贸n de hash sobre una clave secundaria)
Hashing con espacio de direccionamiento Estatico: Es aquella politica donde el espacio disponible para dispersar los registros de un archivo de datos est谩 fijado previamente.
Asi, la funci贸n de hash aplicada a una clave da como resultado una direcci贸n f铆sica posible dentro del espacio disponible para el archivo.
Hashing con espacio de direccionamiento Dinamico: Es aquella politica donde el espacio disponible para dispersar los registros de un archivo de datos aumenta o disminuye en funci贸n de las necesidades de espacio que en cada momento tiene el archivo.
Asi, la funci贸n de hash aplicada a una clave da como resultad un valor intermedio que sera utilizado para obtener la direcci贸n f铆sica posible para el archivo. Estas direcciones f铆sicas no est谩n establecidas a priori y son generadas de manera din谩mica.
- Funci贸n de hash
- Tama帽o de cada nodo de almacenamiento
- Densidad de empaquetamiento
- Metodos de tratamiento de desbordes (overflow)
Es una funci贸n que transforma un valor, que representa una llave primaria de un registro, en otro valor dentro de un determindo rango, que se utiliza como direcci贸n fisica de acceso para insertar un registro en un archivo de datos.
Es la relaci贸n entre el espacio disponible para el archivo de datos y la cantidad de registros que integran dicho archivo
Me fui a rendir, ya fue