B-Tree, LSM-Tree 차이점이 뭘까?

서론

데이터 중심 애플리케이션 설계 3장을 읽으면, 특정 키의 값을 효율적으로 찾기 위한 색인에 대해서 설명해줍니다.

그리고 색인에 대한 데이터구조를 설명해주는데 해시 색인 이후 LSM-Tree와 B-Tree가 대표적으로 나오고 해당 부분을 설명해줍니다. 하지만 읽으면서 이게 무슨 소리지? 싶은 내용이 많아서 혼자 정리해보게 되었습니다.. 생각보다 책내용이 많이 어렵더라구요 ^^;

LSM-Tree(Log-Structured Merge-Tree)

LSM-Tree(Log-Structured Merge-Tree)는 대량의 쓰기 성능을 최적화하고, 순차적인 디스크 접근을 활용하여 저장소 성능을 개선하는 데이터 구조입니다.

1. LSM-Tree 기본 개념

쓰기(Append-Only)를 최적화

• 데이터를 기존 파일에 덮어쓰지 않고, 새로운 데이터 세그먼트를 추가하는 방식이다.
• 쓰기 작업이 디스크의 순차적 I/O를 활용하여 빠르게 수행된다.

읽기 성능은 상대적으로 느릴 수 있음

• 최신 데이터는 메모리에 있고, 오래된 데이터는 여러 개의 세그먼트(SS테이블)에서 검색해야 한다.

여기서 SS테이블이란?
정렬된 문자열 테이블(Sorted String Table)을 말하며 키(key)를 기준으로 정렬된 상태를 유지한다. 컴팩션을 통해 중복된 키를 가진 데이터를 병합하고 최신 값만 유지된다.

컴팩션(Compaction)을 활용하여 데이터 정리

• 컴팩션: 중복된 키를 버리고 각 키의 최신 갱신값만 유지하는 것을 말한다.
  

• 주기적으로 여러 세그먼트들을 병합하여 크기가 큰 데이터 세그먼트로 변환하여 읽기 성능을 최적화할 수 있다.

2. LSM-Tree 구조 및 작동 방식

(1) 쓰기 과정

• 새로운 데이터는 먼저 메모리(Memtable)에 저장된다.
• Memtable이 가득 차면, 불변(Immutable) SS테이블(SSTable)로 변환되어 디스크에 저장된다.
• 이 과정은 기존 데이터를 덮어쓰지 않고, 새로운 파일을 계속 추가하는 방식으로 진행된다.

(2) 읽기 과정

• 최신 데이터는 Memtable(메모리)에서 조회한다.
• Memtable에 없으면, 가장 최근에 생성된 SS테이블부터 차례로 검색.
• 오래된 데이터는 여러 개의 SS테이블을 검색해야 하므로 B-트리보다 상대적으로 느릴 수 있다.

(3) 컴팩션(Compaction)

• 여러 개의 SS테이블이 쌓이면, 파일을 병합하여 오래된 데이터를 삭제하고 새로운 SS테이블을 생성한다.
• 이를 통해 디스크 공간을 최적화하고, 읽기 성능을 개선할 수 있다.
• 레벨 컴팩션(Leveled Compaction)과 크기 계층 컴팩션(Size-Tiered Compaction) 기법이 존재한다.

레벨 컴팩션(Leveled Compaction)
SS테이블을 더 작은 크기의 여러 레벨로 나누고 오래된 데이터는 다음 레벨로 이동하는 방식.
크기 계층(Size-Tiered Compaction)
새로운 작은 SS테이블을 오래된 큰 SS테이블과 점진적으로 병합하는 방식.

B-Tree

1. B-Tree 기본 개념

• 1970년대 등장하여 관계형 데이터베이스의 표준 색인 구조가 되었다.
• SS테이블과 마찬가지로 키-값 쌍을 정렬된 상태로 유지하며, 키 검색 및 범위 질의(Range Query)에 효율적이다.
• 트리가 자동으로 균형을 유지하며, 깊이(Height)는 O(log n)이다.
• 디스크 접근을 최소화하기 위해 페이지 단위로 데이터를 관리한다.
• 각 노드는 여러 개의 키와 하위 노드를 가질 수 있으며, 트리의 분기 계수(Branching Factor)가 크다.

  분기 계수: 한 페이지가 가질 수 있는 하위 페이지의 최대 개수.

• 한 페이지에서 다수의 키를 저장할 수 있기 때문에 디스크 I/O가 줄어들어 성능이 향상된다.
• 기본적으로 쓰기 동작 시 페이지를 덮어써서 데이터를 갱신한다.

