Ordenamiento De Archivos En Base De Datos

Organización de Archivos en Bases de Datos
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ño 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 específico.Clústeres
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 segeneralizan 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 secoloca 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 másregistros, 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 otroregistro 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 mismonivel. 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 delos 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 seencuentran 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...