변형 B-트리의 종류

B-트리를 변형한 변형 B-트리라는 자료구조가 몇 존재한다.

공통점

B-트리에서 파생되어 기본적인 B-트리의 구조인 분할/병합을 통한 균형 유지, 탐색, 삭제등의 로직은 같다.

차이점

B-트리를 구현하는 과정에서 동시성 제어 방식과 디스크 페이지 구조, 형제 노드 사이의 링크, 유지보수 프로세스 등은 구현 방식의 차이가 존재할 수 있다.

쓰기 시 복사형(copy-on-write) B-트리

B-트리와 유사한 구조이지만 노드를 수정할 수 없고 인플레이스 업데이트를 지원하지 않는다. 그 대신 페이지를 복사하고 업데이트한 뒤에 새로운 위치에 저장한다.

사용 이유

데이터 무결성을 보장하기 위해 사용된 변형 B-트리로 기존 방식인 래치 메커니즘이 복잡하여 고안된 방식이다.

주요 로직

• 평행 트리 계층 구조로 변경 전 트리의 구조와 변경 후 트리의 구조가 같이 존재한다.
• 쓰기와 동시 실행하는 읽기는 Old Tree Root를 통해 읽을 수 있다.
• 쓰기와 동시 실행하는 또 다른 쓰기는 기존의 쓰기가 완료될 때까지 대기 후 실행한다.
• 새로운 쓰기가 실행되면 새로운 Tree Root를 생성한다.
• 위 그림은 쓰기가 완료되고 기존의 루트와 변경된 노드가 삭제되는 과정을 나타내는 그림이다.

모든 수정이 완료된 후 최상위 포인터를 갱신하여 읽기 작업은 항상 완전한 상태에서 읽을 수 있다.

메모리 사용량의 문제

평행 트리 계층 구조로 메모리를 많이 사용하지만 트리의 높이가 낮기 때문에 메모리 사용량이 크다는 단점보단 복사 방식의 장점이 더 부각된다.

지연형(lazy) B-트리

동일한 노드에 대한 연속된 쓰기 작업의 I/O 요청 횟수를 줄이기 위해 수정 내용을 버퍼에 저장한다.

사용 이유

더 가볍고 동시성 지원이 쉬운 인메모리 자료 구조를 사용하여 배치 단위로 쓰기 작업을 실시하여 업데이트 비용을 낮추기 위해 고안되었습니다.

주요 로직

MongoDB의 기본 스토리지 엔진인 WiredTiger기준으로 설명합니다.

• 로우 스토어 B-트리를 인메모리와 디스크의 페이지에 각각 다른 방식으로 저장된다.
• 각 페이지는 업데이트 버퍼를 가지고 있습니다.
• 쓰기 작업 시 업데이트 버퍼에 먼저 저장됩니다.
• 읽기 작업 시 버퍼된 내용과 원본 디스크 페이지와 합쳐 가장 최신 데이터를 반환합니다.
• 페이지를 플러시할 경우 업데이트 버퍼의 내용과 페이지 내용을 합치고 디스크에 존재하는 기존 페이지를 덮어씌웁니다.
• 합쳤을 때 허용된 페이지 크기보다 크다면 여러 페이지로 분할합니다.
• 쓰기 작업 시 다른 쓰기 작업이 완료될 때까지 기다리지 않고 바로 작업을 시작합니다.
• 백그라운드에서 페이지 업데이트와 구조 변경을 처리합니다.

지연 적응형 트리

• 각 노드마다 업데이트 버퍼를 유지하지 않고 노드를 서브트리 단위로 그룹화합니다.
• 모든 변경 사항은 상위 레벨 버퍼에서 하위 레벨 버퍼로 전파됩니다.
• 루트 노드부터 시작하여 버퍼가 가득찰 경우 계단식으로 하위 레벨의 버퍼로 넘겨지며 리프 노드 레벨까지 도달하면 배치 단위로 한번에 작업을 수행합니다.

FD-트리

작은 크기의 B-트리를 버퍼로 사용하고 버퍼가 가득 차면 그 내용을 불변 형태로 기록한다. 수정 사항은 상위 레벨에서 하위 레벨로 전파된다.

사용 이유

여러 소규모 램덤 쓰기를 피하고 더 큰 규모로 쓰기 작업을 수행하게 해준다.

주요 로직

• 기존 B-트리와 작업 내용을 저장하는 FD-트리를 사용한다.
• 추가 전용 스토리지와 병합 프로세스를 사용하여 여러 노드에 대한 업데이트 작업을 그룹화한다.
• 쓰기 작업시 대상 노드를 탐색하지 않고 작업 내용을 추가시켜준다.
• 작은 가변 헤드 트리와 여러 개의 정렬된 불변 배열로 구성한다.
• 헤드 트리가 가득찰 경우 저장된 내용을 불변 배열로 옮깁니다.
• 상위 레벨의 노드에서 탐색을 통해 다음 위치를 찾아 하위 레벨로 내려가 점점 범위를 좁힙니다.
• FD-트리는 부분적 케스케이딩을 사용해 레벨 간 포인터를 유지한다.

부분적 캐스케이딩

상위 레벨과 하위 레벨의 값을 연결하기에는 값의 차이가 존재하여 탐색의 복잡성이 높아진다.

하위 레벨의 값을 일부 상위 레벨로 올려 탐색을 더욱 단순하게 만들 수 있다.

따라서 위와 같은 방식으로 배열간의 지름길을 통하여 범위 탐색을 더욱 단순하게 만들 수 있다.

지연형(lazy) B-트리와의 차이점

지연형 B-트리의 경우 B-트리에서 해당 변경사항이 적용될 노드를 찾아 해당 버퍼에 저장하지만 FD-트리의 경우 변경사항이 저장될 새로운 자료구조를 만들어 B-트리에 직접 접근할 필요가 없어진다. 또한 변경사항이 정렬되어있을 경우 램덤 접근이 아닌 순차 접근으로 디스크 IO가 더욱 빨라지게 된다.

위 글은 데이터베이스 인터널스 책을 기반으로 작성되었습니다.