Download Estructuras Basicas de Archivos
Transcript
UNIDAD 2 ORGANIZACIÓN DE ARCHIVOS 1 Temario 2.1 Estructuras Básicas de Archivos 2.2 Técnicas de Indexación 2 Estructuras de Archivos • Una estructura de archivos es una técnica para agrupar físicamente los registros de un archivo en dispositivos de almacenamiento secundario. 3 Estructuras de Archivos Aspectos a Considerar • Características físicas de los dispositivos de almacenamiento. • Sistema Operativo existente. • Software para la administración de archivos. • Necesidades del usuario para almacenar y accesar datos. 4 Estructuras de Archivos Criterios Importantes • Acceso rápido para la recuperación de datos. • Alto rendimiento para las transacciones de procesamiento. • Uso eficiente del espacio en disco. • Protección ante pérdida de datos y fallas. • Minimización de la necesidad de reorganización de los datos. 5 Estructuras de Archivos Organización Lógica de los Datos • Considera la visión del programador (o desarrollador) de aplicaciones. • Un archivo es visto como una colección de registros estructurados, normalmente, en torno a una clave. • Es una visión independiente del dispositivo, donde interesa el uso de los datos más que sus aspectos físicos. 6 Estructuras de Archivos Organización Lógica de los Datos • • • • • Recorrer el archivo Agregar registros al archivo Eliminar registros del archivo Modificar valores del archivo Ordenar el archivo 7 Estructuras de Archivos Organización Lógica de los Datos a) Registro: corresponde a la definición de cada uno de los registros de datos que serán usados dentro de una aplicación, y cuya extensión determina el tipo de archivo que lo contiene Dependiendo de los tipos de registros que un archivo contenga, éste puede ser de largo fijo o de largo variable... 8 Estructuras de Archivos Organización Lógica de los Datos • Archivo de Largo Fijo: el archivo se compone de registros del mismo tipo. • Archivo de Largo Variable: • El archivo se compone de registros del mismo tipo, pero al menos uno de los campos tiene un número de ocurrencias variable. • El archivo se compone de registros del mismo tipo, pero el largo de al menos uno de sus campos es variable. • El archivo se compone de registros del mismo tipo, pero uno de los campos es opcional en cuanto a su tipo. • El archivo se compone de más de un tipo de registro. 9 Estructuras de Archivos Organización Lógica de los Datos b) Campo o Atributo (clave): ítem de dato que describe una característica de la entidad representada por un registro lógico... Clave Candidata: atributo(s) que no soporta(n) valores repetidos. Identificador o Clave Primaria: clave candidata escogida como clave de acceso principal al archivo. Clave Alternativa: clave candidata que no es escogida como identificador. Clave Secundaria: atributo que permite valores repetidos. Clave Inteligente: atributo cuyo contenido permite derivar información adicional de la entidad a la cual pertenece. 10 Estructuras de Archivos • Las diversas estructuras de archivos existentes se pueden dividir en tres grupos: • Archivos Secuenciales: los registros de datos se almacenan en forma contigua. • Archivos Directos: los registros de datos se ubican a partir de una posición, que se obtiene de un atributo que es escogido como clave hashing. • Archivos organizados como Árboles: los registros de datos se guardan en base a un atributo, ordenadamente, según una relación jerárquica y basada en los valores de dicho atributo. 11 Estructuras de Archivos Archivos Secuenciales • Los registros son almacenados en secuencia, uno tras otro. Características: • Es la más simple de usar. • Espacio ocupado es el mínimo, pues sólo se almacenan los datos. • Se pueden identificar dos tipos de archivos secuenciales: desordenado y ordenado. 12 Estructuras de Archivos Archivos Secuenciales Desordenados • Los registros se almacenan unos tras otros, según el orden en que van siendo ingresados • Operaciones • Búsqueda: Se realiza en forma lineal. • Inserción: Se realiza al final del archivo, lo que hace que la operación sea rápida. • Eliminación: Se puede presentar de dos formas: • Física: lo cual implica corrimientos de los datos, para cubrir la entrada liberada (costoso). • Lógica: a través de marcas de borrado. 13 Estructuras de Archivos Archivos Secuenciales Desordenados Archivo Secuencial Desordenado (factor de bloqueo 4) 14 Estructuras de Archivos Archivos Secuenciales Ordenados • Los registros se encuentran almacenados en forma ordenada (ascendente o descendentemente) respecto del valor de un campo de ordenamiento. • Favorece las búsquedas y la generación de listados ordenados. • Operaciones • Búsqueda: Se realiza en forma lineal y/o binaria. • Inserción: Requiere un corrimiento de los registros para mantener el orden... 15 Estructuras de Archivos Archivos Secuenciales Ordenados Archivo Secuencial Ordenado, ordenado por el campo Nombre 16 Estructuras de Archivos Archivos Secuenciales Ordenados • ...el que se puede evitar... • Dejar los bloques de datos a medio llenar, para reservar espacio para posibles inserciones futuras. Mientras no se llenen, habrá desperdicio de memoria. • Mantener un área de overflow a continuación del área de datos, con campos punteros que apunten a ésta. • Incluir a cada bloque de datos un puntero que direccione a una lista enlazada de bloques de overflow. Puede aumentar las búsquedas. • Se considera el archivo real de datos como el archivo maestro o principal, y se van almacenando en un archivo de overflow no ordenado. Al actualizar el maestro, se debe ordenar el archivo de overflow y luego realizar la mezcla de los archivos. 17 Estructuras de Archivos Archivos Secuenciales Ordenados • Eliminación: Se puede presentar de dos formas: • Física: lo cual provoca grandes espacios libres en cada bloque. • Lógica: a través de marcas de borrado. • En ambos casos, es necesario hacer una reorganización de los registros. 18 Estructuras de Archivos Archivos Secuenciales Ordenados • Ordenamiento Externo: • Aplicable a archivos que por su tamaño no pueden ordenarse en memoria principal. • Consta de dos fases: una fase de ordenamiento y una fase de mezcla. 19 Estructuras de Archivos Archivos Secuenciales Ordenados • Fase de Ordenamiento: • Se leen datos que son almacenados en memoria principal, en un área de ordenamiento. • Usando una rutina de ordenamiento interno obtiene los registros ordenados, los que son escritos en dos o más archivos (particiones) en memoria secundaria. • Los registros en las particiones quedan ordenados en forma relativa a cada una de ellas • Posteriormente se mezclan las particiones. 20 Estructuras de Archivos Archivos Secuenciales Ordenados • Fase de Mezcla: • Se combinan los archivos obtenidos en la fase anterior, es decir, se mezclan las particiones generadas en la fase de ordenamiento, produciendo particiones más grandes hasta llegar a una sola partición: el archivo ordenado. 21 Estructuras de Archivos Archivos Secuenciales Ordenados • Fase de Mezcla: 22 Estructuras de Archivos Archivos Secuenciales Ordenados • Algoritmos de Ordenamiento Interno: • Ordenamiento Interno: consiste en leer M registros de una vez desde el archivo desordenado, luego se ordenan a través de un algoritmo de ordenamiento interno y se generan particiones de salida. Se asume que M es el tamaño de la memoria principal disponible (tamaño del buffer). 23 Estructuras de Archivos Archivos Secuenciales Ordenados • Ejemplo: suponer que se tiene un archivo de entrada desordenado con el siguiente contenido: 109 49 34 68 45 2 60 38 28 47 16 19 34 55 98 78 76 40 35 86 10 27 61 92 99 72 11 2 24 Estructuras de Archivos Archivos Secuenciales Ordenados • Al considerar que se tiene un buffer con capacidad para cinco registros, el resultado es: 34 45 49 68 109 2 28 38 47 60 16 19 34 55 98 35 40 76 78 86 10 27 61 92 99 2 11 72 25 Estructuras de Archivos Archivos Secuenciales Ordenados • Algoritmos de Ordenamiento Interno: (cont.) • Selección por Reemplazo: consiste en leer M registros, e ir generando archivos de salida aprovechando algún ordenamiento parcial que pueda existir en el archivo de entrada. Se asume que M es el tamaño de la memoria principal disponible (tamaño del buffer). 26 Estructuras de Archivos Archivos Secuenciales Ordenados • Suponer que se tiene un archivo de entrada desordenado con el siguiente contenido: 109 49 34 68 45 2 60 38 28 47 16 19 34 55 98 78 76 40 35 86 10 27 61 92 99 72 11 2 27 Estructuras de Archivos Archivos Secuenciales Ordenados • El resultado de aplicar el algoritmo de selección por reemplazo es: 34 2 10 2 45 16 27 11 49 19 35 60 28 40 68 34 61 109 38 72 47 92 55 99 76 78 86 98 28 Estructuras de Archivos Archivos Secuenciales Ordenados • De esta etapa es importante destacar: • Al tener particiones grandes, se requerirán menos mezclas; sin embargo, esto no es el único criterio a considerar para seleccionar un algoritmo. • Una ventaja del ordenamiento interno es que genera particiones del mismo tamaño, excepto la última. • La selección por reemplazo, en promedio, produce particiones más grandes que el ordenamiento interno. 29 Estructuras de Archivos Archivos Secuenciales Ordenados • Algoritmos para la Mezcla: • Mezcla N-way balanceada: Las particiones son agrupadas en tres conjuntos, lo más cercanos posibles en cuanto al número de registros que contengan. Los registros de los archivos de entrada son leídos y las particiones mezcladas son distribuidas en los archivos de salida. Esto se realiza en varias fases, alternando el rol de los archivos entre éstas... 30 Estructuras de Archivos Archivos Secuenciales Ordenados Inicialmente Archivo 1 Archivo 2 10 x 1 10 x 1 Después de Fase 1 Después de Fase 2 3x4 Después de Fase 5 1 x 16 Archivo 4 5x2 5x2 1 x 8, 1 x 4 1x8 2x4 Después de Fase 3 Después de Fase 4 Archivo 3 1x4 1 x 20 31 Estructuras de Archivos Archivos Secuenciales Ordenados • Algoritmos para la Mezcla: (cont.) • Mezcla Polifásica: variación no balanceada de la mezcla N-way.... Archivo 1 Archivo 2 Archivo 3 Inicialmente Después de Fase 1 13 x 1 6x1 11 x 1 4x1 7x1 Después de Fase 2 2x1 Después de Fase 3 Después de Fase 4 Después de Fase 5 1 x 17 Archivo 4 Lecturas 7x3 21 4x5 3x3 20 2x9 2x5 1x3 18 1x9 1x5 17 1 x 31 31 32 Estructuras de Archivos Archivos Secuenciales Ordenados • Algoritmos para la Mezcla: (cont.) • Mezcla Óptima: Las particiones iniciales son escritas en archivos separados, así se tiene un conjunto de F archivos cada uno con una partición. Durante cada fase, las F-1 particiones más pequeñas son leídas y mezcladas, y la partición mezclada es escrita en un archivo de salida. Los archivos de entrada son removidos del conjunto y los archivos de salida son agregados. El proceso se repite hasta que el conjunto contiene un único archivo... 33 Estructuras de Archivos Archivos Secuenciales Ordenados Fase Archivo de Entrada 2 2:1 Archivo de Entrada 3 3:1 Archivo de Salida 21:3 Lecturas 1 Archivo de Entrada 1 1:1 2 4:1 5:1 6:1 22:3 3 3 7:1 8:1 9:1 23:3 3 4 10:1 11:1 12:1 24:3 3 5 13:1 14:1 15:1 25:3 3 6 16:1 17:1 18:1 26:3 3 7 19:1 20:1 21:3 27:5 5 8 22:3 23:3 24:3 28:9 9 9 25:3 26:3 27:5 29:11 11 10 28:9 29:11 30:20 20 3 34 Estructuras de Archivos Archivos Secuenciales Mixtos • Es posible almacenar en un mismo archivo registros de diferentes tipos (lo que da origen a un archivo de largo variable). • Para distinguir los registros de un archivo mixto, cada registro tiene, además de los campos propios, un campo llamado tipo_registro, el cual especifica el tipo de registro. 35 Estructuras de Archivos Archivos Directos • Una segunda alternativa para estructurar archivos se basa en la idea de poder alcanzar un registro en forma directa, sin tener que accesar los registros almacenados antes del requerido. Para tal fin, existen los siguientes tipos de direccionamiento: • Direccionamiento Directo: absoluto o relativo. • Direccionamiento Indirecto (hashing). 36 Estructuras de Archivos Archivos Directos • Direccionamiento Directo: • Absoluto: el programa entrega una dirección de hardware (#cilindro, #pista, #sector) y el método de acceso ubica el registro en dicha posición. • Relativo: el programa entrega un número relativo a la posición del primer registro en el archivo y el método de acceso ubica el registro. 37 Estructuras de Archivos Archivos Directos • Ventajas: del direccionamiento absoluto. • No existe transformación previa de la clave primaria. • No existen problemas de colisiones. • Fácil acceso secuencial, pues las claves pueden ser asignadas en forma ordenada. 38 Estructuras de Archivos Archivos Directos • Desventajas: del direccionamiento absoluto. • Es difícil que la clave primaria pueda ser una dirección de hardware (suelen ser códigos inteligentes para el usuario y no para la máquina). • Cualquier cambio de hardware o falla de él, significaría rehacer la asignación de claves. • Claves deben definirse en base a características físicas del dispositivo, y no a lo que le conviene al usuario. 39 Estructuras de Archivos Archivos Directos • Archivos Relativos: direccionamiento relativo. • Conjunto de datos que se pueden accesar directamente, conociendo la posición que tenga un determinado registro, (posición relativa con respecto al comienzo del archivo) • Dicha posición se puede obtener: • Directamente del valor de un campo del registro (número de lista en un curso, lugar de llegada, etc.) • Función sobre un determinado campo del mismo registro (este esquema presenta el problema de las llamadas colisiones). 40 Estructuras de Archivos Archivos Directos • Archivos Relativos: direccionamiento relativo. • Antes de cualquier operación de ingreso de datos, es preciso crear el archivo con tantos registros en blanco como sean necesarios a futuro. • Un registro en blanco se puede construir de dos formas: • Escoger un campo (clave) el cual no puede tener valores nulos en un registro activo. • Agregar a cada registro un campo adicional, de tipo lógico, cuyo valor determine si el registro está activo o no. 41 Estructuras de Archivos Archivos Directos • Archivos Relativos: direccionamiento relativo. • Búsqueda: a través de la posición relativa. En el caso de que se desee accesar todos los registros (activos) del archivo, se debe hacer una búsqueda lineal, pero tomando en cuenta para la salida aquellos registros que no “estén en blanco”. • Inserción: a través de la posición relativa. • Eliminación: a través de la posición relativa. Consiste en anular el valor del campo (clave) o del campo lógico, dependiendo del caso, que determina si el registro es nulo o no. 42 Estructuras de Archivos Archivos Directos • Direccionamiento Indirecto: algorítmico o hashing. • La dirección a ser usada para ubicar el registro se obtiene con una función de transformación al valor de la clave primaria. • El espacio de almacenamiento es dividido es secciones llamadas buckets, que pueden almacenar uno o más registros lógicos. • Un bucket es un bloque del disco o un grupo de bloques de disco. Está dividido en casilleros de tamaño fijo denominados slots. 43 Estructuras de Archivos Archivos Directos • Direccionamiento Indirecto: algorítmico o hashing. • En la actualidad, la mayoría de los SABD implementan sólo este esquema, por lo que en el resto del curso sólo se tratarán los archivos de tipo hashing. • Dos tipos de archivos hashing: • Estático: archivo de tamaño fijo. • con Expansión Dinámica: archivo de tamaño variable. 44 Estructuras de Archivos Archivos Directos • Archivos de tipo Hashing Estático: • La transformación anteriormente mencionada es una función hashing que transforma la clave en un número de bucket relativo. • Una tabla es mantenida en el encabezado del archivo para convertir el número de bucket en la dirección de bloque de disco. 45 Estructuras de Archivos Archivos Directos • Archivos de tipo Hashing Estático: Ejemplo. Nombre del Tema Intérprete #Estreno Crazy in Love Beyonce & Jay-Z 258 Frantic Metallica 593 Go to Sleep God puts a Smile upon your Face RadioHead Coldplay Here we Kum Hollywood Just Because Sálvame la vida San Miguel Molotov Madonna Jane’s Adiction Lucybell Los Prisioneros 287 125 880 1502 468 Show me How to Live Re-Offender White Flag AudioSlave Travis Dido 450 1473 901 367 342 • Suponer archivo de 10 buckets h(#estreno) = #estreno % 10 46 • Así, por ejemplo el primer registro, de clave 258 le corresponde estar guardado en el bucket h(258) = 258 % 10 = 8. • Al repetir lo anterior con todos los registros del archivo se obtiene el siguiente resultado: 47 Estructuras de Archivos Archivos Directos • Archivos de tipo Hashing Estático. • El uso de un archivo hashing permite recuperar los registros en su base a su clave con un costo a un bloque (o cercano). No obstante, el precio que se paga considera dos posibles tipos de problemas: • Manejo de Áreas Muertas: puede darse que el algoritmo no genere todas las direcciones disponibles para almacenar los datos, por lo cual se generan espacios libres que nunca son direccionados. • Sinónimos o Colisiones: al aplicar la función hashing puede generarse una misma dirección a partir de claves diferentes. Para solucionarlo conviene tener en cuenta las técnicas de tratamiento de overflow. 48 Estructuras de Archivos Archivos Directos • Archivos de tipo Hashing Estático: Manejo de Colisiones. • Una colisión ocurre cuando el valor del campo hashing de un nuevo registro a insertar direcciona a una posición en la cual ya existe un registro • Esto obliga a que el nuevo registro se deba insertar en otra posición, a través de una de las siguientes técnicas de resolución de colisiones: • Direccionamiento Abierto • Encadenamiento • Hashing Múltiple 49 Estructuras de Archivos Archivos de tipo Árbol • Técnicas de Manejo de Colisiones: 1. Direccionamiento Abierto: consiste en almacenar el registro que está en colisión en la siguiente posición disponible del área de datos. • La búsqueda del registro se realiza en forma secuencial a partir de la dirección generada por la función hashing, hasta: • Encontrar una entrada vacía. • Encontrar el fin del archivo. • Determinar que el archivo está lleno. 50 Estructuras de Archivos Archivos de tipo Árbol • Técnicas de Manejo de Colisiones: 1. Direccionamiento Abierto (cont.): Ventajas: • Menos espacio con respecto a tener un área de overflow aparte. • Dependiendo de la implementación, puede haber un menor tiempo requerido para acceder al área de overflow, pues como está incorporada a la misma área de datos, hay menos cambios de cilindro. • Uso más óptimo del área de datos, pues se minimizan las áreas muertas (zonas sin registros). Desventaja: • Búsqueda lineal de los registros en colisión. 51 Estructuras de Archivos Archivos de tipo Árbol • Técnicas de Manejo de Colisiones: 2. Encadenamiento: varias localizaciones sólo de overflow son mantenidas haciendo que un bucket de datos pueda direccionar un bucket de overflow. • Existen dos tipos de encadenamiento: • Unificado: cuando el bucket de overflow es compartido por varios buckets de datos. • Enlazado: cuando el bucket de overflow es exclusivo de un bucket de datos. 52 Estructuras de Archivos Archivos de tipo Árbol • Técnicas de Manejo de Colisiones: 2. Encadenamiento (cont.): Ventaja: • Se conoce con certeza los buckets donde hay que buscar un registro. Desventajas: • Pueden generarse una secuencia de buckets en overflow, si éste es constante. • Pueden producirse “zonas muertas” en el mismo área de overflow. 53 Estructuras de Archivos Archivos de tipo Árbol • Técnicas de Manejo de Colisiones: 3. Hashing Múltiple: Consiste en aplicar distintas funciones hashing a los registros que están en colisión hasta encontrar una posición disponible donde almacenarlo. • La secuencia en que se aplican las diferentes funciones hashing debe ser respetada en la búsqueda posterior de los registros. 54 Estructuras de Archivos Archivos Directos • Técnicas de Hashing con Expansión Dinámica. • Las técnicas anteriores consideran un espacio de direccionamiento de tamaño fijo...pero lo normal es que los archivos vayan cambiando su tamaño constantemente, lo que debe verse reflejado en la técnica de hashing que se utiliza. • Existen tres formas básicas para poder implementar una expansión dinámica del tamaño del archivo, mediante técnicas hashing: • Dinámico • Extendible • Lineal 55 Estructuras de Archivos Archivos Directos • Hashing Dinámico. • Considera, además del archivo de datos, una estructura de acceso de tipo jerárquica. • Similar a una técnica de indexación. • El número de buckets no es fijo, sino que aumenta o disminuye según sea requerido. 56 Estructuras de Archivos Archivos Directos • Ejemplo de Archivo Dinámico. 57 Estructuras de Archivos Archivos Directos • Hashing Dinámico (cont.). • El archivo puede empezar con un único bucket; una vez lleno, si un nuevo registro es insertado, el bucket “entra en overflow” y se divide en dos buckets. • Los registros son divididos entre estos dos buckets, según el valor del bit más izquierdo de sus valores hashing. • En este punto se crea una estructura de árbol binario, llamada directorio o índice. Esta situación se repite cuanto sea necesario. 58 Estructuras de Archivos Archivos Directos • Hashing Extendible. • Considera, además del archivo de datos, una estructura de acceso de tipo arreglo, que actúa de modo similar a un índice. • El directorio que se usa es un arreglo con 2d direcciones de buckets (d es la “profundidad global del directorio). • Cada entrada del directorio direcciona a un bucket, que contiene una profundidad local d’ (# de bits sobre el cual se basan los registros contenidos en el bucket). 59 Estructuras de Archivos Archivos Directos • Ejemplo de Archivo Extendible. 60 Estructuras de Archivos Archivos Directos • Hashing Extendible (cont.). • Los primeros d bits más significativos de un valor hashing son usados como índice al directorio; la dirección en cada entrada determina el bucket de almacenamiento. • No tiene que existir un bucket por cada entrada del directorio. 61 Estructuras de Archivos Archivos Directos • Hashing Lineal. • No considera una estructura tipo índice como las anteriores. • Su uso se basa en la existencia, inicialmente de M buckets, numerados de 0 a M-1, los cuales van recibiendo registros de acuerdo a una función hashing h0. • En el momento en que alguno de los buckets se llena, se crea un bucket M en el cual se reparten los datos del bucket 0, aplicando la función hashing h1. • Este esquema se sigue repitiendo a medida que el archivo crece de tamaño. 62 Estructuras de Archivos Archivos de tipo Árbol • Árboles: son archivos en las cuales los registros se organizan en bloques relacionados de forma jerárquica entre sí, de acuerdo a un cierto orden entre los valores que contiene cada registro • En cada uno de los casos se favorece las búsquedas binarias, respecto de la clave sobre la cual se construyó el archivo. • Existen cuatro tipos de árboles posibles de usar en este ámbito... 63 Estructuras de Archivos Archivos de tipo Árbol • Árboles 1. Binarios: tienen un factor de ramificación de 2, es decir, cada nodo tiene a lo más dos descendientes inmediatos (hijos). • La altura mínima de un árbol con N registros es: log2 N + 1 • Desventaja: los tiempos de recuperación no son buenos y requieren un gran esfuerzo para mantener un acceso eficiente a los datos 64 Estructuras de Archivos Archivos de tipo Árbol • Árboles 2. Balanceados de Búsqueda Binaria (AVL): Árboles binarios con restricciones de crecimiento. Inventados como una solución a los problemas de balanceo encontrados en los árboles anteriores. • Se ha establecido que la altura de un AVL con N registros está entre: log2(N+1) y 1.44.4 log2(N+2) - 0.328 • Persisten los problemas de búsqueda debido a que aún se tienen muchos niveles. 65 Estructuras de Archivos Archivos de tipo Árbol • Árboles 3. Árboles B: no existen problemas con estos árboles en cuanto a la recuperación y mantención como los árboles binarios, pues son árboles multiway con operaciones de balanceo propias. • Es el tipo de índice que tradicionalmente se ha usado en ambientes de bases de datos relacionales. 66 Estructuras de Archivos Archivos de tipo Árbol B • Árbol B: se define un árbol B de orden M a aquel árbol que cumple con las siguientes condiciones: • Ningún nodo tiene más de M hijos. • Cada nodo, excepto la raíz, tiene al menos M/2 hijos y a lo más M hijos. • La raíz, a no ser que el árbol sólo tenga un único nodo, tiene al menos 2 hijos. • Todos los nodos terminales se encuentran en el mismo nivel, es decir están a la misma distancia respecto de la raíz. • Un nodo no terminal con K hijos contiene k-1 registros. Un nodo terminal contiene al menos M/2 - 1 registros y a lo más M-1 registros. 67 Estructuras de Archivos Archivos de tipo Árbol B • Árbol B: un nodo de orden M tiene la siguiente estructura: Puntero1 Registro1 Puntero2 Registro2 … Punterom-1 Registrom-1 Punterom donde punteroi apunta a un bloque que contiene registros cuyos valores son mayores que la clave de registroi-1 y menores que la clave de registroi. Así es posible realizar una búsqueda binaria sobre la estructura de datos y alcanzar los datos. 68 Estructuras de Archivos Archivos de tipo Árbol B • Ejemplo de Árbol B, de orden 4. m c a b d e f i g h q j k l n o p t r s u v w 69 Estructuras de Archivos Archivos de tipo Árbol B • Operaciones: sobre un árbol B. • Búsqueda: se comienza examinando la raíz para buscar nodo con el registro requerido. • Si no es encontrado, comparaciones con claves identificarán el puntero a seguir hacia el nivel inferior. • Si es nulo => nivel inferior => registro buscado no está en el archivo. • Si no es nulo, accesar el nodo apuntado, el cual pasa a ser la raíz. 70 Estructuras de Archivos Archivos de tipo Árbol B • Operaciones: sobre un árbol B. • Inserción: los nuevos registros son insertados en un nodo terminal (hoja). • Para determinar el punto de inserción, se realiza la misma operación de búsqueda anterior. • Si la posición determinada se encuentra dentro de un nodo totalmente ocupado, ocurre un overflow, lo cual se resuelve haciendo una división del nodo en tres partes, llevando el registro del medio hacia el nivel superior para insertarlo en el nodo padre, dejando a este último con un hijo más. 71 Estructuras de Archivos Archivos de tipo Árbol B • Operaciones: sobre un árbol B. • Eliminación: también se debe realizar desde el nivel de más abajo hacia arriba. • Problema: Borrar un registro de un nodo que tiene la cantidad mínima de registros permitidos (underflow). Soluciones: • Redistribución - el nodo adyacente al de underflow tiene una cantidad de registros mayor al mínimo: mover registros entre el nodo adyacente y el padre de tal forma de no alterar la estructura del árbol. • Concatenación - no es posible la redistribución: mezcla de nodos, proceso inverso de la división de un nodo. Cambia la estructura del árbol, incluso puede removerse la raíz y reducir en un nivel el árbol. 72 Estructuras de Archivos Archivos de tipo Árbol B • Variaciones del Árbol B: • Árbol B Virtual: • Para alcanzar un nodo, se debe pasar siempre por la raíz (con el consiguiente acceso al disco) • Hay implementaciones en las que el sistema almacena el nodo raíz en la RAM permanentemente. • Si hay memoria suficiente, se puede almacenar los nodos del segundo nivel y más • Ventajas: se reducen los accesos al disco y por ende, los tiempos de respuesta. 73 Estructuras de Archivos Archivos de tipo Árbol B • Variaciones del Árbol B: • Árbol B*: • Un árbol B tiene la restricción de que tiene estar a lo menos un 50% lleno, lo que puede ocasionar que la mayoría de los nodos estén un 50% llenos y un 50% vacíos, desperdiciando en este caso casi la mitad del espacio de los bloques físicos ocupados. • Como una forma de reducir esto, se plantea el árbol B*, el que impone la restricción de que al menos un 66.6% del nodo debe estar lleno. 74