이론공부/화일처리및응용
화일 처리 및 응용 공부 #15 (B*트리)
한반가
2021. 5. 27. 16:10
2021.05.26 - [이론공부/화일처리및응용] - 화일 처리 및 응용 공부 #14 (B-트리)
이전 내용에 이어지는 내용이 몇 있으니 참고하자
기존 B-트리의 문제점
- B트리 구조 유지를 위해 추가적인 유지 연산이 필요함
- 삽입시 노드의 분할, 재분배, 삭제시 노드의 합병, 재분배
- B*- 트리는 B-트리의 성능 개선을 위해 개반된 B트리의 변형
B*-트리
- 공백이거나 높이가 1이상인 m원 탐색트리
- 루트는 리프가 아닌 이상 최소 2개, 최대 2[(2m-2)/3] +1(소수점 내림) 개의 서브트리를 가짐
- 루트와 리프를 제외함 노드는 적어도 (2m-2)/3+1 (소수점 내림)개의 서브트리, (2m-2)/3 개의 키값을 가짐
- 모든 리프는 같은 레벨에 있다.
B 트리와의 차이점
- 삽입으로 인한 노드 분할의 빈도를 축소
- 노드 오버플로시 즉시 분할 하는 대신 아래 과정을 진행
- 오버플로된 키 값과 포인터를 인접한 형제 노드의 여유공간을 이용해 재분배
- 인접 형제 노드가 만원이면 두인접 형제 노드 키값을 3개 노드로 분할
- 한노드가 만원이 되더라도 다른 인접 형제 노드가 만원이 될때 까지 분할은 지연
- 각 내부 노드는 항상 키 값수가 (2m-2)/ 3 이상 키 값을 채운다
같은 노드에서 가질수 있는 최소 키값이 B트리보다 많다.
결과적으로, 같은 키 값 수에 대해 B트리 보다 적은 수의 노드가 필요하게 됨
B*트리 생성
B*트리 삽입
노드 분할에 경우 q 노드 r노드 s 노드 전부를 합쳐서 오름차순으로 나눈후 2/3 부근에 있는 값을 루트로 놓고 다시 분할
B*트리에서 삭제
- B트리에서 삭제와 비슷함, 키 값 삭제로 최소 키 값 수가 유지되지 않으면,
- 형제 노드로 부터 재분배 받도록 시도,
- 형제 노드에 여유 키 값이 없으면 3개 노드를 2개 노드롤 합병
- 합병으로 인해 트리 높이가 한레벨 낮아 질 수 있음
이전 내용과 함께 다시 봐보자