12-3. B*, B+ 트리

03. B*, B+ 트리

B*트리의 정의

- 노드의 약 2/3이상이 채워지는 B트리

- 노드가 꽉 차면 분리하지 않고,키와 포인터를 재배치하여 다른 형제 노드로 옮김

- 삽입/삭제 시 발생하는 노드 분리를 줄이려고 고안됨

 

B*트리의 정의

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

① 공집합이거나 높이가 1이상인 m원 탐색 트리이다.

② 루트 노드는 2개 이상 2(2m-2)/3+1 개 이하의 자식노드 를 갖는다.

③ 내부노드는 최소한 (2m-1)/3개의 자식노드 를 갖는다.

④ 모든 잎노드는 동일한 레벨에 놓인다.

⑤ 포인터가 k개인 잎이 아닌 노드는 k-1개의 키를 갖는다.(루트노드 포함)

 

 

B+트리의 정의

- 탐색 트리로 구성하면 매우 빠르게 탐색할 수 있지만,전체 데이터를 차례로 처리하기는 불편함

    → 매번 왼쪽인지 오른쪽인지 비교해가면서 다음 노드를 찾아가면서 처리해야 함

- B+ 트리는 인덱스된 순차 파일을 구성하는데 사용됨

- B트리와 같이 각 노드의 키가 적어도 1/2이 채워져야 하는 점은 같음

- 잎노드를 순차적으로 연결하는 포인터 집합이 있다는 점에서 다름

    → 잎노드의 마지막 포인터를 다음 키값을 갖는 노드를 가리킴

    → 순차 처리를 할 때는 이 포인터를 이용해서 (키값을 비교하지 않고)차례로 다음 데이터에 접근해서 처리

- 모든 키값이 잎노드에 있고 그 키값에 대응하는 실제 데이터 (파일 내용)에 대한 주소를 잎노드만이 가지고 있음

    → 직접 탐색은 잎노드에 도달해야 종료

 

 

B+ 트리의 노드 삽입

- 잎 노드가 2개의 노드로 분리될 때는 키값 순서에 따라 배치하고 중간 키값은 부모노드에 올려놓음

- 새 노드는 순서에 맞게 잎노드에 삽입함

 

B+ 트리의 노드 삭제

- 키값을 잎노드에서 삭제할 때,트리의 내부노드에서도 삭제할 필요는 없는데,그 키값이 직접 탐색을 위해 쓰이기 때문임