B-tree vs Log-Structured Merge-Tree

B-tree vs Log-Structured Merge-Tree

 

데이터베이스에서 일반적으로 많이 사용되는 데이터 구조는 B-Tree와 LSM(Log-Structured Merged-Tree)이다.

B-Tree

B-Tree는 데이터베이스에 널리사용되며, B-Tree 인덱싱 구조를 사용하면 데이터가 고정 크기 페이지 세그먼트로 디스크에 기록된다. 이러한 페이지 세그먼트의 크기느 약4KB (DMBS마다 다를 수 있음) 이며 키별로 정렬된 Key-Value를 가지고 있다. 단일 B-Tree노드는 페이지 범위에 대한 참조가 있는 배열과 같다. 배열의 최대 참조 수를 “branching factor” 한다. 각 페이지 범위는 다른 페이지 범위를 참조하는 또 다른 B-Tree 노드이다. 결국 리프수준에서 단일 페이지를 찾을 수 있다.

B-Tree는 페이지 참조가 메모리가 아닌 디스크에 저장된다는 점을 제외하면 저수준 프로그래밍 언어의 포인터와 유사하다. B-Tree에서 삽입 및 삭제가 발생하면 branching factor를 충족하기 위해(밸런스를 맞추기 위해) 노드를 두 개의 하위 트리로 분할 할 수 있다. 이 때 데이터베이스가 충돌하는 위험이 발생할 수 있다. 데이터베이스가 충돌하는 시나리오를 완화하기 위해 B-Tree 구현은 모든 단일 원자 데이터베이스 트랜잭션을 기록하는 WAL (Write-Ahead Log)를 작성하여 기록을 추적한다.  WAL은 B-Tree가 손상된 경우 B-Tree의 상태를 복원 하는데 사용된다.

 

Algorithm	Average	Worst case
Space	O(n)	O(n)
Search	O(log n)	O(log n)
Insert	O(log n)	O(log n)
Delete	O(log n)	O(log n)

 

 

 

 

LSM Tree

LSM Tree는 Bitcask, MongoDB, Bigtable, Cassandra, InfluxDB및 SQLite4와 같은 최신 관계형 및 비관계형 데이터베이스에서 사용하고 있는 인기있는 데이터 구조이다. LSM Tree는 각각의 기본 저장 매체에 최적화된 두 개이상의 개별 구조로 데이터를 유지한다. 메모리에는 실제 디스크의 데이터 값을 포함하는 바이트 오프셋에 대한 참조 정보를 Key-Value  형태로 해시 테이블 (또는 해시 인덱스)로 관리한다.

실제로 사용되는 대부분의  LSM Tree는 여러 수준을 사용한다. 레벨 0은 주로 메모리에 보관되며 트리를 사용하여 표시 될 수 있다. 디스크 데이터는 정렬된 상태로 실행될 수 있도록 구성되며 각 실행에는 인덱스 키별로 정렬된 데이터가 포함된다. 실행은 디스크에서 단일 파일로 표시되거나 키 범위가 겹치지 않는 파일 모음으로 표시 될 수 있다. 관련 값을 얻기 위해 특정 키에 대한 쿼리를 수행하려면 레벨0 트리에서 검색하고 긱 실행을 수행해야한다.

 

Algorithm	Average	Worst case
Insert	O(1)	O(1)
Find-min	O(N)	O(N)
Delete-min	O(N)	O(N)

 

 

 

[참고자료]

·       B-Tree : https://en.wikipedia.org/wiki/B-tree

·       Log-structured merge-tree : https://en.wikipedia.org/wiki/Log-structured_merge-tree

 

 

 

2021-03-17 / Sungwook Kang / http://sungwookkang.com

 

B-Tree, LSM Tree, Data Structure, Log-Structured-Merged-Tree, Database Index, 자료구조, 데이터스트럭처, 데이터인덱스