En su nivel más fundamental, una base de datos hace dos cosas

• Permite almacenar datos
• Permite consultar esos datos

Desde las perspectiva de la BD, ¿Cómo podemos almacenar los datos? y, cuando nos consulten, cómo podemos devolver esos datos?

• Probablemente usted no va a implementar su propio motor de almacenamiento, pero si va a escoger uno. Por eso debe saber que hace un motor de almacenamiento por debajo
• Hay diferencias muy marcadas entre los motores de almacenamiento optimizados para cargas transaccionales vs los optimizados para cargas analíticas

Motores de Almacenamiento - Dos familias (Para sistemas transaccionales)

• Estructurados por logs
• Orientado a paginación

Las estructuras de datos que soportan las bases de datos modernas

Ejemplo: Funciones db_get() y db_set() que implementan una base de datos muy sencilla

!/bin/bash
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}

• De la misma forma como funciona esta BD, muchas BDs de datos modernas utilizan un log

  • log: archivo tipo append-only que es una secuencia de records añadidos al final de una estructura de datos

• Escribir datos → Buen desempeño. Insertar datos al final de un archivo es muy eficiente

• Consultar datos → Mal desempeño. El costo de consulta es O(n). Si se duplica la cantidad de records en la BD, el tiempo de consulta se duplica también. La solución a esto son los índices.

Índice: estructura de datos adicional derivada de los datos primarios para obtener acceso rápido a los datos.
- Aceleran las consultas de lectura
- Pero, hacen que las escrituras sean más lentas. Esto porque al escribir se debe actualizar el índice.

Trade-off en sistemas de almacenamiento: Índices aceleran las consultas, pero afectan negativamente las escrituras

• Por eso es que las BDs no indexan todo de forma predeterminada, eso lo debe hacer el desarrollador porque es el que conoce los patrones de acceso a los datos

Índices

def. Estructura de datos adicional que se deriva de los datos primarios y sirve para facilitar la búsqueda de información en la BD.

• Trade-off en los sistemas de almacenamiento
  • índices aumentan desempeño de lectura pero
  • reducen desempeño de escritura

Tipos de Índices → Las estructuras de datos que soportan las bases de datos modernas

• Índices hash → “Hasheé” llaves a valores
• Tablas SST → Tablas de cadenas de caracteres ordenadas (sorted string tables). Almacena los datos en disco de forma ordenada
• Árboles LSM → Log-structured merge tree
• Árboles-B → Divida la BD en bloques de tamaño fijo

Índices Hash
def. Estructura adicional tipo llave-valor donde la llave es el identificador del dato en la estructura primaria y el valor es la ubicación del dato en la tabla

• Se basa en la estructura HashMap (*tipo de dato *diccionario** en múltiples lenguajes de programación)
• Log + Hash map

• Cada vez que añade un nuevo dato al log de la BD, también actualiza el Hash Map
• Para no quedarse sin espacio en disco, se realiza un proceso de compactación y agrupamiento(merging) para solo almacenar el valor más actualizado de una llave y reducir el espacio en disco
  • compactación → Eliminar llaves duplicadas en el log y solo almacenar la última copia
  • Agrupamiento (merging) → Juntar varios segmentos en uno solo

    

Limitaciones de una tabla Hash

• Debe estar en memoria principal → En disco es muy complicado tener un hash map porque es lento. Debe hacer muchas operaciones aleatorias de entrada y salida y es costoso hacer que escale eficientemente.

Tablas SST

def. Tablas de cadenas de caracteres ordenados (sorted string tables)
Formato de almacenamiento en disco donde la secuencia de parejas llave-valor está ordenado con base en la llave.
Características:

• Las parejas llave-valor se almacenan en forma ordenada en disco
• Cada llave solo puede aparecer una vez, con el valor actualizado

  

• El proceso de agrupamiento (merging) se encarga de eliminar los valores no actualizados de las llaves

Árboles LSM (Log-structured merge tree):

Usada en Bases de datos NoSQL
Son una cascada de Tablas SST que se integran en segundo plano
“Data is initially written to a memory component (memtable) and then periodically flushed to disk-based components (SSTables).”

