Understanding of LSM tree (log structured merge tree)

0. The term ：

WAL （write ahead log） It is an additional log writing , It is used for simple flow record and backup .

LSM-tree (Log Structured-Merge Tree), Known as one of the Google Troika , It is also an additional log file , But compared with rough WAL, He divided the log into several sections , And every paragraph is indexed （ The query performance of each segment is Ologn ）.

SStables (Sorted Strings Table) It can be regarded as a map surface , But his queries rely on tree indexes , The complexity of the query is Ologn, He put the key-values Write a table , Then give this form key Sort , Then insert the sorted index table into the end of the array , There is a map structure .
Here's the picture ：

1.LSM-tree, Another name of is bigtable

I think it's more accurate to say , Is a long array , The element of an array is a key-value Pairs .

1.1 When writing ：

Add elements to the end of the file where the array information is stored , And build a sequential index for it （ The index can facilitate the subsequent rapid passage key Positioning elements ）.

When the array is appended to a certain extent （ such as 10M）, The file can't be put , Just create a new file , Create a new array index for this file .

1.2 When reading ：

When reading , Is to find the documents one by one , If there is k File , Each file has n Elements , Then the total length of the array is k*n , The complexity of the query is k * O(logn).

1.3 Optimization plan ：

To avoid the number of documents k More and more , The background will regularly merge small files into large files , namely , Merge the elements of the small file , Build a bigger sstable Indexes .

1.4 Other optimizations ：

1） Yes sstable The file is compressed in segments , Improve bandwidth utilization .

2) use LRU Wait for dinner yes sstable Page memory management , Improve cache access performance .

3）bloom filter, Search for key Skipping must not include key The file of , Speed up the search

4) Choose the right time to merge files , Avoid affecting reading performance .