¿Qué es la organización física? ¿Qué es el diseño de archivos? ¿Qué es un archivo físico? ¿Cuáles son los sistemas de archivo físico?

Las decisiones que se toman en el diseño físico de la base de datos impactan en el almacenamiento en disco y en el sistema operativo. Tienen que ver con el almacenamiento y configuración de los parámetros del SGBD:

• Arquitectura de hardware para la base de datos: procesadores, discos RAID, etc.
• Estructuras de almacenamiento y acceso que permite el SGBD: tipos de indexación, agrupamiento, tamaños de bloques, buffers, etc.
• Parámetros de configuración del SGBD: tamaño de memoria intermedia, intervalos de tiempo en proceso, uso de multiprocesadores, etc.

El medio de almacenamiento utilizado para los datos con los que se opera es la memoria principal. Se define por su uso: es la memoria con la que trabaja casi directamente el procesador. Es volátil: su contenido suele perderse en caso de fallo del suministro eléctrico o de caída del sistema. La más común es la RAM (memoria de acceso aleatorio), la cual se caracteriza por poder acceder a cualquier posición de memoria a la misma velocidad sin tener que recorrer dichas posiciones secuencialmente. Como el procesador es muy rápido, la memoria con la que debe trabajar tiene que ser lo más rápida posible para no generar cuellos de botella. El procesador pide datos, lee y escribe todo el tiempo, necesita estar el menor tiempo posible esperando a que ese dato llegue. Por eso es más importante la velocidad que la capacidad de la memoria principal. La RAM le permite al procesador tener acceso más rápido a una mayor cantidad de datos. Si se llena, el procesador envía los datos que no usa al almacenamiento auxiliar y deja en la RAM aquellos que va a utilizar en ese momento.

La caché es una pequeña memoria ubicada entre la RAM y el procesador con la que éste trabaja directamente. Le indica qué archivos deben ser traídos desde el almacenamiento auxiliar hacia la memoria principal para trabajar con ellos.

