[자료구조] 4-11. B+트리와 B*트리, 2-3-4 트리

B+트리

B+트리는 기존의 B트리에서 확장된 버전이라고 볼 수 있다. 다음과 같은 특성을 가지고 있다:

1. 모든 key와 value를 leaf 노드에 가지고 있다.

2. 모든 leaf 노드가 연결리스트로 이어져 있다.

3. 내부노드는 데이터 참조를 위한 인덱스 역할만 한다.

이러한 특성으로 검색, 삽입, 삭제 모두 빠르게 수행할 수 있다.

대용량 데이터베이스에서의 인덱싱에 사용된다.

 

 

B+트리의 삽입

 

삽입과 삭제 과정에서, t = floor(M/2)로 한다.

 

Case 1. 분리되지 않는 경우:

 

기존 B트리처럼 leaf에 key를 추가하면 된다.

 

 

Case 2. key값이 overflow되는 경우:

 

 

1. overflow된 노드의 중간을 기준으로 2개로 나눈다. 이때, 기준이 되는 곳은 나눈 노드의 오른쪽에 붙인다.

    M이 짝수인 경우, t번째 key를 노드의 중간으로 한다.

    M이 홀수인 경우, t+1번째 key를 노드의 중간으로 한다.

2. 기준이 되는 노드는 key만 부모노드로 올리고, 나뉜 노드들은 이 노드의 자식이 된다.

3. 나눠진 노드의 왼쪽 노드의 포인터를 오른쪽 노드로 한다.

4. 부모 노드가 overflow되는지 확인해주고, overflow된다면 1~3의 과정을 재귀적으로 계속하면 된다.

 

 

 

B+트리의 삭제

 

B+트리에서는 리프 노드에서만 삭제가 가능하다. 삭제되는 노드가 내부 노드(인덱싱용 노드)에 있다면 변경시키면 된다.

 

Case 1. 삭제되는 노드의 key가 노드의 맨 앞이 아니고, 내부 노드(인덱스)에 없을때:

기존 B트리와 동일하다,

 

 

Case 2. 삭제되는 노드의 key가 노드의 맨 앞일때:

 

삭제되는 노드의 key가 노드의 맨 앞이면, 무조건 내부 노드에 있다.

 

이런 경우에는 다음의 과정을 거친다:

1. Leaf노드부터 없앤다. 기존 B트리에서 없애는 것 처럼 없애면 된다. 단, 병합 시에는 부모노드의 key를 가져오는 경우는 생략한다.

리프노드가 병합할 때, 오른쪽 노드의 첫 key가 부모노드이기 때문이다.

 

2. 내부 노드에 있는 key를 없애고, 후임자를 위치시킨다.

 

 

 

 

B*트리

 

B트리의 노드 분리를 줄이기 위해서 나온 변형이다. 

 

B*트리에는 다음과 같은 특징들이 있다:

1. 노드의 최대 2t-1에 대해서 2/3 이상의 자료가 저장되어 있다.

2. 노드가 넘칠 경우 양쪽 형제 노드로 key를 재분배한다. 그리고 모든 형제 노드들이 모두 꽉 찬 경우에야 분할 연산을 수행한다.

(<->B트리는 자신의 노드만 꽉 차면 바로 분할했었다)

 

 

2-3 트리와 2-3-4 트리

 

leaf 노드를 제외한 노드가 모두 2,3개 또는 2,3,4개의 자식을 가지는 B트리의 일종. 노드들이 가능한 많은 자식들을 가질수록 효율적이다.