B* Tree 썸네일형 리스트형 B* Tree 1973년 Knuth는 삽입 시의 재분개 개념에 분할에 대한 새로운 개념을 포함하도록 확장하였다. 그는 이 트리를 B* 트리(tree)라 명명했다. 재분배를 통해 분할을 연기하는 시스템을 생각해보자. 루트(root) 페이지 이외의 페이지를 고려한다면 그 페이지가 분할될 때는 이것이 적어도 꽉 찬 형제(sibling)를 하나 가진다는 것을 알고 있다. 이것은 기존에 한 페이지를 둘로 나누는 방법보다 둘을 셋으로 나누는 방법의 가능성을 제시한다. 두 페이지를 셋으로 분할하는 방법은 분할된 페이지가 반으로 차기보다는 2 / 3 정도로 찬다는 중요한 측면을 가진다. B* 트리는 다음과 같은 성질을 가진다. 1. 각 페이지는 최대 m 개의 자손을 가진다. 2. 루트 노드와 리프(leaf) 노드를 제외한 각 페이지.. 더보기 이전 1 다음