2. B-Tree 구조 및 작동 방식

(1) B-Tree 주요 구성 요소

• 루트 노드(Root Node): B-Tree 최상위 노드. 모든 검색 연산은 루트 노드에서 시작됨.
• 내부 노드(Internal Node): 여러 개의 키를 포함하며, 하위 노드에 대한 포인터를 가짐.
  각 키는 특정 범위의 데이터를 포함하는 하위 노드를 가리킴.
• 리프 노드(Leaf Node): 최하단 노드로, 실제 데이터(키-값)를 저장. 리프 노드는 서로 연결될 수 있어, 순차적인 범위 조회 시 빠르게 이동 가능.

(2) 검색(Read) 과정

• 루트 노드에서 시작하여 찾고자 하는 키의 범위가 포함된 하위 노드로 이동.
• 내부 노드를 탐색하여 적절한 리프 노드까지 이동.
• 리프 노드에서 원하는 키를 검색하여 값 반환.

251을 찾는다면, 200과 300 경계 사이의 페이지 참조를 따라가야한다는 사실을 알 수 있다.

(3) 삽입(Insert) 과정

• 새로운 키가 들어갈 적절한 리프 노드를 찾음.
• 리프 노드에 빈 공간이 있으면 키를 삽입.
• 리프 노드가 가득 찼다면 노드를 분할(Split)하여 두 개의 노드로 나눔.
• 상위 부모 노드에 새로운 키를 삽입하여 분할된 노드를 연결.
• 재귀적으로 부모 노드도 가득 찼을 경우, 트리의 높이가 증가할 수 있음.

만약 키 값 갱신이라면 리프 노드를 찾은 후 값을 변경한다.

(4) 삭제(Delete) 과정

• 삭제할 키가 포함된 리프 노드를 찾음.
• 키를 삭제한 후, 노드에 최소 개수의 키가 남지 않으면 병합(Merge) 수행.
• 병합이 필요할 경우, 부모 노드에서 해당 키를 조정하여 균형을 유지.

(5) 장애 복구 방식

• 데이터베이스가 고장난 상황에서 스스로 복구할 수 있도록 WAL 데이터구조를 추가해 B-Tree를 구현한다.
• WAL: 디스크에 쓰기 전 WAL(Write-Ahead Log, 재실행 로그)을 사용하여 변경 사항을 기록하는 추가 전용 파일.
• WAL은 장애 발생 시 B-Tree를 일관성 있는 상태로 복구하는데 사용한다.

장점과 단점

1. LSM-Tree 장점

(1) 쓰기 성능이 뛰어남

• 순차적인 디스크 쓰기(Append-Only)를 활용하고 SS테이블을 주기적으로 병합하는 방식으로 쓰기 성능을 향상시킨다.
• 기존 데이터를 덮어쓰지 않기 때문에, 랜덤 쓰기 성능이 중요한 B-트리보다 유리하다.

(2) 쓰기 증폭(Write Amplification)이 낮음

• 쓰기 증폭: 데이터베이스에 한 번 쓰인 데이터가 디스크에서 여러 번 다시 기록되는 현상.
• B-Tree는 페이지 단위 덮어쓰기로 인해 같은 데이터를 여러 번 기록해야 한다.
• LSM-Tree는 순차 쓰기로 데이터를 저장하여 SSD 및 HDD의 쓰기 성능을 극대화할 수 있다.

(3) 스토리지 공간 활용이 효율적

• B-Tree는 페이지 단위 저장이므로 페이지 파편화(Fragmentation)로 인해 미사용 공간이 발생할 가능성이 크다.
• LSM-Tree는 주기적으로 SS테이블을 병합하면서 파편화를 제거하기 때문에 저장 공간 활용도가 높다.

(4) SSD와의 궁합이 좋음

• SSD의 내부 펌웨어는 순차 쓰기를 선호하므로, LSM-Tree의 순차 쓰기 방식이 SSD 성능에 유리하다.
• 낮은 쓰기 증폭과 적은 파편화로 인해, LSM-Tree는 SSD의 I/O 대역폭을 효율적으로 활용 가능하다.

2. LSM-Tree 단점

(1) 읽기 성능 저하

• 최신 데이터는 Memtable에서 빠르게 검색 가능하지만, 오래된 데이터는 여러 개의 SS테이블을 검색해야 하기 때문에 읽기 성능이 저하될 가능성이 있다.
• 또한 컴팩션이 원활하지 않으면 디스크 내 병합되지 않은 세그먼트 파일이 많아지고, 이는 읽기 성능을 저하시킬 수 있다.

