B-트리

이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.

✅사용

디스크의 접근 단위는 블록(페이지) (블럭단위로 파일을 입출력한다.)
디스크에 한 번 접근하는 시간은 수십만 명령어의 처리시간과 맞먹는다.
- B-Tree도 자식 노드를 접근할 때는 참조 포인터로 접근을 하지만, 하나의 노드가 가지는 데이터 개수가 많아질수록 포인터 개수는 확연히 줄어 들고, 트리 내에서 다루는 데이터가 많아질수록 이러한 차이는 커진다.
검색트리가 디스크에 저장되어 있다면 트리의 높이를 최소화하는 것이 유리하다.
B-트리는 다진검색트리가 균형을 유지하도록 하여 최악의 경우 디스크 접근 횟수를 줄인 것이다.

✅구조

k차 트리일 때,루트를 제외한 모든 노드는 [k/2] ~ k개의 키를 갖는다.
모든 리프 노드는 같은 깊이를 가진다. (균형트리)
노드의 key들은 항상 정렬된 상태이다.
노드의 key의 수가 k개라면, 자식 node의 수는 k+1개이다.

b-트리 삽입연산

예시) 5차 B-트리일 경우

한 노드에 2~5개의 키만 들어갈 수 있다.

btreeInsert(t,x)
{
	x를 삽입할 리프토느 r을 찾는다.
    x를 r에 삽입한다;
    if(r에 오버플로우 발생) then clearOverflow(r);
}
clearOverflow(r)
{
	if(r의 형제노드 중 여유가 있는 노드가 있음) then {r의 남는 키를 넘긴다};
    else{
    	r을 둘로 분할하고 가운데 키를 부모 노드로 넘긴다;
        if(부모노드 p에 오버플로우 발생)then clearOverflow(p);
    }
}

1️⃣리프노드에 공간이 있을때 → 리프노드에 넣어준다.

2️⃣ 리프노드에 공간이 없을 경우, 부모노드에는 공간이 있을 경우

→ 부모노드에 중간값인 40을 올려주고 노드를 2개로 분할한다.

3️⃣ 리프노드에 공간이 없을 경우, 부모노드에도 공간이 없을 경우

→부모노드에 중간값인 31을 올려주고 리프노드를 2개로 분할한다.

→오버플로우가 부모노드에 발생한다.

→ 부모노드의 중간값 31을 올려주고 부모노드를 2개로 분할한다.

b-트리 삭제연산

btreeDelete(t,x,v)
//x : 삭제하고자하는키
//v : x를 갖고있는노드
{
	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);
    }
}

1️⃣ 삭제할 key가 리프노드에 있다 && 리프노드의 갯수가 여유있는 경우 ([k/2]보다 많은 경우)

2️⃣ 삭제할 key의 노드에 여유가 없는 경우 but 형제노드에 여유가 있는 경우

- 삭제할 키를 리프노드로 이동시키기 위해 리프노드에 있는 키 중에서 삭제할 키의 직후원소와 자리를 교환한다.

- 리프노드에서 삭제할 키를 삭제한다.

- 언더플로우 발생시 형제노드의 키를 재분배 받는다.

3️⃣ 삭제할 key의 노드에 여유가 없는 경우 and 형제노드에 여유가 없는 경우

- 삭제한 키의 노드(r)을 형제노드와 합병한다.