- Se dispone de un espacio de almacenamiento en disco donde cada bloque es de 512 bytes. En dicho espacio se almacenan tablas e índices. Los bloques destinados a tablas cuentan con un encabezado de 15 bytes, más una lista de punteros a las tuplas, con 2 bytes por puntero. Los bloques destinados a índices tienen un encabezado de 10 bytes y su estructura interna corresponde a nodos de un árbol B+. Los números de bloque insumen 4 bytes.
- Una tabla S de 695 tuplas de 64 bytes cada una, con la siguiente
composición: B(4 bytes) clave primaria, C(30 bytes), D(30 bytes). - Un índice sobre la columna B de S.
- Una tabla R de 165510 tuplas de 8 bytes cada una. La tabla tiene el siguiente esquema: A(4 bytes) clave primaria, B(4 bytes) clave foránea referenciando la tabla S
- Un índice sobre la columna A de R
- ¿Cuántos accesos demanda
la inserción de una tupla en la tabla R en el peor caso? - ¿Cuántos accesos
demandaría realizar la consulta
select C,D from R,S where R.B=S.B and R.A=25
si se toman los índices como camino de acceso a las tablas? - Los costos de acceso se calculan en bloques.
- Las juntas dan como resultado cantidades de tuplas,
que deben traducirse a
bloques con las cantidades de bytes que ocupan las tuplas en los bloques. - Sea un árbol B de 3 niveles. Las claves son números enteros y
la capacidad máxima de un nodo son 4 claves. El árbol se encuentra
en el siguiente estado:- La raíz tiene una única clave con valor 110.
- Los dos niveles siguientes tienen las claves 4, 25, 33, 37, 45, 55, 58,
66, 74, 90, 93, 106, 115, 120, 133, 137, 141, 155, 162, 189, 206
Se pide:
- Muestre, si existe, una estructura
posible para el árbol que, cumpliendo con las dos condiciones citadas,
tenga al menos una de sus hojas llenas - Muestre, si existe, una estructuranposible para el árbol que, cumpliendo con las dos condiciones citadas,
pierda un nivel al eliminar alguna de sus claves, señalándola
(considerar que el algoritmo intenta reorganizar si es posible; en caso contrario,
busca fusionar con el hermano izquierdo y sólo si esto no es posible
fusiona con el hermano derecho).
El almacenamiento se ha ocupado con:
Se pide determinar:
Solución. Lo primero de todo es determinar para qué sirve
toda la información que nos dan. Por un lado tenemos la cantidad de tuplas
de cada tabla y por otro la cantidad de bytes que ocupan, y la cantidad de bytes
que se usan para guardar los bloques de la tabla. Hay que tener en cuenta lo
siguiente:
¿Cuántos accesos demanda la inserción de una tupla en la
tabla R en el peor caso?
Piden insertar en la tabla que tiene un índice Arbol-B sobre A en R.
Hay que determinar el orden del árbol B, o sea, la cantidad de punteros
por nodo que tiene, para saber cuántos niveles tiene y por lo tanto
cuántos accesos nos tomaría insertar un registro ahí. Para
empezar tomemos la suposición de que un nodo del árbol ocupa un
bloque. Por cada bloque de 512 bytes quedan 502 para guardar datos (el resto
es encabezado). Teniendo en cuenta que en un registro del árbol B caben
un valor de clave de 4 bytes, y un valor de puntero ocupa 2 bytes, son 6 bytes
por registro, luego son 83 registros por bloque. La cantidad de niveles se
calcula con la fórmula logn/2(M), donde M es la
cantidad de registros del archivo. Para R, esto es 165510 y n es 83 así
que n/2 es 42. Con la fórmula obtenemos 3 niveles y pico, y lo ajustamos
a 4.
El peor caso. El peor caso de inserción, me parece a mí,
es que el árbol esté tan lleno en la parte donde necesitemos insertar,
que la partición de nodos que deberá ocurrir llegue hasta el nodo
raíz.
Vamos a asumir que en el archivo de datos toma 1 solo acceso insertar la nueva
tupla. En el índice, primero hay que buscar la hoja en donde hay que insertar,
y luego realizar la operación de inserción. La lectura toma tantos
accesos como los niveles del árbol, por lo tanto, serán 4 lecturas.
Las escrituras son: para crear la partición de la hoja, 2 escrituras: una
de la nueva hoja con el dato nuevo, y la nueva hoja creada. Propagamos hacia los
3
niveles superiores y concluimos que necesitamos 2 escrituras por cada nivel, o sea,
8 escrituras, y una escritura más para escribir el nuevo nodo raíz.
En total, 9 escrituras, mas 4 lecturas son 13 accesos.
¿Cuántos accesos demandará la consulta?
La consulta que piden realizar es una junta con selección. Resulta que
se piden las tuplas de R con A=25. Ocurre que A es clave primaria de R, luego va
a haber una sola tupla de esa tabla que cumpla con la condición. Además
hay un índice sobre A, luego se requieren 5 accesos (una por nivel del
árbol más 1) para llegar a esa tupla. Se pide juntar esa tupla de
R con S sobre el atributo B, y resulta que B es clave primaria de S
y también tiene índice. Como hay 83 bloques en cada bloque del
índice, quiere decir que S tiene 1 nivel y pico, digamos 2 niveles. Al
ser B clave primaria de S, hay una sola
tupla de S que va en el resultado, y
la puedo buscar con el índice a un costo de 3 accesos (como ya dijimos,
2 niveles +1).
Luego el total quedaría así: 5 accesos de T más 3
para S = 8 accesos.