Log-Structured Merge Tree

https://www.youtube.com/watch?v=i_vmkaR1x-I

https://www.linkedin.com/pulse/day-storage-engines-lsm-tree-farhan-khan/

• key-value 형태

• 로그파일 기반

  • append-only, 따라서 쓰기 작업의 퍼포먼스가 좋다, O(1)
  • 쓰기작업은 disk에 바로하지 않고 순차적으로 로그파일과 memTable에 쓴다
  • memTable말고 로그파일이 필요한 이유는 Write-Ahead Log 사용 이유 처럼 시스템이 crash했을 때 복구를 위해서이다.

  

• Cassandra, LevelDB, RocksDB 등 많은 NoSQL DB가 LSM Tree 사용

참고: 데이터베이스와 자료구조 요약

1. Red-Black Tree: 삽입/삭제가 빠름.
2. B-Tree: 대규모 데이터에서 검색과 범위 쿼리에 최적화됨. SQL-like 연산에 적합.
3. 자료구조 선택:
   • 데이터베이스는 사용 목적에 따라 다른 자료구조를 선택함.
   • Redis: B-Tree 대신 Sorted Sets 등 간단한 구조 사용 (캐시 중심).

MemTable (메모리테이블)

• key값으로 정렬
• balanced binary tree (RedBlack Tree)
• 일정 사이즈에 도달하면 disk의 SSTable에 데이터를 flush 한다.

• in memory hash map을 사용해 각각의 key의 값이 disk의 어디에 있는지 memTable에 저장

• SSTable 이 정렬되어 있기 때문에 메모리에 모든 key의 index를 유지할 필요가 없다

SSTable (Sorted String Table)