[File System] ::B* tree, B+ tree

B tree의 문제점은 구조를 유지하기 위해 추가적으로 연산을 해야한다는 것 (삽입시 분열하거나,, 삭제할때 재분배,합병하거나...)

Knuth에 의해 제안된 B* 트리는 이러한 문제를 보안하기 위해 나왔으며 Btree에서 최소 2/M의 키값을 가져야한다는 점을 2/3의 키값을 가져야한다고 변경한것이다.

특징은 아래와 같다.

1) 리프를 제외한 모든 노드는 m개의 서브트리 이상을 가질 수 없다

2) 루트와 리프를 제외한 모든 노드는 적어도 [(2m-2)/3]+1개의 서브트리를 갖는다.

3) 루트는 리프가 아닌 이상 최소 2개, 적어도 2[(2m-2)/3]+1개의 서브트리를 갖는다.

4) 모든 리프는 같은 레벨에 있다.

5) 리프가 아닌 노드의 키 값의 수는 그 노드의 서브트리수보다 하나 적다

6) 각 리프노드는 최소[ (2m-2)/3]개, 최대 m-1개의 키 값을 갖는다.

삽입

원래는 분열을 하지 않았는가? 분열을 하지 말고 인접한 형제 노드에게 재 분배한다. 만약에 인접한 친구까지 가득차있으면 이들을 분열해 3개의 노드로 만든다.

예를들어보자, m=5 인 b* 트리이다.

여기에서 24를 입력하려고 하면 오버플로가 발생한다.

이때 형제 노드에게 중간값을 부모노드로 이동하는 재분배 작업을 실행

만약 위아래 둘다 오버플로가 발생하는 상황이면 어떻게 해야할까?

그럴때는 아래와 같이 3개의 노드로 나눈다.

1) 처음노드에는 최소로 가져야하는 키 값인 (2m-2)/3 인 2개가 들어간다. ,... 그리고서 적절하게 분배

삭제

삭제는 원래 B-tree와 동일하나 세개의 노드를 두개의 노드로 합병하는것이다 다르다.

최악의 경우 노드와 두 자식노드가 한개의 노드로 합병되어 트리의 높이가 낮아지는것

knuth는 B+-Tree 도 제안을 했다. B+트리는 아래 2가지로 구성되어있다.

1) 리프가 아닌 노드로 된 인덱스 세트

2) 리프 노드로만 구성된 순차 세트

- 인덱스 세트에 있는 친구들은 그냥 단순히 경로만 제공하는 목적임 ( 위에서 보면 인덱스 세트에 있는 모든 값들이 다시 순차 세트에 나타나있는것을 볼 수 있음!! )

- 리프노드는 데이터 파일의 순차 세트를 나타내며 모두 리스트로 연결되어 있다.

특징은 다음과 같다

1. 루트는 0,2 또는 [m/2]에서 m개 사이의 서브트리를 갖는다.

2. 루트와 리프를 제외한 모든 노드는 최소 [m/2]개 , 최대 m개의 서브트리를 갖는다.

3. 모든 리프는 같은 레벨에 있따.

4. 리프가 아닌 노드에 있는 키값의 수는 그 노드의 서브트리수보다 하나적다.

5. 리프 노드는 데이터파일의 순차 세트를 나타내며 모두 리스트로 연결되어있다.

삽입

예를들어보자 아래와 같은 트리에 값 80을 넣고 싶다.

그럼 아래와 같이 70,80,100 중 중간 값인 80을 위로 올리고 노드 [70|100]은 분열된다.

 

삭제

예를 들어 아래의 트리에서 100을 삭제한다고 해보자.

인덱스 셋에 있는 100은 삭제하지 않는다. 그 이유는 인덱스 셋에 있는 100은 70이 들어있는 노드의 키값을 탐색하는데 필요한 분기 키값으로 사용될 수 있기때문

위의 상황은 간단했다. 그렇다면 다시 원래대로 돌아와서 110을 삭제할땐 어떨까?

결과는 아래와 같다. 노드의 키값은 변했지만 구조는 변하지 않았다.