Dos formas de organizar datos en disco, y cada una paga el coste en un sitio distinto.
B-tree (la de casi todos los motores relacionales clásicos). Un árbol de páginas de tamaño fijo (por ejemplo 8 KB). Para modificar un registro se localiza su página y se reescribe en su sitio.
- Lecturas: pocas páginas por búsqueda (el árbol es bajo y ancho), muy predecibles.
- Escrituras: aleatorias en disco, y cambiar un byte puede obligar a reescribir toda una página (amplificación de escritura). Se protege con WAL.
LSM-tree (muchos motores de clave-valor). Las escrituras van a una tabla en memoria (memtable) y a un log; cuando se llena, se vuelca como un fichero ordenado inmutable (SSTable). En segundo plano, la compactación fusiona ficheros.
- Escrituras: secuenciales y rápidas. Excelente para ingesta.
- Lecturas: pueden tener que mirar la memtable y varios ficheros. Se mitigan con filtros de Bloom y con la compactación.
- Coste oculto: la compactación reescribe datos varias veces (amplificación de escritura otra vez) y compite con las lecturas por el disco.
| B-tree | LSM-tree | |
|---|---|---|
| Escritura | aleatoria, en sitio | secuencial, añadir |
| Lectura | 1 camino por el árbol | varios ficheros + filtros |
| Amplificación | por página y WAL | por compactación |
| Latencia | estable | picos durante compactaciones |
Nunca gana siempre. Se elige mirando la carga: ¿muchas escrituras?, ¿lecturas puntuales o rangos?, ¿cuánto te importa la latencia en cola?