Ejercicios Organización de Archivos

1. Sea un Árbol B con capacidad para 3 claves en nodos internos y para 5 en nodos hoja, y con claves automáticas.
   • Muestre el estado del árbol tras cargarlo con las claves 1 a 23.
   • Muestre el estado del árbol tras cargar la clave 24.
   • Indique en qué otra situación se utiliza la primitiva de alta de carga.
2. Sea un árbol B con capacidad para 3 elementos en nodos internos y 5 en nodos hojas, con el siguiente estado inicial:

   0: 1( 464) 3( 527) 2( 666) 4
   1: ( 63)( 269)( 354)
   3: ( 467)( 500)
   2: ( 532)( 542)( 550)( 559)( 651)
   4: ( 734)( 863)( 979)

   • Indicar qué nodos se leen o escriben y mostrar los estados sucesivos para las siguientes operaciones: alta 600, baja 651, baja 734.
   • Mostrar el estado de un árbol B+ con capacidad para 3 elementos en nodos internos y 4 en hojas producto de convertir el árbol B inicial, y con carga al 75%.
3. Dado el siguiente árbol con capacidad para 3 elementos en nodos internos, y 5 en hojas:

   0: 1( 583) 3( 790) 2
   1: ( 59)( 166)( 204)( 500)( 525)
   3: ( 596)( 711)
   2: ( 858)( 862)( 882)( 899)

   • Grafique los estados sucesivos al efectuar las siguientes operaciones, e indique los nodos leídos y escritos para cada una: baja 583, alta 300, baja 500.
   • Suponiendo que las claves del árbol representan registros de datos de 297 bytes, calcule las capacidades mínimas y máximas de nodos internos y hoja en términos de cantidades de registros, para implementarlo con nodos de 4 Kb.
4. Dada la siguiente definición

   Persona((dni)i, apellido, nombres, fNac) 

   • Defina en C estructuras y firmas de funciones para todas las primitivas de organización comentando sus objetivos
   • Defina clases en C++ para organizar este archivo
5. Dado el árbol B+ con el estado inicial que se muestra abajo, con capacidad para 3 registros en nodos internos y para 4 en hojas:
   • Grafique los estados sucesivos resultantes de las operaciones: baja 27, baja 421, alta 700 y alta 800.
   • Indique los nodos que se deben leer para la búsqueda de 725 en el árbol final e indique el resultado.
   • Asumiendo que las claves ocupan 4 bytes y representan registros que ocupan 237 bytes, que los números de nodos ocupan 1 byte, y que los nodos tienen un campo de control de un byte para indicar si son de índice o de secuencia y otro campo de un byte para indicar cuántos elementos tiene, calcular las capacidades de nodos de 2048 bytes.

     0: 7 ( 573) 6
     7: 2 ( 176) 8 6: 1 ( 658) 9( 900) 4
     2: ( 3)( 27) 8 8: ( 350)( 421)( 428) 1 1: ( 573)( 592)( 619) 9 9: ( 658)( 724)( 797) 4 4: ( 900)( 965)( 969) 0 

6. Suponga que un árbol B tiene h niveles (para llegar a una hoja se debe leer h-1 nodos, ya que la raíz se supone está siempre en RAM), y que otro árbol B* con carga mínima 2/3 tiene h* niveles.
   • Indique para cada árbol la cantidad de lecturas y escrituras necesarias para resolver un alta tanto en el mejor (sin ningún sobreflujo) como en el peor (con sobreflujo en todos los niveles) de los casos posibles. Exprese las fórmulas en términos de h y de h* y justifíquelas.
   • Explique la diferencia entre las primitivas de baja de ambos árboles.
7. Análisis comparativo de organizaciones balanceadas:
   • Indique las diferencias en la primitiva de alta de registros entre organizaciones B y B*.
   • Indique las diferencias en la primitiva de baja de registros entre organizaciones B y B+.
