B* 트리
From IT Wiki
현대 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 노드 포함)