특정 키가 데이터베이스에 존재하지 않음을 빠르게 판별해주는 블룸 필터(Bloom Filter)를 활용하여 불필요한 SS테이블 조회를 줄이는 최적화 방법이 존재 한다.

(2) 컴팩션(Compaction)으로 인한 성능 저하

• 디스크 I/O 리소스를 공유하므로, 컴팩션이 진행되는 동안 대기 시간이 증가할 가능성이 있다.
• 특히 높은 쓰기 처리량(High Write Throughput)이 필요한 경우, 컴팩션이 쓰기 속도를 따라가지 못하면 문제 발생 가능성이 있다.
• 이 문제를 방지하려면 지속적인 모니터링 및 적절한 설정 조정 필요하다.

(3) 트랜잭션 처리에 불리하다.

• B-Tree는 각 키가 색인의 한 곳에 정확하게 존재한다.
• 하지만, LSM-Tree는 같은 키가 여러 개의 SS테이블에 존재할 수 있.
• 이로 인해 강력한 트랜잭션 격리(Transaction Isolation)가 필요한 경우, B-Tree가 더 적합하다.

3. B-Tree의 장점

(1) 빠른 읽기 성능

• 모든 키가 정렬된 상태로 저장되며, 검색 및 범위 조회가 빠르다. (O(log n))
• 데이터가 하나의 트리 구조에서 관리되므로, 여러 파일을 검색해야 하는 LSM-Tree보다 효율적이다.

(2) 자동 균형 유지 (Self-Balancing)

• 트리 깊이가 O(log n)로 유지되므로, 데이터가 많아져도 검색 속도가 크게 느려지지 않는다.
• 모든 리프 노드는 같은 깊이를 유지하여 균형을 잃지 않는다.

(2) 트랜잭션 처리 및 동시성 지원

• B-Tree는 데이터가 한 곳에만 존재하므로 강력한 트랜잭션 격리(Transaction Isolation) 지원한다.
• RDBMS에서 트랜잭션을 구현할 때 주로 사용된다.

(4) 범위 조회(Range Query)에 최적화됨

• 리프 노드가 서로 연결되어 있어, 정렬된 데이터의 범위 검색이 빠르다.

4. B-Tree의 단점

(1) 쓰기 성능이 상대적으로 낮음

• 삽입 및 삭제 시, 기존 페이지를 덮어쓰는 방식이므로 랜덤 쓰기가 발생한다.
• 특히 SSD에서는 랜덤 쓰기가 성능 저하를 유발할 수 있다.
• 페이지에서 일부 데이터만 변경해도 전체 페이지를 다시 기록해야 한다.

(2) 쓰기 전 로그(WAL, Write-Ahead Log) 필요

• 트랜잭션을 보장하려면 변경 사항을 WAL에 먼저 기록한 후, B-Tree에 반영해야 한다.
• 이 과정에서 추가적인 디스크 쓰기가 발생하여 쓰기 오버헤드가 증가한다.

(3) 페이지 분할(Split) 및 병합(Merge) 비용 발생

• 삽입 시 노드가 가득 차면 노드를 분할해야 하고, 삭제 시 노드가 비면 병합해야 한다.
• 이러한 작업이 빈번할 경우 성능 저하가 발생할 수 있다.

정리

비교 항목	B-Tree	LSM-Tree
쓰기 성능	랜덤 쓰기 발생, 기존 페이지 덮어쓰기	순차적 쓰기(Append-Only)
읽기 성능	빠름 (O(log n))	여러 SS테이블을 검색해야 하므로 상대적으로 느림
범위 조회	빠름 (리프 노드 간 연결)	일부 최적화 가능하지만 상대적으로 느림
컴팩션(Compaction) 영향	없음	컴팩션 시 성능 저하 가능(백그라운드에서 실행)
쓰기 증폭(Write Amplification)	높음 (같은 페이지를 여러 번 덮어씀)	낮음 (순차적 데이터 병합)
트랜잭션 지원	강력한 트랜잭션 격리 제공	키가 여러 세그먼트에 존재할 수 있어 상대적으로 불리
SSD와의 호환성	랜덤 쓰기 발생, SSD에서 비효율적일 수 있음	순차 쓰기로 SSD와 궁합이 좋음
저장 공간 효율성	페이지 파편화 가능	주기적인 파편화 제거로 저장 공간 절약
일반적인 사용 사례	관계형 데이터베이스(RDBMS), 파일 시스템	NoSQL, 로그 저장소, 대용량 데이터 처리

참고: 데이터 중심 애플리케이션 설계 3장