B 트리

페이지 덮어 쓰기와 고장 복구를 위한 WAL 유지 대신 (LMDB 같은) 일부 데이터베이스는 쓰기 시 복사 방식(copy-on-write scheme)을 사용한다. 변경된 페이지는 다른 위치에 기록하고 트리에 상위 페이지의 새로운 버전을 만들어 새로운 위치를 가리키게 한다. 이 접근 방식은 동시성 제어에도 유용하다.

페이지에 전체 키를 저장하는 게 아니라 키를 축약해 쓰면 공간을 절약할 수 있다. 특히 트리 내부 페이지에서 키가 키 범위 사이의 경계 역할을 하는 데 충분한 정보만 제공하면 된다. 페이지 하나에 키를 더 많이 채우면 트리는 더 높은 분기 계수를 얻는다. 그러면 트리 깊이 수준을 낮출 수 있다.

일반적으로 페이지는 디스크 상 어디에나 위치할 수 있다. 키 범위가 가까운 페이지들이 디스크 상에 가까이 있어야 할 필요가 없기 때문이다. 질의가 정렬된 순서로 키 범위의 상당 부분을 스캔해야 한다면 모든 페이지에 대해 디스크 찾기가 필요하기 때문에 페이지 단위 배치는 비효율적이다. 따라서 많은 B 트리 구현에서 리프 페이지를 디스크 상에 연속된 순서로 나타나게끔 트리를 배치하려 시도한다. 하지만 트리가 커지면 순서를 유지하기가 어렵다. 반대로 LSM 트리는 병합하는 과정에서 저장소의 큰 세그먼트를 한 번에 다시 쓰기 때문에 디스크에서 연속된 키를 서로 가깝게 유지하기가 더 쉽다.

트리에 포인터를 추가한다. 예를 들어 각 리프 페이지가 양쪽 형제 페이지에 대한 참조를 가지면 상위 페이지로 다시 이동하지 않아도 순서대로 키를 스캔할 수 있다.

프랙탈 트리 (fractal tree) 같은 B 트리 변형은 디스크 찾기를 줄이기 위해 로그 구조화 개념을 일부 빌렸다.