Capitulo 6 – Estructuras Fisicas de datos y costo de consultas

  1. 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.
    El almacenamiento se ha ocupado con:

    • 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 &
      iacute;ndice sobre la columna A de R

    Se pide determinar:

    1. ¿Cuántos accesos demanda
      la inserción de una tupla en la tabla R en el peor caso?
    2. ¿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?

    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:

    • 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.

    ¿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.

  2. 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:

    1. Muestre, si existe, una estructura
      posible para el árbol que, cumpliendo con las dos condiciones citadas,
      tenga al menos una de sus hojas llenas
    2. Muestre, si existe, una estructura

      nposible 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).

Be the first to comment

Leave a Reply

Your email address will not be published.


*