B+tree : disk ⇒ random access 하지만, Sequential이 성능이 좋음 ⇒ array사용

Bst : DRAM ⇒ NoSQL은 SkipList 사용

⇒ 구글이 선택한 이 2가지 요소를 함께 사용하는 것이 LSM-Tree이다.

Log-Structured Merge Tree

• write-intensive하다. ⇒ fast insertion!
• key-value stores에서 자주 사용된다.
• MemTable - Immutable(수정불가능한) Memtable로 구성되어있다.
  • Immutable Memtable이 disk로 flush되어 SSTable(Sorted array)이 된다.

🎯 동작 과정

• 메모리 64MB의 skip List가 full이되면

• 수정 불가능한 데이터 구조인 Immutable MemTable이 된다.

• 수정불가능한 skiplist를 array로 변환(레벨 0의 노드를 순차적으로 읽으면 array가 됌) ⇒ 그 후 flush
  • 이 일련의 작업을 Background Compaction이라 부름

🎯 실제 예시

• compaction이 insertion에 영향을 주지 않는다 → insertion이 빠르다!
• search는 좀 느리다. 왜? disk I/O를 유발하기 때문에