Organización de Archivos en Bases de Datos

May 4, 2007 · Archivado en Uncategorized

Diseño Físico.

Como las decisiones de diseño físico dependen tan estrechamente del DBMS a utilizar, en este blog apenas podemos dar lineamientos de diseñoo físico que permitan lograr un buen rendimiento de las transacciones que operan sobre la base de datos. En el laboratorio se ejercitan estos conceptos con un manejador de base de datos especcífico.

Clusteres

Se agrupan los bloques del archivo en clusteres, también llamados segmentos o «extents» y se enlazan los clusters con apuntadores. Este es el caso más general de la ubicación enlazada.

Archivos Hash

Partiendo de cómo se implementa una tabla de hash en memoria principal (hash interno), se generaliza a un archivo de hash almacenado en disco (hash externo). Las de la tabla de hash se generalizan a bloques de disco llamados buckets, cada uno de los cuales puede ser un solo bloque o un grupo de bloques consecutivos. Se dispone de M buckets para almacenar el archivo, los cuales se llenan al 80% de su capacidad. La función de hash aplicada a un valor de la clave de hash da un resultado que se interpreta como el bucket donde se va a almacenar el registro. En el encabezado del archivo se coloca una lista donde se indica, para cada bucket, la dirección del bloque de disco donde se encuentra el bucket.

El problema de las colisiones en el hash externo también se generaliza. Muchos registros pueden resultar en el mismo valor de la función de hash sin problemas, mientras quepan en el bucket correspondiente a ese valor. Sin embargo, cuando ya el bucket se llena y no le caben mas registros, es necesario disponer de un área de overow. Esta área consiste de una serie de bloques de disco donde colocar los registros que no quepan en los buckets originalmente dispuestos para el archivo. El bucket que se llena tiene un apuntador a registro que apunta a un registro dentro de un bloque del área de overow donde se encuentra el registro que no cupo allí, si es necesario insertar otro registro en ese mismo bucket, primero se inserta en el área de overow y el registro insertado inmediatamente antes apunta a este nuevo registro, formando una cadena de registros en el área de overow que iban en el bucket en cuestión y no cupieron.

Arboles B

Los árboles B de orden p son un caso particular de árboles de búsqueda que siempre están balanceados, es decir, todas sus hojas están al mismo nivel. Esto se logra imponiendo restricciones adicionales sobre el árbol y haciendo que los algoritmos de inserción y eliminación las cumplan. Ahora en cada nodo se distingue entre los apuntadores a subárbol, pi y apuntadores a datos, pri. Cada valor Ki del campo de búsqueda tiene asociado un apuntador pri al registro o al bloque donde está el registro que tiene ese valor en ese campo.

Adicionalmente, hay información adicional que se coloca en el árbol para el uso de los algoritmos de manipulación, ejemplos de esta información son: q (número de registros que están actualmente en el nodo), apuntador al nodo madre.

Arboles B+

Son una variante de los árboles B según la cual los apuntadores a los registros de datos solo se almacenan en las hojas del árbol, lo cual diferencia la estructura de los nodos internos de la estructura de los nodos hoja. Los nodos internos tienen la misma forma de los nodos de un árbol de búsqueda en general. Los nodos hoja tienen una entrada por cada valor del campo de búsqueda junto con un apuntador al registro (o al bloque que contiene el registro) si el campo de búsqueda es clave. Para un campo que no es clave, el apuntador es a bloque y en ese bloque se encuentran los apuntadores a los registros de datos que contienen ese valor, con lo cual se crea un nivel de indirección adicional.

Los nodos hoja del árbol B+ se enlazan con apuntadores entre sí para facilitar el acceso secuencial ordenado a todos los registros de datos. Los nodos hoja constituyen el primer nivel o nivel base de un índice de múltiples niveles, y los nodos internos del árbol B+ constituyen los otros niveles del multinivel. Algunos valores del campo de búsqueda que se encuentran en las hojas se repiten en los nodos internos del árbol B+ para guiar la búsqueda.

Creacion de ndices. Como adelantamos en los lineamientos generales, los campos que

son candidatos a tener caminos de acceso dedicados son: atributos por los cuales se

hacen busquedas (por igualdad o por rango), atributos claves o atributos que forman

parte de una condicion de join entre relaciones. Al crear caminos de acceso, hay

que establecer un compromiso entre el ahorro en tiempo que va a signi car el tener

ese camino de acceso y el gasto adicional en que se va a incurrir para realizar las

operaciones de actualizacion de los datos, que tambien deben actualizar los caminos

de acceso. En general, los caminos de acceso son tambien llamados ndices.

ISAM (Método de acceso secuencial indexado)

1. Cuándo construir un índice para un atributo. En general, si un atributo es clave o si se utiliza para alguna búsqueda o condición de join, hay una justificación inicial para crear un índice por ese atributo. Una situación deseable para la creación de índices es cuando existen varias consultas que se pueden contestar simplemente recorriendo los índices, sin necesidad de acceder el registro de datos.

2. Cuándo crear un índice de varios atributos. Si existen varias consultas que necesitan acceder los datos por varios atributos simultaneamente, por ejemplo, consultas cuya condición de selección utilice la edad y la carrera de un estudiante, entonces se justi ca crear un sólo índice por esos dos atributos. En este caso es importante que se construya el índice con el orden correcto en los atributos.

3. Cuando crear un índice cluster. Como un archivo puede tener a lo sumo o un índice primario o uno cluster, esta decisión es delicada pues tiene implicaciones en el ordenamiento físico de los registros de datos. Los índices cluster favorecen las búsquedas por rango. Si hay muchas consultas con este tipo de búsqueda por un atributo, puede que valga la pena crear el índice cluster, siempre y cuando estas consultas requieran acceso al registro de datos. En cambio, si la consulta no necesita acceder el registro de datos, entonces no tiene sentido crear un índice cluster para ese campo.

4. Cuándo usar un índice basado en hash o un índice basado en un árbol. Los manejadores de base de datos ofrecen principalmente estructuras B+ para la construcción de índices, sin embargo algunos sistemas proveen la posibilidad de uno basado en hash. Los árboles B+ son buenos para búsquedas por igualdad o por rango, pero los basados en hash, solo son buenos para las búsquedas por igualdad, y esto es una característica que debe ser tomada en cuenta en esta decisión.