B-Tree 검색트리가 방대하면 모두 메모리에 올려놓고 사용할 수 없다. 따라서 디스크에 넣어둔 상태로 작업해야 한다. 이는, 외부 검색트리에 해당한다. 외부검색트리일 땐 CPU보다는 디스크 접근 횟수가 효율을 좌우한다. 그리고 트리의 높이를 최소화하는 것이 유리하다. 이는 분기수를 늘리면 다진 검색트리가 되고 높이도 줄어든다. 10억 개의 키값을 가진 이진검색트리는 높이가 30이다. 256개의 분기를 가진 트리는 5의 높이를 갖는다. 이러한 분기는 블럭의 크기를 고려하여 결정한다. B-Tree는 결국 트리 균형을 유지하여 최악의 경우 디스크 접근 횟수를 줄인다. 또한, 다진검색트리로써 다음과 같은 특성을 갖는다. 루트노드를 제외한 모든 노드에서 [k/2]~k개의 키를 갖는다. 모든 리프 노드는 똑같은 ..
