20 agosto 2012

Forense de SQLite IV - Páginas B-Tree y Overflow


Continuo con la serie de SQLite resumiendo lo visto hasta ahora. Pero para no repetirme demasiado, lo hago esquemáticamente.
  • Las bases de datos SQLite se componen de páginas de un mismo tamaño.
  • Este tamaño se especifica en la cabecera del archivo en la posición 16. 
  • Las páginas son de distintos tipos según los datos que contengan. 
  • Las freelist son un tipo de páginas que han quedado libres tras borrarse la información que contenían.
    • En estas páginas puede haber información eliminada. 
    • Se localizan mediante una página especial llamada freelist troncal, que enumera todas las páginas libres en arrays de 4 bytes.
  • Una freelist troncal puede estar  encadenada a otras páginas troncales mediante los 4 primeros bytes.
    • Si los 4 primeros bytes son 00 00 00 00, significa que no hay más páginas troncales.
    • El segundo campo de 4 bytes de una página troncal indica el número de elementos de array que hay en esa página troncal, por lo tanto, el número de punteros a hojas libres (freelist leaf).
    • El número de la primera página troncal está en la cabecera del archivo en la posición 32.
    • Una página freelist troncal también puede tener espacio libre si los arrays con posiciones no la completan.
Páginas B-Tree
Las páginas B-Tree es donde se almacena la información de la tabla. Existen dos tipos de páginas B-tree las interiores y las hojas, que a su vez pueden ser de tablas o índices.

Al igual que ocurría con las páginas libres, las páginas b-tree interiores contienen punteros a otras páginas b-tree con los registros de cada tabla, denominados celdas. A la primera página B-tree que no tiene hijos, se la denomina página root.

Existe una página root por cada tabla o índice que tenga la base de datos y todos los registros de esa tabla colgarán de ella. Es decir, por cada CREATE TABLE, se creará una página b-tree root de tabla y por cada CREATE INDEX, una página b-tree root de índice.

Figura 1. Esquema B-tree de SQLite

Puede que parezca algo confuso, pero según avanzamos en la entrada quedará todo mucho más claro.

Tanto las páginas interiores como las hojas de página tienen la misma estructura. Se inician con una cabecera de página que varía entre 8 ó 12 bytes según el tipo de b-tree, un array de punteros a celdas de 2 bytes cada elemento y finalmente las celdas con datos, su tamaño depende  del contenido que tengan. Cada celda es un registro de la tabla.

Una celda es creada o modificada cada vez que se ejecuta un INSERT o un UPDATE y eliminada si la base de datos recibe un DELETE.

La página número 1 es una página btree excepcional, ya que comienza en la posición 100 e incluye la cabecera de la base de datos.

Figura 2. Esquema página 1 - B-tree 

La cabecera de una página Btree tiene una composición sencilla donde se indican todas sus características.

Tabla 1. Cabecera B-tree
Vamos a mostrar esto en un ejemplo de una hoja B-tree de tabla, viendo cada uno de los campos y explicándolos con mayor detalle.

Imagen 1. Cabecera B-tree de hoja de tabla

  • 0D: Indica que la página es una b-tree de hoja de tabla (13)
  • 02 E8: Indica que hay bloques libres. Estos bloques forman cadenas y el primer eslabón comienza en la posición 744. Los bloques libres se producen cuando hay celdas borradas
  • 00 05: Especifica que existen 5 celdas en la página, es decir, que la tabla tiene 5 registros.
  • 01 AE: La primera celda se encuentra en la posición 430 (relativa a la posición de la página).
  • 00: No hay bytes fragmentados. Estos bytes representan tamaños inferiores a 2 bytes sin usar dentro de la página.
  • 01 AE .. 03 E0: cada grupo de 2 bytes, son las posiciones de las celdas en la página: 430, 587, 854, 882 y 992.
  • 03 E0: Esta marcado por que aparentemente es una celda eliminada, ya que se indicó que solo había 5 (coloreadas en azul) y en la sexta posición aún hay datos, aunque su valor se ha sobre escrito con el de la posición de la celda número 5.
Para maximizar espacio  las celdas comienzan ubicándose al final de la página y subiendo hasta que llegan al array de posiciones de celda. Por lo que los registros más antiguos estarán en posiciones más altas.

Del ejemplo se observa que se indica la posición 744 como el principio de los bloques libres. Desde aquí comienza una cadena, donde los dos primeros bytes indican la posición del siguiente bloque libre ó 00 00, si no hay más, y los dos siguientes, el tamaño del bloque libre. Con esta información, somos capaces de encontrar todo el espacio que la base de datos tiene asignada como libre.

Vamos a verlo en la práctica. Saltando desde la posición del comienzo de la página al 744.

Imagen 2. Saltando a posición 744 relativa
Como estaba en la posición 1024 (la segunda página), aterrizo en la posición: 1768.

Imagen 3. Cadena de bloque libre.
  • 00 00: Indica que no hay más bloques libres que continuar.
  • 00 6E: Equivale a 110 bytes que componen el bloque.
  • 15 13 ... 00 08: compone el bloque libre, el equivalente al registro eliminado.
Con unas simples cuentas podemos comprobar que cuadran los números, ya que 1768+110=1878, lo que equivale a la posición relativa: 1878-1024=854, justo donde comienza la siguiente celda.

Las celdas tienen un formato complejo que incluye más cabeceras y que está pensado para optimizar el espacio en disco. Con este sistema, por ejemplo un campo VARCHAR(20), no reserva 20 bytes de página, si no que ocupa tan solo lo que haya realmente en ese campo. Todo esto se verá en la siguiente entrada y la composición de celdas (¡otro tostón más!)

En resumen, una página de tipo B-Tree tiene espacio en el que habrá datos eliminados en tres partes distintas:
  • Desde el final del array de punteros a celdas hasta que comienza la celda, denominado "unallocated space"
  • Las celdas que hayan sido eliminadas y que forman los bloques libres
  • Los bytes fragmentados que hayan quedado debido al cambio de tamaños de celdas. Por ejemplo, si una celda contenía "12345" y pasa a contener "1234" tras un comando SQL de UPDATE, estos siempre son iguales o menores a 3 bytes, por lo que en general no hay mucho donde rascar.
Páginas Overflow
Cuando un registro no cabe en una sola página, por ejemplo, imaginemos una tabla con un campo VARCHAR(1090), en una base de datos con una página de tamaño 1024, el contenido de la celda es desbordado a una nueva página denominada Overflow.

Las páginas overflow solo contienen 4 bytes al inicio que indican el número de otra página si la celda continua ó 00 00 00 00 si es la última y la celda termina en ella.

Figura 3. Esquema página overflow. 

En la figura 3 se marca en amarillo la posición de la siguiente página overflow y en verde el contenido de la celda.

En las páginas de overflow hay espacio disponible y por lo tanto susceptible a tener datos eliminados. Ocupa desde el final de la celda hasta el final de la página. En la figura 3 se representa con el cuadrado azul.

¿Qué ocurre si se borra una tabla entera? pues la root page y todas las páginas que de ellas cuelguen (tanto b-tree interiores como hojas de página), además de las overflow, serán marcadas como páginas libres para ser reutilizadas, tal y como vimos en el post anterior.

Todos las entradas de la serie:

1 comments :

Alex dijo...

Buen artículo como de costumbre, una pregunta, toda esta información la has sacado de alguna web en concreto?, como por ejemplo http://sqlite.org/docs.html?, me gustaría saberlo para echar un vistazo.


Saludos!