B 트리
최적화 기법
- 페이지에 전체 키를 저장하는 게 아니라 키를 축약해 쓰면 공간을 절약할 수 있다. 특히 트리 내부 페이지에서 키가 키 범위 사이의 경계 역할을 하는 데 충분한 정보만 제공하면 된다. 페이지 하나에 키를 더 많이 채우면 트리는 더 높은 분기 계수를 얻는다. 그러면 트리 깊이 수준을 낮출 수 있다.
- 일반적으로 페이지는 디스크 상 어디에나 위치할 수 있다. 키 범위가 가까운 페이지들이 디스크 상에 가까이 있어야 할 필요가 없기 때문이다. 질의가 정렬된 순서로 키 범위의 상당 부분을 스캔해야 한다면 모든 페이지에 대해 디스크 찾기가 필요하기 때문에 페이지 단위 배치는 비효율적이다. 따라서 많은 B 트리 구현에서 리프 페이지를 디스크 상에 연속된 순서로 나타나게끔 트리를 배치하려 시도한다. 하지만 트리가 커지면 순서를 유지하기가 어렵다. 반대로 LSM 트리는 병합하는 과정에서 저장소의 큰 세그먼트를 한 번에 다시 쓰기 때문에 디스크에서 연속된 키를 서로 가깝게 유지하기가 더 쉽다.
- 트리에 포인터를 추가한다. 예를 들어 각 리프 페이지가 양쪽 형제 페이지에 대한 참조를 가지면 상위 페이지로 다시 이동하지 않아도 순서대로 키를 스캔할 수 있다.
- 프랙탈 트리 (fractal tree) 같은 B 트리 변형은 디스크 찾기를 줄이기 위해 로그 구조화 개념을 일부 빌렸다.
Docs
관련 문서
Plugin Backlinks: 아무 것도 없습니다.