1973년 Knuth는 삽입 시의 재분개 개념에 분할에 대한 새로운 개념을 포함하도록 확장하였다. 그는 이 트리를 B* 트리(tree)라 명명했다.
재분배를 통해 분할을 연기하는 시스템을 생각해보자. 루트(root) 페이지 이외의 페이지를 고려한다면 그 페이지가 분할될 때는 이것이 적어도 꽉 찬 형제(sibling)를 하나 가진다는 것을 알고 있다. 이것은 기존에 한 페이지를 둘로 나누는 방법보다 둘을 셋으로 나누는 방법의 가능성을 제시한다.
두 페이지를 셋으로 분할하는 방법은 분할된 페이지가 반으로 차기보다는 2 / 3 정도로 찬다는 중요한 측면을 가진다. B* 트리는 다음과 같은 성질을 가진다.
1. 각 페이지는 최대 m 개의 자손을 가진다.
2. 루트 노드와 리프(leaf) 노드를 제외한 각 페이지는 적어도 (2m - 1) / 3 개의 자손을 가진다.
3. 루트 노드는 적어도 두 개의 자손(decendant) 노드를 가진다. (리프 노드가 아닐 경우)
4. 모든 리프 노드는 동일한 레벨에 나타난다.
위에서 기존 B-트리의 정의와 성질에서 특징적으로 달라진 것은 규칙 2이다. 즉, 하나의 B* 트리는 최소 (2m - 1) / 3 개의 키를 가진 페이지들로 이루어진다. 이 새로운 성질은 삭제와 재분배의 절차에 영향을 끼친다.
B* 트리 절차들을 구현하기 위해, 정의에 의해 형제를 결코 갖지 않는 루트를 분할하는 문제를 반드시 다루어야 한다. 형제가 없다면 둘을 셋으로 분할이 불가능하다. Knuth는 루트 페이지의 경우 다른 페이지보다 큰 크기로 확장될 수 있도록 하고, 분할될 때는 2 / 3만큼 찬 두 개의 페이지를 생성할 수 있는 방법을 제안하였다. 이 제안은 루트 아래에 있는 모든 페이지들이 B* 트리의 특성을 가진다는 것을 보장할 수 있다는 장점이 있다. 하지만 다른 페이지들보다 큰 페이지를 다룰 수 있는 절차를 필요로 한다. 다른 해결책으로, 루트의 분할을 통상적인 하나에서 둘로 분할하는 방식이 있다. 이 방법은 특별한 페이지 핸들링을 하지 않아도 되지만, 한 페이지의 최소 키 개수에 민감할 수 밖에 없는 삭제, 재분배와 같은 프로시저를 복잡하게 한다. 이런 프로시저는, 루트의 자식 페이지들이 다만 1 / 2만 차있다는 것을 인식할 수 있어야 하기 때문이다.
Reference
Micheal J. Kolf, Bill Zoellick, Greg Riccardi, File Structure, Addision Wesley
재분배를 통해 분할을 연기하는 시스템을 생각해보자. 루트(root) 페이지 이외의 페이지를 고려한다면 그 페이지가 분할될 때는 이것이 적어도 꽉 찬 형제(sibling)를 하나 가진다는 것을 알고 있다. 이것은 기존에 한 페이지를 둘로 나누는 방법보다 둘을 셋으로 나누는 방법의 가능성을 제시한다.
두 페이지를 셋으로 분할하는 방법은 분할된 페이지가 반으로 차기보다는 2 / 3 정도로 찬다는 중요한 측면을 가진다. B* 트리는 다음과 같은 성질을 가진다.
1. 각 페이지는 최대 m 개의 자손을 가진다.
2. 루트 노드와 리프(leaf) 노드를 제외한 각 페이지는 적어도 (2m - 1) / 3 개의 자손을 가진다.
3. 루트 노드는 적어도 두 개의 자손(decendant) 노드를 가진다. (리프 노드가 아닐 경우)
4. 모든 리프 노드는 동일한 레벨에 나타난다.
위에서 기존 B-트리의 정의와 성질에서 특징적으로 달라진 것은 규칙 2이다. 즉, 하나의 B* 트리는 최소 (2m - 1) / 3 개의 키를 가진 페이지들로 이루어진다. 이 새로운 성질은 삭제와 재분배의 절차에 영향을 끼친다.
B* 트리 절차들을 구현하기 위해, 정의에 의해 형제를 결코 갖지 않는 루트를 분할하는 문제를 반드시 다루어야 한다. 형제가 없다면 둘을 셋으로 분할이 불가능하다. Knuth는 루트 페이지의 경우 다른 페이지보다 큰 크기로 확장될 수 있도록 하고, 분할될 때는 2 / 3만큼 찬 두 개의 페이지를 생성할 수 있는 방법을 제안하였다. 이 제안은 루트 아래에 있는 모든 페이지들이 B* 트리의 특성을 가진다는 것을 보장할 수 있다는 장점이 있다. 하지만 다른 페이지들보다 큰 페이지를 다룰 수 있는 절차를 필요로 한다. 다른 해결책으로, 루트의 분할을 통상적인 하나에서 둘로 분할하는 방식이 있다. 이 방법은 특별한 페이지 핸들링을 하지 않아도 되지만, 한 페이지의 최소 키 개수에 민감할 수 밖에 없는 삭제, 재분배와 같은 프로시저를 복잡하게 한다. 이런 프로시저는, 루트의 자식 페이지들이 다만 1 / 2만 차있다는 것을 인식할 수 있어야 하기 때문이다.
Reference
Micheal J. Kolf, Bill Zoellick, Greg Riccardi, File Structure, Addision Wesley