Árboles B+ y Árboles LSM Hay dos estructuras de datos básicas cuando hablamos de los componentes básicos de Bases de datos. Los árboles B+ se usan cuando necesitamos menos tiempo de búsqueda e inserción y, por otro lado, los árboles LSM se usan cuando tenemos conjuntos de datos con uso intensivo de escritura y las lecturas no son tan altas.

Este artículo enseñará sobre Árbol de combinación estructurado de registros alias Árbol LSM . Los árboles LSM son la estructura de datos subyacente a muchas bases de datos de tipo clave-valor distribuidas NoSQL altamente escalables, como DynamoDB, Cassandra y ScyllaDB de Amazon.

Árboles LSM

Una versión simple de LSM Trees comprende 2 niveles de estructura de datos similar a un árbol:

• Memtable y reside completamente en la memoria (digamos T0)
• SStables almacenadas en el disco (digamos T1)

Árbol LSM simple

Los nuevos registros se insertan en el componente T0 memtable. Si la inserción hace que el componente T0 supere un cierto umbral de tamaño, un segmento contiguo de entradas se elimina de T0 y se fusiona con T1 en el disco.

Flujo de trabajo LSM

LSM utiliza principalmente 3 conceptos para optimizar las operaciones de lectura y escritura:

• Tabla de cadenas ordenadas (SSTables) : Los datos se clasifican en orden de modo que cada vez que se leen, su complejidad temporal sea O (Log(N)) en el peor de los casos, donde N es el número de entradas en una tabla de base de datos.

  1. SSTable

• Memtable :
  • Una estructura en memoria
  • Almacena datos de forma ordenada
  • Actúa como caché de reescritura
  • Después de alcanzar un cierto tamaño, sus datos se vacían como una SSTable en la base de datos.
  • Como, el número de SSTable aumenta en el disco y si alguna clave no está presente en los registros
    • Mientras leemos esa clave, necesitamos leer todas las SSTables, lo que aumenta la complejidad del tiempo de lectura.
    • Para superar este problema, el filtro Bloom entra en escena.
    • El filtro Bloom es una estructura de datos que ahorra espacio y puede indicarnos si falta la clave en nuestros registros con una tasa de precisión del 99,9%.
    • Para usar este filtro, podemos agregarle nuestras entradas cuando se escriben y verificar la clave al comienzo de las solicitudes de lectura para atender las solicitudes de manera más eficiente cuando ocupan el primer lugar.

Representación memtable

• Compactación :
  • Como almacenamos datos como SSTable en el disco, digamos que hay norte SSTable y el tamaño de cada tabla es METRO
  • Entonces el peor de los casos Leer la complejidad del tiempo es O( N* Registro(M) )
  • Entonces, a medida que aumenta el número de SSTables, Leer la complejidad del tiempo también aumenta.
  • Además, cuando simplemente estamos vaciando las SSTables en la base de datos, la misma clave está presente en varias SSTables.
  • Aquí viene el uso de un compactador.
  • Compactor se ejecuta en segundo plano, fusiona SSTables y elimina varias filas con la misma y agrega la nueva clave con los datos más recientes y los almacena en una nueva SSTable fusionada/compactada.

3.1. SSTables descargadas al disco

3.6. Compactador compactó 2 SSTables a 1 SSTable

Conclusión:

• Las escrituras se almacenan en un árbol en memoria (Memtable). Cualquier estructura de datos de soporte (filtros de floración e índice disperso) también se actualiza si es necesario.
• Cuando este árbol se vuelve demasiado grande, se descarga en el disco con las claves en orden.
• Cuando llega una lectura, la verificamos usando el filtro de floración. Si el filtro de floración indica que el valor no está presente, le informamos al cliente que no se pudo encontrar la clave. Si el filtro de floración significa que el valor está presente, entonces comenzamos a iterar SSTables del más nuevo al más antiguo.
• Complejidades del tiempo de LSM
  • Tiempo de lectura: O(log(norte)) donde N es el número de registros en el disco
  • Hora de escritura: O(1) como se escribe en la memoria
  • Hora de eliminación: O(log(norte)) donde N es el número de registros en el disco
• Los árboles LSM se pueden modificar para obtener estructuras de datos más eficientes utilizando más de 2 filtros. Algunos de ellos son bLSM, Diff-Index LSM.