[알고리즘] 다진 검색 트리 (B-tree)

다진 검색 트리

B-tree

• 디스크의 접근 단위는 블록(페이지)

• 디스크에 한 번 접근하는 시간은 수십만 명령어의 처리 시간과 맞먹는다

• 검색트리가 디스크에 저장되어 있다면 트리의 높이를 최소화하는 것이 유리하다

• B-트리는 다진검색트리가 균형을 유지하도록 하여 최악의 경우 디스크 접근 횟수를 줄인 것이다

 

B-tree는 균형잡힌 다진검색트리로 다음 성질을 만족한다.

- 루트는 1~k개의 키를 갖는다

- 루트를 제외한 모든 노드는 floor(k/2) ~ k개의 키를 갖는다.

- 모든 리프 노드는 같은 깊이를 갖는다.

- 키가 하나도 없는 트리로 B-tree이다.

 

B-tree 노드 삽입 알고리즘

# t : 트리의 루트 노드 
# x : 삽입하고자 하는 키
BTreeInsert(t, x) { 
	x를 삽입할 리프 노드 r을 찾는다; 
	x를 r에 삽입한다; 
	if (r에 오버플로우 발생) then clearOverflow(r); 
} 
clearOverflow(r) 
{  
	if (r의 형제 노드 중 여유가 있는 노드가 있음) then {r의 남는 키를 넘긴다}; 
	else { 
		r을 둘로 분할하고 가운데 키(ceil(k/2)+1)를 부모 노드로 넘긴다; 
		if (부모 노드 p에 오버플로우 발생) then clearOverflow(p); 
	} 
}

[예제] 빈 트리에 다음 키들을 삽입하는 과정을 적으시오.

k=3, k=4, 80, 90, 95, 55, 50,60,70,15, 25, 35, 30,40,10,20,7,8,3,4,5,6,2,1,

B-tree 노드 삭제 알고리즘

# t : 트리의 루트 노드 
# x : 삭제하고자 하는 키
# v : x를 갖고 있는 노드
BTreeDelete(t, x, v) 
{ 
	if (v가 리프 노드 아님) then { 
		x의 직후원소  y를 가진 리프 노드를 찾는다; 
		x와  y를 맞바꾼다; 
	} 
	리프 노드에서 x를 제거하고 이 리프 노드를  r이라 한다; 
	if (r에서 언더플로우 발생) then clearUnderflow(r); 
} 
clearUnderflow(r) 
{  
	if ( r의 형제 노드 중 키를 하나 내놓을 수 있는 여분을 가진 노드가 있음) 
		then { r이 키를 넘겨받는다;} 
	else { 
	r의 형제 노드와 r을 합병한다; 
	if (부모 노드  p에 언더플로우 발생) then clearUnderflow(p); 
	} 
}

[예제] 다음 B-tree (k=3) 에서 다음 키들을 차례로 삭제 하는 과정을 적으시오. 6, 19, 4, 10, 16, 25

※ B-tree의 각노드는 적어도  k/2개의 키를 가지도록 되어 있다. 노드당 최소키수를 2k/3나 3k/4으로 정한다면, 트리가 더욱 통통하고 납작해질 텐데, 아쉽지 않은가? 삽입삭제 알고리즘과 연관지어, 최소키 수를 k/2로 정한 이유가 무엇일까?

 

※ 균형 트리의 깊이와 노드 수

증명 설명

2진 트리	깊이	1	2	3	h
	노드 수	1	1+2	1+2^1+2^2	(2^h - 1) / (2-1)
3진 트리	깊이	1	2	3	h
	노드 수	1	1+3	1+3^1+3^2	(3^h - 1) / (3-1)
4진 트리	깊이	1	2	3	h
	노드 수	1	1+4	1+3^1+3^2	(4^h - 1) / (4-1)
t진 트리	깊이	1	2	3	h
	노드 수	1	1+t	1+t^1+t^2	(t^h - 1) / (t-1)

 

최소 키를 가진(홀쭉한) B-tree의 예

한 노드의 키 수가 t-1이고 높이가 3인 위 B-Tree의 전체 키의 수

= T.root의 키 수 + T.root의 각 서브트리의 노드 수 * 한 노드의 키의 수

= 1 + 2 * ((t^3 - 1) / (t-1)) * (t - 1)

= 2t^h - 1

 

다시 위 Theorem에서 

등식(=)의 경우, 가장 B-tree가 홀쭉한 경우의 h(좌항)와 우항이 같다는 의미이며

부등식(<)의 경우, 평범한 B-tree의 h는 우항보다 작다는 의미이다.

B-트리가 가장 홀쭉한 경우를 생각하고 그 때의 노드 수보다는 일반적으로 많다(n)는 의미이다.

 

 

 

자료참조 - 쉽게 배우는 알고리즘 · 관계 중심의 사고법 / 문병로