-
B 트리 개요
검색 트리가 방대하면 검색 트리를 메모리에 모두 올려두고 사용할 수 없게 되어 검색 트리가 디스크에 있는 상태에서 작업을 해야 한다. 이런 경우에 CPU 작업 효율성보다 디스크 접근 횟수가 효율을 좌우하게 된다.
B 트리는 디스크 환경에서 사용하기 적합한 외부 다진 검색 트리로 B 트리의 한 노드에는 최대 k개까지의 키가 크기 순으로 저장되어 있다.
※ 검색 트리가 디스크에 있는 상태로 사용되면 이를 외부 검색 트리라고 한다.
B 트리에 k개의 키가 존재하는 경우 k + 1 개의 자식을 가지게 된다.
이때, 주어진 키를 key 0 ~ key k - 1로 나타내고 자식 서브 트리를 각각 T 0 ~ T k 로 나타내면 다음의 관계가 성립한다.
T 0 의 모든 노드의 값 < key 0 < T 1의 모든 노드의 값 < key 1 < ... < key k - 1 < T k 의 모든 노드의 값
쉽게 배우는 알고리즘 B 트리 그림 5-17 B 트리는 균형 잡힌 다진 검색 트리로 다음의 성질을 만족한다.
- 루트를 제외한 모든 노드는 k / 2 ~ k 개의 키를 갖는다.
- 모든 리프 노드는 같은 깊이를 가진다.
※ B 트리는 최대 효율을 위해 디스크의 블록의 크기에 따라 가질 수 있는 최대 키의 개수가 정해진다.
디스크의 한 블록의 크기가 4,096 byte 일 때, 키의 크기가 16 byte 페이지 번호가 4 byte를 차지하는 경우
B 트리가 가질 수 있는 최대 키의 개수는 디스크의 한 블록의 크기 / 키와 페이지 번호를 나타내는데 필요한 크기 이므로
4,096 / (4 + 16 + 4) ≒ 170.6
최대 170개의 키 값을 가질 수 있다.
이상은 책에 동일한 조건에 대해 170개 라는 결과를 가지고 과정을 고민한 결과이나 결과에 의문이 든다.
노드의 구조가 다음과 같다고 가정하자.
대략적인 B 트리 노드 구조 이때, 부모 노드 페이지 번호인 pp와 키가 키 값과 페이지 번호 하나를 가진다고 하면 남는 페이지 번호 p-1을 제외하고 계산하면 다음과 같은 결과가 나오게 된다.
(4,096 - (4 + 4)) / (16 + 4) ≒ 204.4
최대 204개의 키 값을 가질 수 있다.
이 부분은 확인이 필요해 보인다.