README · by ansango
← Volver al libro

Storage and retrieval (OLTP)

Cómo se almacenan los datos en disco: log-structured, B-trees, LSM-trees, índices secundarios y por qué cada algoritmo favorece distintos patrones de carga

~5 min de lectura
Resumen

Una base de datos es, en el fondo, una estructura de datos que persiste en disco y responde consultas. Esta nota cubre los algoritmos de almacenamiento y recuperación que dominan las bases de datos modernas: log-structured (LSM-trees), B-trees, índices secundarios y las implicaciones operativas de cada opción.

Por qué importa el almacenamiento

El libro abre con la observación más simple y más profunda: las bases de datos gastan la mayor parte del tiempo moviendo datos entre disco y memoria. La elección del formato de almacenamiento determina el rendimiento de cada operación.

Jerarquía de almacenamiento:

   Registers (CPU)  ◄─── 1 ns
        │
   L1 cache        ◄─── 1 ns
        │
   L2 cache        ◄─── 10 ns
        │
   L3 cache        ◄─── 100 ns
        │
   RAM             ◄─── 100 ns
        │
   SSD             ◄─── 100 μs
        │
   HDD             ◄─── 10 ms
        │
   Network         ◄─── 1 ms
Disco es 1000x más lento que RAM

Un acceso a disco es mil veces más lento que un acceso a RAM. Por eso las bases de datos tratan de minimizar accesos a disco, no maximizar CPU.

Database-centric architecture

El libro comienza con un patrón básico usado en bases de datos sencillas (SQLite, dbm):

key1 → value1
key2 → value2
key3 → value3

Cada clave es un offset en un archivo. La búsqueda es O(1) en el mejor caso. La limitación: el modelo es muy pobre (clave plana, valor binario).

Log-structured storage

El primer paso más sofisticado es el log-structured: append-only.

Log:
┌─────────────────────────────────────────┐
│ k1=v1 │ k2=v2 │ k3=v3 │ k4=v4 │ k5=v5 │
└─────────────────────────────────────────┘
     ▲                                ▲
   write here                    read from here

Características

Por qué es útil

El log como estructura universal

Kafka, los logs de transacciones, los logs de eventos: todos vienen de esta idea. Un log es muchas cosas: almacenamiento, replicación, fuente de verdad.

Hash indexes

El primer paso para hacer el log consultable es añadir un índice hash en memoria.

# Hash index en memoria
index = {
    "k1": 0,    # offset 0
    "k2": 6,    # offset 6
    "k3": 12,   # offset 12
    ...
}

Características

Compactación

El log crece indefinidamente. Para evitarlo, los sistemas compactan: mantienen solo la versión más reciente de cada clave.

Antes de compactación:
┌─────────────────────────────────────┐
│ k1=v1 │ k2=v2 │ k1=v3 │ k3=v3 │ k1=v5 │
└─────────────────────────────────────┘

Después de compactación:
┌────────────────────┐
│ k1=v5 │ k2=v2 │ k3=v3 │
└────────────────────┘
Compactación = garbage collection

Es el mismo concepto que en memoria (generation scavenging). Las versiones antiguas se eliminan. Solo mantienen la más reciente.

SSTables (Sorted String Tables)

Para superar la limitación del hash, los sistemas usan SSTables: log ordenado por clave.

SSTable:
┌─────────────────────────────────────────┐
│ apple=red, k1=v1                       │
│ banana=yellow, k2=v2                   │
│ cherry=red, k3=v3                       │
│ ...                                     │
└─────────────────────────────────────────┘
Cada bloque está ordenado por clave.

Ventajas

Implementaciones

LSM-trees (Log-Structured Merge-Trees)

El libro describe las LSM-trees como la evolución de los SSTables. La estructura típica:

Memtable (en RAM, mutable)
    ↓ flush cuando se llena
SSTable 1 (en disco, inmutable)
    ↓ cuando se acumulan varios
SSTable 2 (en disco, merge con SSTable 1)
    ↓
SSTable mayor (mergea varios menores)

Beneficios

Limitaciones

LSM-trees son el estándar de las bases modernas

LevelDB, RocksDB, Cassandra, HBase, ScyllaDB, DynamoDB (con Local Secondary Indexes) usan LSM-trees. La razón: las escrituras son baratas, lo que importa para workloads con muchos writes.

B-trees

El otro gran enfoque es el B-tree, usado en la mayoría de bases relacionales.

Estructura

B-tree:
                    ┌─────────────┐
                    │  [50, 100]  │  ← root
                    └──────┬──────┘
                           │
              ┌────────────┼────────────┐
              ▼            ▼            ▼
        ┌─────────┐  ┌─────────┐  ┌─────────┐
        │[10, 30] │  │[60, 80] │  │[120,150]│
        └────┬────┘  └────┬────┘  └────┬────┘
             │            │            │
        ┌────┴────┐  ┌────┴────┐  ┌────┴────┐
        ▼         ▼  ▼         ▼  ▼         ▼
      [≤10]  [11-30] ...           ...

Características

B-trees vs LSM-trees

CaracterísticaB-treeLSM-tree
ReadsMás rápidosMultiple SSTables, más I/O
WritesMás lentos (página random)Muy rápidos (append)
CompresiónMás difícilMejor (orden + bloques)
PredicibilidadEstableVariable (compaction)
MadurezMásMenos

[!tip> Elige el árbol según el workload

  • Read-heavy: B-tree (Postgres, MySQL, Oracle).
  • Write-heavy: LSM-tree (Cassandra, RocksDB).
  • Mixto: depende del ratio y de los índices secundarios.

Índices secundarios

Los índices secundarios son índices adicionales para búsquedas que no son por clave primaria.

-- Tabla principal
CREATE TABLE users (
    id SERIAL PRIMARY KEY,
    email VARCHAR(255),
    name VARCHAR(255)
);

-- Índice secundario sobre email
CREATE INDEX idx_users_email ON users(email);

Implementación

Costos de los índices secundarios

Cada índice adicional multiplica el coste de escritura (hay que actualizar todos los índices). El libro insiste: cada índice tiene un precio.

Multicolumn indexes

-- Índice compuesto (last_name, first_name)
CREATE INDEX idx_users_name ON users(last_name, first_name);

Útil para queries que filtran por ambos campos. El orden importa: solo funciona para queries que usan el prefijo más a la izquierda.

Índices covering

Un índice que incluye todas las columnas que la query necesita, sin tener que ir al heap.

-- Índice covering
CREATE INDEX idx_users_covering ON users(email) INCLUDE (name);
Los índices covering son trucos poderosos

Postgres y otros permiten columnas extra en el índice. La query puede servirse solo desde el índice, sin tocar la tabla.

Manteniendo los índices

El libro advierte sobre los costes ocultos:

-- Reindexar en Postgres
REINDEX INDEX idx_users_email;

-- Actualizar estadísticas
ANALYZE users;

Comparación final

SistemaModelo de almacenamientoMejor para
Postgres, MySQLB-treeRead-heavy, transacciones
MongoDB, CassandraLSM-treeWrite-heavy, escala horizontal
LevelDB, RocksDBLSM-treeEmbedded, baja latencia
HBaseLSM-treeBig data, scan-heavy
CockroachDB, SpannerB-tree distribuidoGeo-distribuido, OLTP
FoundationDBB-treeTransacciones serializables

Resumen en tres frases

Próximos pasos