Estructuras de Indexación en Bases de Datos: Árboles B, B+ y Cálculo de Rendimiento

Estructuras de Indexación en Bases de Datos: Árboles B y B+

1. Comparativa de Indexación (lx) en Árbol B y Árbol B+

A continuación se detallan las características de la indexación (lx) en estructuras de árbol B y B+:

• Los nodos hoja (nH) están al mismo nivel: Sí / Sí (SS).
• Los nodos tienen la misma estructura: Sí / No (SN).
• La ocupación de los nodos es uniforme: Sí / Sí (SS).
• La búsqueda de un valor es uniforme: No / Sí (NS).
• Recorrer el fichero (F) requiere pasar por todos los nodos índice: Sí / No (SN).
• El fichero (F) debe estar ordenado para tener índice: No / No (NN).

2. Rendimiento y Tiempos de Acceso en Ficheros Desordenados

Considerando un fichero desordenado que ocupa B bloques y tiene un tiempo de acceso D:

1. Recorrido de todos los registros de F: B x D (BXD).
2. Buscar el primer registro de F que cumple una condición:
   • Mejor caso: D
   • Peor caso: B x D (BXD)
3. Buscar todos los registros de F que cumplen una condición: B x D (BXD).
4. Insertar un nuevo registro en F: 2 x D (2XD).
5. Borrar el primer registro que cumple una condición:
   • Mejor caso: 2 x D (2XD)
   • Peor caso: (B x D) + D

3. Conceptos de Selectividad en Consultas

¿Qué es la selectividad (condición de selección)?

Es el cociente entre el número de filas que cumplen la condición de selección y el número total de filas de la tabla.

¿Qué es la selectividad de la concatenación (join) de 2 tablas?

Es el cociente entre el número de filas resultantes de la concatenación y el número total de pares de filas del producto cartesiano de ambas tablas.

4. Optimización de Consultas de Agregación

¿Qué método sería el más eficiente para obtener MIN(E) de S?

Como el índice sobre el campo E en la tabla S es de tipo B+, usaríamos el propio índice para buscar el valor más pequeño. Este se encuentra en el nodo-hoja más a la izquierda (dado que el índice es ascendente), permitiendo obtener el resultado de forma directa sin necesidad de acceder al fichero de datos.

5. Casos Prácticos de Cálculo de Índices

Dado un fichero de 400.000 registros de 256 Bytes (B) cada uno, con un índice ordenado multinivel sobre el campo A. El campo de indexación ocupa 20 Bytes (B), el tamaño del puntero es de 12 Bytes (B) y el tamaño del bloque es de 2 KB (2048 Bytes):

Caso 1: El campo A es clave (restricción de unicidad) y no ordena el fichero

• Tamaño de una entrada del índice: Ocupa 32 bytes (20 B + 12 B).
• Factor de bloqueo del índice (fb_índice): 2048 / 32 = 64 entradas por bloque.
• Altura del índice: log64(400.000) ≈ 4.
• Estructura del índice: Como el campo A es clave, no habrá dos registros con el mismo valor en A. Además, al no estar el fichero ordenado por ese campo, el índice del primer nivel será un índice secundario denso (con tantas entradas como registros tiene el fichero de datos). Es decir, el índice tendrá 400.000 entradas en el primer nivel.

Caso 2: El campo A es clave (restricción de unicidad) y ordena el fichero

• Bloques ocupados por el fichero: 400.000 / 8 = 50.000 bloques (calculado como 2048 B / 256 B = 8 registros por bloque).
• Estructura del índice: Como el campo A es clave, no habrá dos registros con el mismo valor en A. Al estar el fichero ordenado por el campo A, el índice del primer nivel será un índice primario disperso (con tantas entradas como bloques tenga el fichero de datos). Es decir, el índice tendrá 50.000 entradas en el primer nivel.
• Altura del índice: log64(50.000) ≈ 3.