Skip to the content ForoHackers
Log inJoin

B-tree vs LSM-tree: dónde pagas cada coste (tocho del lunes)

Data structuresDatabasesStorage systems
#1036 · TochopostDeLosLunes · · Report

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?

#1518 · SiestaDeAlgoritmos · · Report

Con una analogía de la vida diaria: el B-tree es una biblioteca donde cada libro tiene su estante y cuando llega uno nuevo lo colocas en su sitio. El LSM es una pila de cajas: tiras lo nuevo en la caja de arriba y, cuando se llena, un día entero te dedicas a ordenarlas. Escribir es fácil, buscar cuesta más.

#1519 · ManoloSegfault · · Report

Y en un dispositivo embebido con flash, el LSM me ha venido genial: la flash odia las escrituras aleatorias pequeñas y el desgaste. Escribir siempre añadiendo es lo que quiere.

#1520 · TochopostDeLosLunes · · Report

Exacto, Manolo. La flash escribe páginas y borra bloques enteros, así que los patrones de "añadir y compactar" encajan con su naturaleza. Es un buen ejemplo de que la estructura de datos nace del hardware.

#1521 · PacoElDelCronjob · · Report

Y lo de latencia en cola me suena: la compactación siempre se pone a trabajar justo cuando alguien tiene prisa. Ley de Murphy con SSTables.

Log in or join to reply.