이전 장
B 트리
B 트리(Balanced Tree)는 고정 크기(4kb)의 블록 또는 페이지로 구성되어 있다. 트리라는 단어처럼 B트리는 맨 위의 루트 페이지와 루트 페이지가 참조하는 여러 리프 페이지(Leaf Page)로 구성되어 있다. 각 페이지는 하위 페이지들의 주소(ref)를 가지고 있다. 하위 페이지를 참조하는 개수를 분기계수라고 한다.
LSM트리와의 공통점과 차이점
공통점
•
LSM 트리와 마찬가지로 키-값 쌍의 데이터로 이루어져 있으며 항상 정렬된 채 유지된다.
차이점
•
LSM은 데이터를 가변적인 세그먼트로 나누고, 가장 낮은 레벨의 세그먼트부터 순차쓰기를 한다.
•
B트리는 고정크기의 페이지로 구성되어 있다. 쓰기를 할 때 데이터를 새로 추가하는 게 아니라 기존 데이터를 덮어쓰는 방식을 사용하기 때문에 하나의 페이지만 사용한다.
왜 balanced tree일까 - 쓰기 과정
B트리는 LSM과 달리 기존 페이지에 키가 존재한다면 그 키를 덮어쓴다. 만약 키가 존재하지 않는 경우 페이지에 새 키를 추가한다. 이때 B트리는 고정 크기의 페이지이므로 페이지 공간이 부족하면 한 페이지를 여유공간이 있는 두 페이지로 새로 만들어 분할한다. 그리고 기존 페이지에는 새로 생긴 두 페이지에 대한 ref를 추가한다.
이렇게 B트리는 고정 크기의 페이지들이 균형 있게 유지되기 때문에 Balanced Tree라는 이름을 가진다.
B트리의 쓰기 위험성
B트리의 쓰기 과정에는 두 가지 위험이 있다.
1.
고아 페이지의 발생
페이지를 분할하다가 기존 페이지에 새로 생긴 두 페이지의 ref를 기록하던 중 장애가 생기면 새 하위 페이지들은 부모 페이지가 없는 상태가 된다. 이를 위해 쓰기 전에는 ‘쓰기 전 로그(write-ahead log, WAL)’라는 복원 파일을 생성한다.
2.
다중스레드 접근에 대비한 동시성 제어
B트리는 덮어쓰기를 하기때문에 다중스레드에서 데이터에 동시에 접근했을 때 데이터의 일관성이 깨질 수 있다. 이를 대비해 B트리는 쓰기를 할 때 래치(Latch)라는 락을 걸어둔다.
LSM트리와의 비교
쓰기는 LSM이 빠르고 읽기는 B트리가 빠르다.
B트리는 ‘쓰기 전 로그'를 작성하고, 페이지를 분할하고 상위 페이지에 주소를 기록하는 등 쓰기 과정에서 오버헤드가 발생한다(최소 두번의 쓰기 발생). 반면 LSM은 멤테이블에 새로 추가하는 식이다. 때문에 LSM은 B트리보다 쓰기 처리량이 높다. 또한, B트리는 페이지 분할 과정에서 페이지에 여유 공간을 만들기 때문에 낭비되는 공간이 생기지만 LSM은 필요한 만큼만 추가하기 때문에 공간 활용도가 좋다(압축률이 더 좋다).
LSM이 읽기가 느린 이유는 조회 시 bloom filter도 조회해야 하고, 값이 없다고 판단되면 다음 레벨의 세그먼트로 거슬러 올라가는 등 확인해야할 데이터가 많기 때문이다. 반면 B트리는 쓰기가 느린 대신 중복되는 데이터가 없다. 각 키가 색인의 한 곳에만 존재한다.
references
•
책 데이터중심어플리케이션설계 3장
