B-tree contra LSM-tree: por dentro del índice de tu base de datos

Elegir base de datos sin saber qué estructura usa por debajo es elegir a ciegas. Las dos familias que dominan (B-tree y LSM-tree) resuelven el mismo problema con filosofías opuestas, y cada una cobra en un lugar distinto.

Primero: por qué el disco lo cambia todo#

En memoria, leer cualquier dirección cuesta más o menos lo mismo. En disco, no.

El disco no lee bytes: lee bloques, típicamente de cuatro u ocho kilobytes. Leer un byte o leer cuatro kilobytes cuesta prácticamente lo mismo.

Y cada acceso a un lugar distinto es caro: en SSD, decenas o centenas de microsegundos; en disco mecánico, milisegundos, porque el brazo tiene que moverse.

Eso invierte el criterio de diseño. En memoria, minimizas comparaciones. En disco, minimizas accesos.

Un árbol binario con un millón de elementos tiene veinte niveles. Si cada nivel es un acceso a disco, son veinte accesos, lo que es inaceptable.

La solución es hacer que cada nodo sea grande, del tamaño de un bloque, con cientos de hijos en vez de dos. El árbol queda bajito.

B-tree: lectura predecible#

Cada nodo ocupa una página de disco y guarda cientos de claves con sus punteros. Con un factor de ramificación de unos trescientos, un árbol de tres niveles direcciona veintisiete millones de registros.

Tres accesos en el peor caso, y los dos primeros niveles casi siempre están en memoria, así que en la práctica es uno.

La variante que usa toda base relacional es el B+tree: los datos quedan solo en las hojas, y las hojas están enlazadas entre sí en una lista. Eso deja los nodos internos más ligeros (caben más claves por página) y convierte el barrido por rango en caminar por una lista enlazada, sin subir y bajar.

Escritura: la página se lee, se altera y se regraba. Si se llenó, se parte en dos y el padre se actualiza. Escritura aleatoria: cada update toca una página distinta del disco.

Resultado: lectura predecible y rápida, incluso por rango y ordenación. Escritura mediana en volumen alto.

Quién lo usa: Postgres, MySQL/InnoDB, Oracle, SQL Server, SQLite. Prácticamente todo el mundo relacional.

LSM-tree: escritura secuencial#

El LSM-tree parte de una premisa distinta: la escritura aleatoria es cara, así que nunca hagas escritura aleatoria.

Toda escritura va a una estructura ordenada en memoria (la memtable) y a un log secuencial en disco, el WAL, que existe para recuperar en caso de caída.

Cuando la memtable se llena, se vuelca al disco de una vez, como un archivo ordenado e inmutable: un SSTable. Escritura siempre secuencial, siempre rápida.

El precio aparece en la lectura. Un registro puede estar en la memtable o en cualquiera de los archivos, del más nuevo al más viejo. Para no abrirlos todos, cada archivo tiene un filtro de Bloom, que responde al instante "seguro que no está aquí", y ahorra la lectura.

Y como los archivos se acumulan, existe la compactación: un proceso de fondo que junta archivos, descarta versiones antiguas y elimina lo que fue borrado.

Quién lo usa: Cassandra, RocksDB, LevelDB, HBase, ScyllaDB, y el motor de almacenamiento de varias cosas que usas sin saberlo, incluidas muchas bases de series temporales.

Amplificación: las tres cuentas#

Este es el vocabulario que permite compararlos de forma honesta.

Amplificación de escritura: cuánto escribe el disco realmente por cada byte que grabaste.

En LSM, el mismo dato se reescribe en cada nivel de compactación. Un megabyte que grabaste puede convertirse en diez megabytes de escritura real. Eso desgasta el SSD y consume ancho de banda de I/O.

En B-tree, reescribes la página entera para alterar una fila. Eso también amplifica, pero de forma más predecible.

Amplificación de lectura: cuántos accesos hacen falta para encontrar un registro.

En B-tree, es el número de niveles: pequeño y constante.

En LSM, es el número de archivos que hay que consultar: variable, y por eso el filtro de Bloom importa tanto.

Amplificación de espacio: cuánto espacio se ocupa más allá del dato útil.

En LSM, las versiones antiguas todavía sin compactar ocupan espacio.

En B-tree, las páginas dejan espacio libre a propósito para que quepan inserciones futuras: fragmentación por diseño.

La tabla de decisión#

Elige B-tree cuando

• ·la lectura por rango y la ordenación son frecuentes
• ·la latencia predecible importa más que el pico de rendimiento
• ·necesitas transacciones ACID ricas
• ·el patrón es más lectura que escritura

Elige LSM cuando

• ·el volumen de escritura es alto y continuo
• ·el acceso es por clave, no por rango
• ·la compresión importa: un archivo inmutable y ordenado comprime mejor
• ·toleras variación de latencia

El detalle que decide en la práctica#

La variación de latencia del LSM durante la compactación es real y es lo que más sorprende a quien migra.

El p50 puede ser excelente y el p99 saltar cuando una compactación grande está corriendo. Si tu producto tiene un SLO agresivo de cola, eso tiene que entrar en la cuenta, y existen estrategias de compactación distintas (por nivel, por tamaño) que cambian amplificación por previsibilidad.

Del otro lado, el B-tree sufre con la escritura concurrente en la misma página y con la fragmentación a lo largo del tiempo, lo que aparece como degradación lenta que solo un VACUUM o REINDEX resuelve.

Ninguna de las dos es gratis. La pregunta correcta nunca es "cuál es mejor", sino "qué cuenta prefiero pagar".

Qué cambia esto en tu día#

Tres cosas concretas:

1. Al elegir base de datos, busca en la documentación qué estructura usa. Eso te dice más sobre el comportamiento bajo carga que la página de marketing.

2. Al investigar latencia irregular en una base LSM, mira las métricas de compactación antes que cualquier otra cosa.

3. Al investigar degradación lenta en una base B-tree, mira fragmentación, bloat y estadísticas desactualizadas.

Saber el nombre de la estructura convierte "la base está rara" en una hipótesis comprobable.