El árbol LSM (del árbol de combinación con estructura de registro - árbol de combinación con estructura de registro) es una estructura de datos utilizada en muchos DBMS que proporciona acceso rápido al índice en condiciones de solicitudes de inserción frecuentes (por ejemplo, cuando se almacenan registros de transacciones ). Los árboles LSM, como otros árboles, almacenan pares clave-valor. Un árbol LSM mantiene dos o más estructuras diferentes, cada una optimizada para el dispositivo en el que se almacenará. La sincronización entre estas estructuras ocurre en bloques.
Una versión simple de un árbol LSM, un árbol de dos niveles, consta de dos estructuras en forma de árbol C 0 y C 1 . C 0 es más pequeño y se almacena completamente en RAM, mientras que C 1 está en memoria no volátil. Las nuevas entradas se insertan en C 0 . Si, después de la inserción, el tamaño de C 0 supera algún umbral predeterminado, el segmento contiguo se elimina de C 0 y se fusiona con C 1 en el almacenamiento persistente. Se logra un buen desempeño debido a que los árboles están optimizados para su almacenamiento, y la fusión se realiza de manera eficiente y en grupos de varios registros, utilizando un algoritmo que recuerda al merge sort .
La mayoría de los árboles LSM utilizados en la práctica implementan varios niveles. El nivel 0 (llamémoslo MemTable) se almacena en la RAM y se puede representar mediante un árbol normal. Los datos en los dispositivos de almacenamiento persistente se almacenan en forma de tablas ordenadas por clave ( SSTable ). La tabla se puede almacenar como un archivo separado o como un conjunto de archivos con valores clave que no se superponen. Para encontrar una clave específica, debe verificar su presencia en MemTable y luego revisar todas las SSTables en el dispositivo de almacenamiento persistente.
Esquema de trabajo con LSM-tree:
La clave buscada puede aparecer en varias tablas a la vez en dispositivos de almacenamiento persistente, y la respuesta final depende del programa. La mayoría de las aplicaciones solo necesitan el último valor asociado con una clave determinada. Otros, como Apache Cassandra , en el que cada valor es una fila de la base de datos (y una fila puede tener un número diferente de columnas en diferentes tablas de almacenamiento persistente), tienen que procesar todos los valores de alguna manera para obtener el resultado correcto [1] . Para reducir el tiempo de ejecución de consultas, en la práctica intentan evitar la situación con demasiadas tablas en dispositivos de almacenamiento persistente.
Se han desarrollado extensiones al método de "nivel" para mantener estructuras B+ , como bLSM [2] y Diff-Index. [3]
La arquitectura de árbol LSM le permite satisfacer una solicitud de lectura desde la RAM o en una llamada a dispositivos de almacenamiento persistente. La escritura también es siempre rápida, independientemente del tamaño de almacenamiento.
SSTable en dispositivos de almacenamiento persistente es inmutable. Por lo tanto, los cambios se almacenan en MemTable y las eliminaciones deben agregar un valor especial a MemTable. Debido a que las nuevas lecturas se producen secuencialmente en el índice, el valor actualizado o la entrada de eliminación de valor se producirán antes que los valores antiguos. Una combinación de ejecución periódica de SSTables antiguos en el almacenamiento persistente hará estos cambios y, de hecho, eliminará y actualizará los valores, eliminando los datos innecesarios.
| Árbol (estructura de datos) | |
|---|---|
| Árboles binarios | |
| Árboles binarios autoequilibrados |
|
| árboles B |
|
| árboles de prefijo |
|
| Partición binaria del espacio | |
| Árboles no binarios |
|
| Rompiendo el espacio |
|
| Otros árboles |
|
| Algoritmos | |