rendimiento y organizaciÓn de archivos
DESCRIPTION
RENDIMIENTO Y ORGANIZACIÓN DE ARCHIVOS. - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: RENDIMIENTO Y ORGANIZACIÓN DE ARCHIVOS](https://reader036.vdocumento.com/reader036/viewer/2022082422/56813b72550346895da47be1/html5/thumbnails/1.jpg)
RENDIMIENTO Y ORGANIZACIÓN DE ARCHIVOS
![Page 2: RENDIMIENTO Y ORGANIZACIÓN DE ARCHIVOS](https://reader036.vdocumento.com/reader036/viewer/2022082422/56813b72550346895da47be1/html5/thumbnails/2.jpg)
En este documento se compara el coste de algunas operaciones simples en varias organizaciones de archivo básicas sobre una colección de archivos de empleado.
Se supondrá que los archivos e índices están organizados de acuerdo a la clave de búsqueda compuesta(edad, sueldo) y que las operaciones de selección están sobre estos campos.
Las organizaciones que se consideran son:
- Archivos de registros de empleados ordenados de forma aleatoria en un archivo de montículo.- Archivo de registros de empleados ordenado por (edad, sueldo).- Archivo de árbol B+ agrupado por (edad, sueldo).- Archivo de árbol B+ no agrupado por (edad, sueldo).- Archivo de Montículo con un índice no agrupado por (edad, sueldo).
![Page 3: RENDIMIENTO Y ORGANIZACIÓN DE ARCHIVOS](https://reader036.vdocumento.com/reader036/viewer/2022082422/56813b72550346895da47be1/html5/thumbnails/3.jpg)
OPERACIONES A REALIZAR
• Nótese que si el archivo de datos está ordenado. !un índice cuya clave de búsqueda difiera del orden del archivo se comporta como un índice sobre archivo de montículo.
• Las operaciones que se consideran son:– Exploración: Lee todos los registros del archivo.– Búsqueda con selección de igualdad: Lee todos los registros que
satisfacen una selección de igualdad; ejemplo: “Determinar el registro de empleados con edad 23 y sueldo 50”
– Búsqueda con selección por rango: Lee todos los registros que satisfacen una selección por rango; “Los registros de empleados con edad mayor a 35”.
– Insertar un registro: Insertar un registro en el archivo, se debe identificar la página en la que se debe insertar el registro.
– Borrar un registro: borrar un registro identificado por un criterio de búsqueda, se debe encontrar la página, leerla, modificarla y escribirla en disco.
![Page 4: RENDIMIENTO Y ORGANIZACIÓN DE ARCHIVOS](https://reader036.vdocumento.com/reader036/viewer/2022082422/56813b72550346895da47be1/html5/thumbnails/4.jpg)
MODELO DE COSTE
• B: número de páginas de datos cuando los registros están distribuidos en páginas sin desperdiciar espacio.
• R: número de registros por página.• D: tiempo medio para leer o escribir una página en disco.• C: tiempo medio para procesar un registro (comparar el
contenido del registro)..• Función de asociación: se utiliza para corresponder un
registro en un rango de números.• H: tiempo requerido para aplicar la función de asociación
a un registro.
![Page 5: RENDIMIENTO Y ORGANIZACIÓN DE ARCHIVOS](https://reader036.vdocumento.com/reader036/viewer/2022082422/56813b72550346895da47be1/html5/thumbnails/5.jpg)
MODELO DE COSTE: VALORES TÍPICOS
• D =15 milisegundos.• C y H = 100 nanosegundos.• Se debe considerar también la velocidad del
CPU y el tráfico generado al transmitir datos.
![Page 6: RENDIMIENTO Y ORGANIZACIÓN DE ARCHIVOS](https://reader036.vdocumento.com/reader036/viewer/2022082422/56813b72550346895da47be1/html5/thumbnails/6.jpg)
ARCHIVOS EN MONTÍCULO• Exploración: el coste es B(D+RC) pues hay que recuperar cada una de
las B páginas tomando un tiempo D por página y para cada página procesar los B registros con un tiempo C por registro.
• Búsqueda por selección de igualdad: – Suponiendo que el registro exista en promedio se debe leer la mitad del
archivo 0,5B(D+RC).– En caso que no exista el registro se debe leer todo el archivo. – Sino se busca por un criterio de clave candidata se debe leer todo el archivo y
no se sabe cuantos registros cumplen el criterio.• Búsqueda por selección de rango: no se sabe donde están ubicados los
registros que satisfacen el criterio de búsqueda el coste es B(D+RC).• Inserción: se insertan los registros al final del archivo, es necesario leer la
última página del archivo, añadir el registro y escribir la página, el coste es: 2D+C
• Borrado: Es el cote búsqueda + (C+D); sin considerar compactación.
![Page 7: RENDIMIENTO Y ORGANIZACIÓN DE ARCHIVOS](https://reader036.vdocumento.com/reader036/viewer/2022082422/56813b72550346895da47be1/html5/thumbnails/7.jpg)
ARCHIVOS ORDENADOS• Exploración: el coste es B(D+RC), obsérvese que este caso no es mejor ni peor que los
archivos no ordenados.• Búsqueda por selección de igualdad:
– Suponiendo que la selección de igualdad se corresponde con el criterio de ordenación (edad, sueldo) (al menos edad=30 o sueldo=50)
– Se puede encontrar la primera página con una búsqueda binaria log2B, cada paso posterior para encontrar todos los registros que cumplen la condición requieren de una operación E/S y dos comparaciones.
– Una vez encontrada la página el primer registro puede encontrarse nuevamente haciendo una búsqueda binaria cuyo coste es Clog2R por tanto el coste es Dlog2B+Clog2R.
• Búsqueda por selección de rango: suponiendo que la selección es por el criterio de búsqueda (edad, sueldo) el coste es similar a la búsqueda por selección de igualdad para varios registros que cumplan la condición.
• Inserción: para insertar un registro y mantener el orden es necesario encontrar la posición correcta en el archivo, añadir el registro y después leer y reescribir todas las páginas posteriores. El coste es el correspondiente a encontrar la posición del registro nuevo 2(0,5(D+RC)) es decir coste de búsqueda B(D+RC).
• Borrado: Es necesario buscar el registro, borrarlo de la página y escribir la página.
![Page 8: RENDIMIENTO Y ORGANIZACIÓN DE ARCHIVOS](https://reader036.vdocumento.com/reader036/viewer/2022082422/56813b72550346895da47be1/html5/thumbnails/8.jpg)
COMPARACIÓN DE LOS COSTES E/STipo de Archivo
Exploración Búsqueda por Igualdad
Búsqueda por Rango
Inserción Borrado
Montículo BD 0,5BD BD 2D Búsq+D
Ordenado BD DLog2B DLog2B+núm paso sel.
Búsq+BD Búsq+BD
Agrupado 1,5BD DLogF1,5B DLogF1,5B+núm. paso sel.
Búsq+D Búsq+D
Índice en árbol no agrupado
BD(R+0,15) D(1+LogF0,15B)
D(1+LogF0,15B)+núm. pasos sel.
D(3+LogF0,15B) Búsq+2D
Índice asociativo no agrupado
BD(R+0,125) 2D BD 4D Búsq+2D
![Page 9: RENDIMIENTO Y ORGANIZACIÓN DE ARCHIVOS](https://reader036.vdocumento.com/reader036/viewer/2022082422/56813b72550346895da47be1/html5/thumbnails/9.jpg)
ÍNDICES Y AJUSTES DE RENDIMIENTO
• La elección de los índices tiene un impacto enorme en el rendimiento del sistema y debe realizarse en el contexto de la carga de trabajo es decir la combinación más habitual de operaciones y actualización.
• El tratamiento completo de índices y su rendimiento requiere entender lqa evaluación de consultas de la base de datos y el control de concurrencia.