Editing B* 트리

현대 RDBMS에서 가장 많이 사용되는 인덱스 구조로, B 트리의 개선 버전

== 특징 ==

* 노드의 약 2/3이상이 채워지는 B트리
* 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮김
* 삽입/ 삭제 시 발생하는 노드 분리를 줄이려고 고안됨

== 구성 ==

* Root 노드
* Branch 노드
* Leaf 노드

== 규칙 ==
'''차수가 m인 B*트리는 다음 조건을 만족하는 B 트리이다'''

* 공집합이거나 높이가 1이상인 m원 탐색 트리이다.
* Root 노드는 2개 이상 2(2m-2)/3+1 개 이하의 자식노드를 갖는다. 
* 내부노드는 최소한 (2m-1)/3개의 자식노드 를 갖다. 
* 모든 Leaf 노드는 동일한 레벨에 놓인다.
* 포인터가 k개인 Leaf가 아닌 노드는 k-1개의 키를 갖는다. (Root 노드 포함)

== 같이 보기 ==

* [[B 트리]]
* [[B+ 트리]]