B* 트리

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

특징[편집]

  • 노드의 약 2/3이상이 채워지는 B트리
  • 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮김
  • 삽입/ 삭제 시 발생하는 노드 분리를 줄이려고 고안됨
  • 데이터가 기본적으로 정렬되어 저장됨
  • Max/Min의 효율적 처리 가능

구성[편집]

  • Root 노드
  • Branch 노드
  • Leaf 노드

규칙[편집]

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

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

같이 보기[편집]