LSM-Tree veya Log-Structured Merge Tree

LSM Tree Ne İçindir?

LSM-Tree hızlı yazma içindir. Açıklaması şöyle. 

- LSM (Log-Structured Merge) tree is a data structure designed for efficient write-intensive workloads, commonly used in storage systems and database engines.

- It offers high write throughput and efficient disk space utilization by leveraging sequential write operations and periodic merging of data.

LSM Tree Bileşenleri

Açıklaması şöyle

We can distinguish two key components of the tree, the in-memory buffer, also called Memtable, and the disk-resident tables. The main idea is to accept writes to the in-memory part of the tree, and to flush them periodically, or when a certain size is met.

A key aspect of this structure is ordering, indeed, keys are sorted both in RAM and on disk, enabling logarithmic searches.

Yani LSM Tree iki kısımdan oluşur

1. Memtable

2. Disk Resident Tables

1. Memtable

Sıralı yani sorted olması gerekir.  Red-Black Tree , AVL Tree,  Skip List gibi bir veri yapısı kullanılabilir

2. Disk Resident Tables

 SSTable - Sorted String Table  veri yapısı kullanılır

3. Yani

Skiplist + SSTable  kullanılabilir. 

 Skip List + SSTable kullanılabilir

Compaction

Açıklaması şöyle

Level 0 segments are periodically merged into Level 1 segments. This process is called compaction

B-Tree vs LSM-Tree

Açıklaması şöyle

The biggest difference is probably this:
  -B-Tree enables faster reads
 - LSM-Tree enables fast writes