• Datos ordenados → consultas basadas en rangos eficientes
• Escrituras secuenciales a disco → Buen throughput de escritura

1. Usuario hace una operación de escritura
2. Las escrituras es escriben en memoria principal
   1. memtable → Estructura de datos en memoria para almacenar datos recientes
3. Cuando memtable se llena, se ordenan y se envian a disco (sort and flush)
4. Al estar en disco después de un tiempo, ocurre un algoritmo de agrupamiento y compactación.
   1. merge y compact → Agrupar las SSTables y eliminar valores actualizados o borrados

Básicamente, se tiene una estructura tipo árbol en RAM que recibe las escrituras (Memtable). Cuando la memtable se llena, los datos se envían al disco. En el disco se hace un proceso de segundo plano que agrupa y compacta los segmentos para eliminar valores eliminados y desactualizados.

Nota. DynamoDB, Cassandra, BigTable y RocksDB usan Árboles LSM

• Google BigTable fue la tecnología pionera que introdujo los términos SSTable y Memtable

Árboles-B (B-Trees )
El tipo de indice más utilizado y el estándar para las bases de datos relacionales (Y muchas no relacionales). Tipo update-in-place

Filosofía: Dividen la base datos en bloques de tamaño fijo (páginas), tradicionalmente de 4 KB y leen/escriben una página a la vez.

• Es un diseño que encaja más con el hardware subyacente porque los discos también se dividen en bloques de tamaño fijo
• Cada página se puede identificar utilizando una dirección (como un apuntador en disco, no en memoria). Se utiliza las referencias de disco para construir un árbol de páginas
• Cada llave en las “hojas” del B-tree tiene una apuntador a la dirección en disco donde está el bloque que contiene el valor de la llave

Son el tipo de estructura de índice más utilizado en bases de datos relacionales. MySQL, Postgres, Oracle y muchas más usan árboles-b para sus indices.

El árbol siempre está balanceado y tiene una profundidad de O(log n)

• Casi todas las BDs pueden estar en un B-tree que sea de 3 a 4 niveles de profundidad. Un árbol de 3 niveles, páginas de 4KB y un factor de branching de 500 puede almacenar hasta 265 TB

Explicación Árboles-B

Procesamiento Transaccional vs Analítico

Originalmente, una escritura a una BD representaba una transacción comercial.

• Cliente comprando algo
• pagarle a un empleado

OLTP → Online transaction processing

• Patrones de acceso similares a los de una transacción comercial
  • App normalmente consulta un pequeño número de filas con base en un índice (llave)

OLAP → Online analytical processing

• Patrones de acceso para el análisis de datos
  • Consulta sobre cantidades masivas de filas pero a pocas columnas. Calcula valores agregados (SUM, AVG, COUNT)

Procesamiento transaccional vs analitico

¿El mismo sistema que utilizo para que mis clientes reserven un asiento en el avión es el mismo sistema que utiliza el analista para detectar patrones de compra en los vuelos? NO!
Por eso se crearon dos aproximaciones distintas. Dos tipos de motores de almacenamiento
OLTP → BD que soporta que los clientes reserven un puesto en el avión

• Optimizado para procesamiento transaccional
• Son sistemas “user facing”. Manejan un volumen masivo de consultas

OLAP → BD que soporta las operaciones de analitica e inteligencia de negocios. Por ejemplo, averiguar cuantos puestos se han vendido en un mes

• Optimizado para analítica
• Son sistemas “Business-analyst facing”. Manejan poco volumen de consultas pero las consultas son mucho más grandes
• Cuando sus consultas necesitan escanear una gran cantidad de filas, los índices de las BDs OLTPs pierden relevancia. Acá es más importante codificar los datos de una forma compacta.

Al principio de los sistemas computacionales, las BDs se utilizaban tanto para procesamiento transaccional como analítico. SQL es flexible en ese aspecto. No obstante, la década de 1980 las compañías dejaron de usar sus sistemas OLTP para analítica y empezaron a hacer consultas de análisis en BDs separadas → Esas bases de datos se conocen como Bodegas de Datos (Data warehouses)

Data Warehousing (Bodegas de datos)