8. Dado el archivo B+ con nodos de secuencia con capacidad 4 y nodos índice con capacidad 3 con el siguiente estado inicial:

   0: 2( 275) 4( 418) 3( 563) 1
   2: ( 21)( 59)( 120)( 150) 4 4: ( 300)( 313) 3 3: ( 418)( 547) 1 1: ( 563)( 716) 0 

   • Grafique el estado posterior e informe el costo en lecturas y escrituras de cada operación, realizada en el siguiente orden: alta 200, baja 418, baja 300.
   • Recalcule las capacidades de los nodos del archivo considerando que los registros son de 143 bytes, las referencias a nodos y el indicador de contenido de 2 bytes, el indicador de nivel de 1 byte y que el tamaño de los nodos es de 2 Kb.
9. Se desea organizar registros de datos de longitud fija de 244 bytes e identificadores de 4 bytes en un árbol B# con nodos de 4 Kb. Defina lógicamente cada tipo de nodo para direcciones

1. Sea un archivo directo con cubetas para dos registros y organización de desbordes por saturación lineal.
   • Cárguelo al 70% con las claves 1239, 2461, 1837, 2246, 2149, 991 y 2547, y muestre su estado
   • Elimine la clave 2461, muestre el estado del archivo tras la operación e indique qué cubetas leyó y escribió para efectuarla.
   • Inserte la clave 1001, muestre el estado del archivo tras la operación e indique qué cubetas leyó y escribió para efectuarla. Tenga en cuenta que las inserciones normales se realizan con validación de unicidad de clave.
2. Se dispone de un archivo secuencial desordenado con 12743 registros de longitud variable con promedio 231 y se lo quiere reorganizar como directo con bloques de 4 Kb y con dispersión doble usando como segunda función h2(k)=k mod 7+2.
   • Determinar el tamaño en bloques con que se debe crear el archivo previendo que su cantidad de registros puede llegar a crecer un 25%.
   • Describa algorítmicamente cómo se resuelve un desborde en un alta normal en el archivo.
3. Se dispone de un archivo secuencial de 39746 registros de longitud variable desordenados, con longitud promedio de 239 bytes, con el que se desea cargar un archivo directo con áreas de desborde intercaladas con bloques de 2 Kb.
   • Indique la cantidad de bloques con los que inicializaría el archivo para cargarlo con una densidad del 80%, con una saturación esperada del 5%.
   • Especifique una función de dispersión h(k), k identificador numérico de los registros.

1. Detalle alternativas para implementar índices de clasificación con organización B.
2. Se dispone de un archivo de datos cuyos registros tienen un identificador primario IP de 4 bytes, y se desea construir un índice secundario de clasificación por un atributo AC de 14 bytes. Defina dos estructuras alternativas para organizar al índice secundario como árbol B+, determinando un tamaño de nodo práctico e informando las capacidades de los nodos índices y de secuencias para cada alternativa.
3. Sea un archivo

   Datos((a)i, b, (c)?, d)

   con un índice

   Datos-c((c)i, (a)+)

   en los que a es un entero de 2 bytes, b es una cadena de caracteres de hasta 255 bytes y c y d son enteros de 4 bytes.

   • Indique si Datos-c es primario o secundario, si es de identificación o de clasificación, y si es exhaustivo o selectivo y por qué.
   • Especifique las definiciones lógicas de Datos, de Datos-c y sus archivos de control necesarios para organizarlos como archivos directos con dispersión extensible.
   • Especifique algorítmicamente cómo se actualiza Datos-c tras el alta de un registro en Datos.
4. Dadas las siguientes definiciones lógicas de archivos para un servicio de consultorios externos de un hospital, clasifíquelos como maestros o transaccionales y proponga y justifique organizaciones adecuadas:

   Medico((matricula)i, apellido, nombre, tel)
   Paciente((dni)i, apellido, nombre, tel)
   Turno(((medico(matricula))ie, fecha, hora)i, ((paciente(dni))ie)?)
   Diagnostico((codDiagn)i, nombre)
   Medicamento((codMed)i, nombre)
   Prescripciones((((medico(matricula))ie, fecha, hora, (diagnostico(codDiagn))ie)ie)i,
   (prescrip(medicamento(codMed))ie, presentacion, dosisUnidad, dosisDia, diasTratamiento)+)
   //para cada diagnóstico efectuado en un turno se puede prescribir más de un medicamento

Tenga en cuenta que para dar turnos se crean periódicamente registros con dni de paciente nulo y que se debe poder consultar a qué paciente se le prescribió medicamentos en un turno (indique cómo resolver esto).