Como el procesador es volátil y trabaja con las memorias RAM y caché, no es un costo que ambas memorias sean volátiles también y que sus datos se pierdan cuando no reciba corriente eléctrica (después de todo, el procesador no podrá usarlos. El problema entonces pasa por definir dónde almacenar los datos para que no se borran permanentemente. El almacenamiento secundario cumple esa función: almacena los archivos hasta que sean requeridos por el procesador y sean enviados a la memoria principal. Es un almacenamiento no volátil: para mantener los datos guardados no depende de estar conectado a una fuente de alimentación.

El disco rígido es esencial para los sistemas de datos, ya que es allí donde se almacenarán los datos ingresados a la base. De hecho, generalmente se guarda en ellos toda la base de datos. Para acceder a ellos es necesario trasladarlos desde el disco hacia la memoria principal. Se compone de una serie de discos, con sus cabezales, uno arriba del otro, que giran sobre un eje. El cabezal se mueve hacia delante y hacia atrás (más lejos y más cerca del centro) para recorrer el disco y de leer la información en ambas caras del mismo. Se ubica en la pista correcta y espera a que la rotación del disco lo lleve a la posición de memoria que necesita. Cuanto más rápido giren los discos, más velozmente se accede a esa posición. Una vez ubicado allí puede leer o escribir la información de esa ubicación. Los tiempos de acceso dependen de la localización de los datos y la latencia, es decir, qué tan distanciado esté el dato del eje rotacional del disco y de la posición del cabezal.

Una página o bloque de memoria es la unidad de lectura y escritura. Es el conjunto de bytes transferidos del disco a la RAM en un solo acceso (generalmente 4 kB). Como los archivos suelen ser mayores a esta unidad, se dividen en varios bloques. Es más fácil de leer si se guardan en forma secuencial ya que serán leídos también de forma secuencial, dando lugar a las extensiones.

Una extensión es un conjunto de páginas contiguas físicamente que el Adm. de disco asigna y libera. Se persigue que páginas contiguas lógicamente lo estén también físicamente, reduciendo al mínimo el acceso.

El SGBD posee una memoria intermedia (buffer de la BD:RAM almacenamiento primario del servidor) entre éste y el almacenamiento secundario. Es un espacio reservado en la memoria principal para el sistema de gestión de bases de datos. Éste recibe peticiones de escritura, lectura, actualización y borrado de registros. Cada uno de ellos se van a convertir en archivos y, por ende, en bloques que estarán en esa memoria intermedia (sean actuales o bloques ya trabajados).

Cuando se llena el buffer se deben borrar del mismo algunos bloques para que su lugar sea ocupado por otro que se esté requiriendo para una determinada operación en ese momento. En función de la prioridad que se haya establecido para determinar cuáles bloques borrar, si éstos no fueron modificados, pueden eliminarse de la memoria intermedia sin problemas porque, en caso de necesitarlo, se lo puede traer otra vez desde el almacenamiento secundario.

En cambio, si los bloques a eliminar de memoria principal sufrieron modificaciones, primero se escriben las mismas en el almacenamiento secundario para poder recuperar el valor actualizado, de ser necesario. Una vez hecho eso, se trae a memoria intermedia el bloque que estaba esperando. Esto también ocurre cuando el bloque a eliminar no existe en memoria secundaria.

Considerando que el SGBD hace uso de la memoria intermedia para mejorar su desempeño de acceso a memoria secundaria, es factible que, al actualizar el valor de un atributo de un registro de una tabla de una base de datos, esa modificación esté en memoria principal y no en memoria secundaria (aunque sea temporalmente).

Un arreglo redundante de discos independientes (RAID) es un arreglo de dos o más discos rígidos que se presentan ante el sistema operativo como uno solo. Cada disco trabaja de manera independiente y es el controlador de RAID el que administra su funcionamiento.

Un RAID persigue dos objetivos muy distintos, que a veces se logran complementar según el tipo de RAID:

• Performance: obtener mayor velocidad en las operaciones de lectura/escritura y mejor rendimiento.
• Tolerancia a fallos: si se rompe un disco no se pierden los datos.

Al tratarse de discos que trabajan en paralelo, es recomendable que todos posean la misma velocidad de lectura y escritura e igual capacidad de almacenamiento. En caso de que sean diferentes, todo el arreglo funcionará a la velocidad del disco más lento y refleja la capacidad de aquel disco que posea menor cantidad de almacenamiento.

• RAID 0:

Divide cada bloque en n partes (según la cantidad de discos), distribuyendo cada una de ellas en un disco. Cuando se necesite leerlos, se recupera cada parte guardada en los discos. Si se rompe un disco, se pierden todos los datos que estaban almacenados en el arreglo, ya que los bloques no pueden ser reconstruidos (cada parte es incompleta).

Cada bloque se escribe en los n discos de forma paralela. Al estar multiplicados los bloques, si se rompe un disco no se pierde la información almacenada en el arreglo y el sistema sigue funcionando.

se trata de 2 o más arreglos RAID 1 en donde cada bloque se divide en n2 partes y cada una de ellas se escribe en 2 discos, como en el RAID 0. La situación si se rompe un disco dependerá de cuál disco se rompa. Se pierden todos los datos si se rompe una cantidad de discos tal que resulte imposible reconstruir los bloques.

divide el bloque de datos en p partes, distribuyendo cada una en n-1 discos, almacenando en el disco información de paridad. La misma consiste en una función que, aplicada sobre una de las p partes del bloque, permite reconstruir la parte que falta. Este tipo de paridad se denomina paridad por bloque distribuida ya que puede guardar la paridad en diferentes discos del arreglo, a veces en uno y otras veces en otro distinto, en bloques reservados (y no en un disco reservado). Un bloque de paridad no puede guardar la paridad de los bloques del mismo disco, ya que un fallo del disco supondría la pérdida de los datos y de la paridad y, por tanto, no sería recuperable. Existen niveles inferiores de RAID que dividen por bit (paridad por bit en RAID 3) o por bloque (paridad por bloque en RAID 4).

Nivel de RAID

Cantidad de discos

Velocidad de E/S

Objetivo

Cantidad mínima de discos

Tolerancia de ruptura

Capacidad de almacenamiento

Sin RAID

1

m segundos

Sólo guardar datos

1

0 discos

x GB

RAID 0

n

mn segundos

Performance

2

0 discos

n*x GB

RAID 1

n

m segundos para escritura; sin embargo, se puede leer la mitad de un bloque de cada disco, tardando mn segundos en lectura

Tolerancia a fallos y mayor performance en lectura.

2

n-1 discos

x GB

RAID 10

n

mn segundos

Tolerancia a fallos y performance de lectura y escritura

4

Variable

n2*x GB

RAID 5

n

mn segundos + cálculo de paridad y distribución

Tolerancia a fallos; mínima mejora de performance

3

1 disco

(n-1)*x GB

• El nivel 2 de RAID,

también conocido como organización de códigos de corrección de errores tipo memoria (memory-style-error-correcting-code organization, ECC), emplea bits de paridad. Hace tiempo que los sistemas de memoria utilizan los bits de paridad para la detección y corrección de errores. Cada byte del sistema de memoria puede tener asociado un bit de paridad que registra si el número de bits del byte que valen uno es par (paridad = 0) o impar (paridad = 1).

organización de paridad con bits entrelazados, mejora respecto al nivel 2 al aprovechar que los controladores de disco, a diferencia de los sistemas de memoria, pueden detectar si los sectores se han leído correctamente, por lo que se puede utilizar un solo bit de paridad para la corrección y para la detección de los errores. La idea es la siguiente: si uno de los sectores se deteriora, se sabe exactamente el sector que es y, para cada uno de sus bits, se puede determinar si es un uno o un cero calculando la paridad de los bits correspondientes de los sectores de los demás discos. Si la paridad de los bits restantes es igual que la paridad guardada, el bit perdido es un cero; en caso contrario, es un uno.

organización de paridad con bloques entrelazados, emplea la distribución del nivel de bloques, como RAID 0, y, además, guarda un bloque de paridad en un disco independiente para los bloques correspondientes de los otros N discos. Este esquema se muestra gráficamente en la Figura 11.3e. Si falla uno de los discos, se puede utilizar el bloque de paridad con los bloques correspondientes de los demás discos para restaurar los bloques del disco averiado.

En un bloque puede almacenarse filas o columnas de una tabla de la base de datos. Esto permite distinguir:

• Bases de datos orientadas a filas:

Los valores de las filas se almacenan físicamente en forma contigua dentro del archivo. Este tipo es más eficiente para, por ej., leer todos los datos de un registro ya que para ello sólo debería leer 1 bloque.

Los valores de las columnas se almacenan físicamente en forma contigua dentro del archivo, en donde uno de los bloques contendrá los atributos de la tabla. Este tipo es más eficiente para, por ej., obtener promedios o cantidades de un atributo de varios registros, ya que para eso también debería leer 1 bloque. Por este motivo son más analíticas. Permite comprimir los datos que se almacenan porque no se guardan valores repetidos: dos registros para el mismo valor del mismo atributo apuntan a la misma PK. Además, no guarda los valores vacíos o nulos. Cuanto más repetidos estén los datos, mayor será la posibilidad de compresión.

Las bases de datos relacionales poseen mayoritariamente almacenamiento

orientado a filas. Para separar los datos, se utilizan caracteres separadores que:

• Separan el nombre del campo del valor del campo.
• Separan los campos.
• Indican el fin del registro.

Cada bloque posee un factor de bloqueo, que es la cantidad de registros que entran en un bloque para una tabla determinada. Los espacios de longitud fija no utilizados se almacenan en blanco.

Beneficios:

• Mayor rapidez en las lecturas. Se leen solamente las columnas necesarias para el procesamiento de una consulta determinada.
• Optimización de los accesos al disco.
• Ocupan menos espacio, dado que los datos se guardan comprimidos.
• Ideales para calcular datos agregados.
• Recomendada para entornos OLAP, donde existen altos índices de lectura pero poca escritura

1. Registro de longitud fija con 6 campos y 71 bytes.
2. un registro con dos campos de longitud variable y tres de longitud fija.
3. un registro de longitud variable con tres campos variables.

Existen diversas maneras de ordenar en el disco los distintos bloques que componen un archivo:

• Asignación contigua: los bloques se almacenan en extensiones, uno al lado del otro. Esto acelera la lectura del archivo. Tiene el problema de que, si el bloque consecutivo está ocupado por otro archivo, el sistema se ve obligado a usar un bloque de desbordamiento no consecutivo para almacenar la parte que falta (lanzándose a través de un puntero) y esperar a poder hacer una reorganización que permita ponerlos en orden otra vez.
• Asignación enlazada: se indica cuál es el primer bloque donde está almacenado el archivo y cada bloque tiene un puntero al siguiente. El problema que presenta es que, si sólo se debe leer un bloque que no es el primero, para llegar al deseado deben leerse primero los anteriores.
• Asignación con índice: utiliza un bloque que indica dónde están el resto de los bloques en donde se almacena el archivo. Así, para leer un bloque que no es el primero, sólo debe leerse éste para llegar inmediatamente al buscado.

Guardar los registros ordenados utilizando como criterio alguno de los atributos permite reducir la cantidad de bloques que se leen para acceder a los datos que se están buscando. Existen distintas alternativas de guardar los registros ordenados en un archivo para optimizar el funcionamiento:

• Dejar espacios en blanco por bloque: evita que la inserción de un registro implique traer a memoria principal 2 bloques en vez de uno para reorganizarlos.
• Área de derrame con punteros: se asigna el registro a otro bloque añadiendo un puntero en el bloque en el que debería estar almacenado. Esto permanecerá así hasta que se reorganicen los bloques.
• Bitácora de transacciones (offline): se guardan todos los registros sin orden para distribuirlos ordenados cuando la base de datos tenga menos peticiones de acceso.
• Secuenciales indexados e índices agrupados: se puede utilizar un índice agrupado para recorrer, buscar y ordenar los registros en el archivo.

Existen dos formas de organizar registros desordenados:

• Organización de montón: almacena los datos sin orden, lo cual facilita la inserción de registros.
• Organización directa: se aplica una función sobre los valores de ciertos atributos que indica en qué bloque se va a guardar ese registro. Es preciso elegir un atributo útil que permita tener una buena distribución de los bloques.

En esta organización se puede colocar cualquier registro en cualquier parte del archivo en que haya espacio suficiente. No hay ninguna ordenación de los registros. Generalmente sólo hay un archivo por cada relación.

Se crea un índice con id=0, que está desordenado. Tabla sin índice clúster (o agrupado)

Las páginas IAM son páginas que administran los extents que una tabla o índice utilizan. Las páginas IAM contienen la localidad de las 8 páginas iniciales y un bitmap de extents indicando que extents pertenecen al objeto. Una sola página IAM puede administrar hasta 512,000 páginas de datos. Las páginas IAM siempre están alojadas en extents mixtos, y pueden estar en cualquier archivo o filegroup. SQL Server trata de mantener a todas las páginas IAM agrupadas para mejorar el performance.

Índices

Un índice es un lugar donde se puede buscar por una clave de búsqueda, encontrar (si existe) lo buscado y tiene un puntero que indica en dónde se encuentra el dato buscado. La clave de búsqueda consiste en uno o varios atributos. Si los registros están ordenados, existe una clave de orden, que es el atributo según el cual se ordenan los registros.

El índice se guarda en otro bloque de memoria. La idea de utilizarlo es, cuando se busca un dato, poder traerlo a la memoria principal primero para recorrerlo y determinar en qué bloques buscar los datos que se necesiten, y también determinar si éstos existen antes de leer los bloques de datos.

Clasificación de índices

• Índices ordenados: están basados en una disposición ordenada de los valores.
• Según la coincidencia entre la clave de búsqueda y la clave de orden:
• Primario: cuando la clave de búsqueda del índice coincide con la clave de orden. Pueden ser:
• Disperso: cuando el índice no contiene un registro índice por cada valor de atributo que es clave de búsqueda. Si el valor de atributo buscado no está en el índice, se comienza a buscar a partir del valor anterior en el que debería estar aquél.
• Denso: si el índice contiene un registro índice por cada valor de atributo que es clave de búsqueda.
• Secundario: cuando la clave de búsqueda no coincide con la clave de orden. Si los registros no están ordenados, no existe clave de orden, por lo que el índice sólo podrá ser de este tipo. Los índices secundarios nunca pueden ser dispersos, siempre son densos.
• Según el nivel:
• Sin niveles.
• Multinivel: para encontrar un valor hace falta recorrer distintos niveles en los que esté dividido el índice.
• Según su agrupación:
• Agrupado: cada registro del índice contiene el registro buscado.
• No agrupado: cada registro del índice contiene un puntero que indica en qué bloque de memoria se encuentra el registro buscado.
• Índices asociativos: se aplica una función de asociación (hash) sobre la clave de búsqueda para identificar el bloque donde se encuentra el registro buscado.

Índices ordenados

Cada estructura de índice está asociada con una clave de búsqueda concreta. Los registros en el archivo indexado pueden estar a su vez almacenados siguiendo un orden, semejante a como los libros están ordenados en una biblioteca por algún atributo como el número decimal Dewey. Un archivo puede tener varios índices según diferentes claves de búsqueda. Si el archivo que

contiene los registros está ordenado secuencialmente, el índice cuya clave de búsqueda especifica el orden secuencial del archivo es el índice con agrupación (clustering index).

En la figura se muestra un archivo secuencial de los registros cuenta tomados del ejemplo bancario. Los registros están almacenados según el orden de la clave de búsqueda: nombre sucursal.

Estos archivos con índice primario según una clave de búsqueda se llaman archivos secuenciales indexados. Representan uno de los esquemas de índices más antiguos usados por los sistemas de bases de datos. Se emplean en aquellas aplicaciones que demandan un procesamiento secuencial del archivo completo así como un acceso directo a sus registros.

Índices densos y dispersos

Un registro índice o entrada del índice consiste en un valor de la clave de búsqueda y punteros a uno o más registros con ese valor de la clave de búsqueda. El puntero a un registro consiste en el identificador de un bloque de disco y un desplazamiento en el bloque de disco para identificar el registro dentro del bloque. Hay dos clases de índices ordenados que se pueden emplear:

• Índice denso. Aparece un registro índice por cada valor de la clave de búsqueda en el archivo. El registro índice contiene el valor de la clave y un puntero al primer registro con ese valor de la clave de búsqueda. El resto de registros con el mismo valor de la clave de búsqueda se almacenan consecutivamente después del primer registro, dado que, ya que el índice es primario, los registros se ordenan sobre la misma clave de búsqueda. Las implementaciones de índices densos pueden almacenar una lista de punteros a todos los registros con el mismo valor de la clave de búsqueda; esto no es esencial para los índices primarios.

• Índice disperso. Sólo se crea un registro índice para algunos de los valores. Al igual que en los índices densos, cada registro índice contiene un valor de la clave de búsqueda y un puntero al primer registro con ese valor de la clave. Para localizar un registro se busca la entrada del índice con el valor más grande que sea menor o igual que el valor que se está buscando. Se empieza por el registro apuntado por esa entrada del índice y se continúa con los punteros del archivo hasta encontrar el registro deseado.

Índices secundarios

Los índices secundarios deben ser densos, con una entrada en el índice por cada valor de la clave de búsqueda, y un puntero a cada registro del archivo. Un índice primario puede ser disperso, almacenando sólo algunos de los valores de la clave de búsqueda, ya que siempre es posible encontrar registros con valores de la clave de búsqueda intermedios mediante un acceso secuencial a parte del archivo. Si un índice secundario almacena sólo algunos de los valores de la clave de búsqueda, los registros con los valores de la clave de búsqueda intermedios pueden estar en cualquier lugar del archivo y, en general, no se pueden encontrar sin explorar el archivo completo. Un índice secundario sobre una clave candidata es como un índice denso primario, excepto en que los registros apuntados por los sucesivos valores del índice no están almacenados secuencialmente. Si la clave de búsqueda de un índice primario no es una clave candidata, es suficiente si el valor de cada entrada en el índice apunta al primer registro con ese valor en la clave de búsqueda, ya que los otros registros podrían ser alcanzados por una búsqueda secuencial del archivo. Por tanto, un índice secundario debe contener punteros a todos los registros. Se puede usar un nivel adicional de indirección para implementar los índices secundarios sobre claves de búsqueda que no sean claves candidatas. Los punteros en estos índices secundarios no apuntan directamente al archivo. En vez de eso, cada puntero apunta a un cajón que contiene punteros al archivo. Se muestra la estructura del archivo cuenta, con un índice secundario que emplea un nivel de indirección adicional, y teniendo como clave de búsqueda el saldo

Índices multinivel

Incluso si se usan índices dispersos, el propio índice podría ser demasiado grande para un procesamiento eficiente. En la práctica no es excesivo tener un archivo con 100.000 registros, con 10 registros almacenados en cada bloque. Si tenemos un registro índice por cada bloque, el índice tendrá 10.000 registros. Como los registros índices son más pequeños que los registros de datos, podemos suponer que caben 100 registros índices en un bloque. Por tanto, el índice ocuparía 100 bloques. Estos índices de mayor tamaño se almacenan como archivos secuenciales en disco. Si un índice es lo bastante pequeño como para guardarlo en la memoria principal, el tiempo de búsqueda para encontrar una entrada será breve. Sin embargo, si el índice es tan grande que se debe guardar en disco, buscar una entrada implica leer varios bloques de disco.

Para resolver este problema el índice se trata como si fuese un archivo secuencial y se construye un índice disperso sobre el índice con agrupación, como se muestra.

Índice multinivel: Árbol B+

• Los índices de árbol B + son una alternativa a los archivos secuenciales indexados.
• Inconvenientes de los archivos secuenciales indexados: el rendimiento baja cuando el archivo crece, dado que se crean muchos bloques de desbordamiento. Es necesario reorganizar periódicamente todo el archivo.
• Ventajas de los archivos de índice de árbol B +: se reorganiza automáticamente por sí mismo con pequeños cambios locales, a pesar de las inserciones y los borrados. No es necesario reorganizar todo el archivo para mantener el rendimiento.
• Inconvenientes de los árboles B +: inserciones extras, sobrecarga de borrados y costes de espacio.
• Las ventajas de los árboles B + superan a los inconvenientes, por lo que se emplean ampliamente.

Un árbol B+ es un árbol con raíz que satisface las siguientes propiedades:

• Todos los caminos, desde la raíz a las hojas, tienen la misma longitud
• Cada nodo que no es ni raíz ni hoja, tiene entre [n/2] y n hijos.
• Un nodo hoja tiene entre [(n–1)/2] y n–1 valores
• Casos especiales:
• Si la raíz no es una hoja, tiene al menos 2 hijos.
• Si la raíz es una hoja (es decir, no hay otros nodos en el árbol), puede tener entre 0 y (n–1) valores.

Estructura de nodos del árbol B+

Nodo típico

•  Ki son los valores de la clave de búsqueda
• Pi son los punteros a los hijos (para nodos no hoja) o a los registros o cajones de registros (para nodos hoja).
• En un nodo las claves de búsqueda están ordenadas

K1 < K2 < K3 < . . . < Kn–1

Propiedades de un nodo hoja:

Para i = 1, 2, . . ., n–1, el puntero P apunta a un registro del archivo con valor de clave de búsqueda Ki, o un cajón de punteros a los registros del archivo, cada registro con valor de clave de búsqueda Ki. Sólo es necesaria una estructura de cajones si la clave de búsqueda no es una clave primaria.

• Si Li, Lj son nodos hoja e i < j, los valores de clave de búsqueda de Li son menores que los de Lj
• Pn apunta al siguiente nodo hoja, ordenado por clave de búsqueda

Un índice Árbol B+ es un índice multinivel equilibrado invertido denso:

• Es equilibrado porque se puede estimar con precisión cuántos bloques hay que leer para recorrer el índice y llegar a un dato específico.
• Es invertido porque su forma es la de un árbol al revés.

Cada uno de los bloques es un nodo del índice. El mismo va a representar los valores de atributo ubicados en la base u hojas del árbol. Para llegar a cada valor siempre se recorre la misma cantidad de bloques, siendo dicho número la altura del árbol. Cada nodo que no sea hoja tiene entre n2 y ni hijos, donde no es fijo para cada árbol concreto.

Cada nodo posee dos claves (V1;…;Vn-1) y punteros (P). En el nivel de nodos hoja (la base del árbol), cada nodo puede guardar hasta n-1 valores. El último puntero Pn apunta al siguiente registro. Esto permite, en el caso de que se quiera recorrer todos los registros a partir de un cierto valor, situarse en el primero de ellos y desde ahí leerlos todos sin recorrer cada uno de los caminos posibles del árbol.

Los nodos no hoja (internos) forman un índice multinivel (disperso) sobre los nodos hoja. La estructura de los nodos internos es la misma que la de los nodos hoja, excepto que todos los punteros son punteros a nodos del árbol. Un nodo interno podría guardar hasta n punteros y debe guardar al menos n2 punteros. Cada clave del nodo (V1;…;Vn-1es un valor de clave de búsqueda y su función es indicar qué camino seguir para hallar ese valor: los valores menores a una clave del nodo apuntan en dirección izquierda y los mayores o iguales a la derecha. Un puntero adicional apunta a aquellos valores mayores o iguales a la primera clave del nodo y menores que la segunda.

Cada nodo tiene la misma cantidad de punteros, en función de cuántas claves de búsqueda entren en un bloque (nodo) del índice. El nodo raíz puede tener menos de n2 punteros; sin embargo, debe tener al menos 2 punteros, salvo que el árbol tenga un solo nodo.

Ejemplo búsqueda:

La estructura del árbol suele modificarse ante operaciones de actualización:

En un nodo hoja pueden encontrarse:

• Un puntero que indique en qué bloque de memoria está el registro con ese valor de clave de búsqueda (índice no agrupado).
• El registro o dato buscado (índice agrupado). Generalmente son más pequeños por no contener los datos.

Pueden combinarse índices agrupados y no agrupados, teniendo, por ej., un índice no agrupado basado en un atributo que lleve a otro índice agrupado en base a otro atributo, existiendo entre ellos el valor de clave de búsqueda que permite recorrer el siguiente índice (de ser necesario hacerlo, dependerá de la consulta que dé origen a la búsqueda).

• Inconvenientes de los archivos secuenciales indexados: el rendimiento baja cuando el archivo crece, dado que se crean muchos bloques de desbordamiento. Es necesario reorganizar periódicamente todo el archivo.
• Ventajas de los archivos de índice de árbol B +: se reorganiza automáticamente por sí mismo con pequeños cambios locales, a pesar de las inserciones y los borrados. No es necesario reorganizar todo el archivo para mantener el rendimiento.
• Inconvenientes de los árboles B +: inserciones extras, sobrecarga de borrados y costes de espacio.
• Las ventajas de los árboles B + superan a los inconvenientes, por lo que se emplean ampliamente.

Búsquedas con índices

Búsqueda de filas en un montón con un índice no agrupado

Búsqueda de filas en un índice agrupado

Búsqueda de filas en un índice agrupado con un índice no agrupado

Árbol B

• Elimina redundancia
• Los nodos internos tienen 2 punteros por cada clave. Uno apunta al cajón de la clave, y el otro apunta al siguiente nodo hijo.

Índices Agrupados y no agrupados

Los índices agrupados están ordenados igual que la tabla, son dispersos. Cada nodo hoja tiene los datos de la tabla

Los nodos hoja de los índices no agrupados tiene punteros a los datos

Índices bitmap

Los índices bitmap son un tipo de índices especializado diseñado para la consulta sencilla sobre varias claves, aunque cada índice bitmap se construya para una única clave.

Para que se utilicen los índices bitmap, los registros de la relación deben estar numerados secuencialmente comenzando, por ejemplo, por 0. Dado un número n debe ser fácil recuperar el registro con número n. Esto resulta especialmente fácil de conseguir si los registros son de tamaño fijo y están asignados a bloques consecutivos de un archivo. El número de registro se puede traducir fácilmente en un número de bloque y en un número que identifica el registro dentro de ese bloque.

Un índice bitmap sobre el atributo A de la relación r consiste en un mapa de bits para cada valor que pueda tomar A. Cada mapa de bits tiene tantos bits como el número de registros de la relación. El i-ésimo bit del mapa de bits para el valor vj se define como 1 si el registro con número i tiene el valor vj para el atributo A. El resto de los bits del mapa de bits se define como 0.

En su forma más simple, un índice de mapa de bits sobre un

atributo tiene una mapa de bits por cada valor del atributo

• El mapa de bits tiene tantos bits como registros
• En un mapa de bits para el valor v, el bit para un registro es 1 si el registro tiene el valor v para el atributo, de lo contrario es 0

Índices Hash (asociativos)

Los índices asociativos están basados en una distribución uniforme de los valores a través de una serie de cajones (buckets). El valor asignado a cada cajón está determinado por una función, llamada función de asociación (hash function), la cual se aplica sobre la clave de búsqueda.

Un cajón indica una unidad de almacenamiento que puede guardar uno o más registros. Un cajón es normalmente un bloque de disco, aunque también se podría elegir de tamaño mayor o menor que un bloque de disco.

Existen dos tipos de asociaciones posibles:

• Asociación estática: el conjunto de direcciones posibles de los cajones es fijo. Se crea un cajón para cada valor de la función de asociación. Así, para realizar una búsqueda con el valor Ki de la clave de búsqueda, basta con calcular fKi y buscar luego el cajón con esa dirección. Esto presenta problemas cuando las bases de datos aumentan de tamaño.
• Asociación dinámica: modifica dinámicamente la función de asociación para adaptarse al aumento o disminución de tamaño de la base de datos, dividiendo y fusionando los cajones en cada caso. No se crea un cajón para cada valor de la función de asociación; en vez de eso, se crean cajones bajo demanda, a medida que se insertan registros en el archivo. Así, para localizar el cajón que contiene el valor de la clave de búsqueda Ki, el sistema toma los primeros i bits más significativos de fKi, busca la entrada de la tabla correspondiente a esa cadena de bits, y sigue el puntero del cajón de esa entrada de la tabla.

Asociación estática

• Un cajón es una unidad de almacenamiento que contiene uno o más registros (generalmente un cajón es un bloque de disco).
• En una organización de archivos asociativa se obtiene el cajón de un registro directamente desde su valor de clave de búsqueda, empleando una función de asociación.
• La función de asociación h es una función desde el conjunto de todos los valores de claves de búsqueda QUE, hasta el conjunto de todas las direcciones de cajones B.
• La función de asociación se emplea para localizar registros para accesos, inserciones y borrados.
• Los registros con diferentes valores de claves de búsqueda pueden asociarse al mismo cajón; de este modo, para localizar un registro, se ha de recorrer secuencialmente el cajón entero.

La organización de archivos asociativa del archivo cuenta, utilizando nombre sucursal como clave

Asociación dinámica

Como se ha visto, la necesidad de fijar el conjunto C de direcciones de los cajones presenta un problema

serio con la técnica de asociación estática vista en el apartado anterior. La mayor parte de las bases de

datos aumenta de tamaño con el tiempo. Si se va a utilizar la asociación estática para esas bases de datos,

hay tres opciones:

1. Elegir una función de asociación de acuerdo con el tamaño actual del archivo. Esta opción provocará

una degradación del rendimiento a medida que la base de datos aumenta de tamaño.

2. Elegir una función de asociación de acuerdo con el tamaño previsto del archivo en un momento

determinado del futuro. Aunque se evite la degradación del rendimiento, puede que inicialmente

se pierde una cantidad de espacio significativa.

3. Organizar periódicamente la estructura asociativa en respuesta al crecimiento del archivo. Esta

reorganización supone elegir una nueva función de asociación, volver a calcular la función de

asociación de cada registro del archivo y generar nuevas asignaciones de cajones. Esta reorganización

es una operación masiva que consume mucho tiempo. Además, hay que prohibir el acceso

al archivo durante la reorganización.

La función de asociación utilizada calcula la suma de los dígitos del número de cuenta módulo siete.(cajones de 0 a 6)

Un problema en el hash estático es el desbordamiento del bloque. El hash dinámico ayuda a superar este problema. También es llamado Método de hash extensible.  En este método, los depósitos de datos aumentan y disminuyen según el número de registros. Permite realizar operaciones como inserción, eliminación, etc. sin afectar el rendimiento.

Creo una función Hash que devuelve 2(i) y voy tomando dígitos a medida que aumenta el número de cajones. Es el prefijo asociativo. El prefijo asociativo puede tomar tantos valores como número de bit (i *2)

Indice invertido

índice invertido, que relaciona cada palabra clave Ci con el conjunto Si de (los identificadores de) los documentos que contienen Ci. Para dar soporte a la clasificación por relevancia basada en la proximidad de las palabras clave estos índices pueden proporcionar no sólo los identificadores de los documentos, sino también una lista de las ubicaciones dentro del documento en las que aparecen las palabras clave. Estos índices hay que almacenarlos en disco, y cada lista Si puede abarcar varias páginas de disco. Para minimizar el número de operaciones de E/S para la recuperación de cada lista Si, el sistema intentará guardar cada lista Si en un conjunto de páginas consecutivas del disco, de modo que toda la lista se pueda recuperar con una sola búsqueda en el disco. Se pueden usar índices de árbol B+ para asignar cada palabra clave Ci a su lista invertida asociada

Índices sobre viarias claves

Una estrategia más eficiente para este caso es crear y utilizar un índice con una clave de búsqueda (nombre _ sucursal, saldo)—esto es, la clave de búsqueda consistente en el nombre de la sucursal concatenado con el saldo de la cuenta. Esa clave de búsqueda, que contiene más de un atributo, se denomina a veces clave de búsqueda compuesta. La estructura del índice es la misma que para cualquier otro índice, con la única diferencia de que la clave de búsqueda no es un simple atributo sino una lista de atributos

Índices de cobertura

Los índices de cobertura almacenan los valores de algunos atributos (distintos de los atributos de la clave de búsqueda) junto con los punteros a los registros. El almacenamiento de valores de atributo adicionales es útil en los índices secundarios, ya que permite responder algunas consultas utilizando únicamente el índice, sin ni siquiera buscar en los registros de datos