B Tree / B* Tree / B+ Tree

B Tree(Balanced Tree)

균형트리로서 기존에 자식을 2개만 가질 수 있던 Binary tree를 확장하여 더 많은 자식을 가질 수 있는것

기존의 binary tree의 경우 추가, 검색, 삭제등에 O(NlogN)의 시간복잡도를 보여주었고

좌우 균형이 맞지않는 최악의 경우 O(N*N)의 시간복잡도를 가지게 된다.

B-Tree란 하나의 node에 어러자료가 배치되는 tree 구조이다.

한개의 node에 M개의 자료가 배치되면 M차 B-tree라고 한다.

5차 B-Tree인경우 자식노드가 최대 5개인 것을 의미한다.

B-Tree는 스스로 균형을 맞추는 tree이다. 그래서 최악의 경우에도 O(logN)의 검색성능을 보인다.

또한 B-tree는 하나의 node에 많은 수의 data를 저장할 수 있다.

조건 

1. node의 자료수가 N이라면 자식의 수는 N + 1 이어야 한다.

2. 각 node의 data는 정렬된 상태여야 한다.

3. node의 자료 A의 left subtree는 A보다 작은 값들이고 right subtree는 A보다 큰 값들이어야 한다.

3. Root node는 적어도 2개이상의 자식을 가져야 한다.

4. Root node를 제외한 모든 node는 적어도 M/2개의 자료를 가지고 있어야 한다.

5. 외부 node로 가는 경로의 길이는 모두 같다. // 외부노드는 모두 같은 level에 있다.

6. 입력자료는 중복될 수 없다.

3 Order B-Tree  

각 Node는 최대 2개의 key를 가질 수 있고 최대 3개의 Child를 가질 수 있다.

B* Tree

B-Tree의 각 node는 disk의 block과 같기 때문에 node 하나를 접근하는 것은 disk를 한번 더 접근하는 것을 의미한다.

그러므로 보다 적은 수의 node를 생성하는 것이 색인구조의 성능을 높일 수 있다.

생성되는 node의 수를 줄이기 위해 B-Tree의 변형으로 B* Tree가 나오게 되었다.

B-Tree는 특성을 유지하기 위해 삽입과정에서의 분열과 삭제과정에서의 합병등의 보조 연산이 필요하다.

B* Tree에서는 이러한 보조 연산을 가급적 지연시켜 횟수를 감소시키려 했다.

(B* Tree의 평균 저장공간 사용률은 81%에 도달한다 하더라)

조건

1. Root node를 제외한 모든 node는 2/3이상 채워져야 한다.(B-Tree는 1/2이상)

2. B* Tree는 node의 분열을 줄여서 보조연산을 줄이려 한다. 따라서 node가 가득차면 분열하는 대신 이웃한 형제node로 재배치를 한다.

재배치작업은 부모node + 해당node + 형제node의 key들을 나열한 뒤, 중간 key값을 부모node로 보내고 남은 key들을 반분하여 해당node와

형제 node에 배치하는 행동이다.

3. 한 node가 가득차고 인접node까지 모두 가득찰때까지 분열을 하지 않는다.

삽입

1. B-Tree에서와 같은 방법으로 삽입을 한다.

2. node가 가득차면 이웃한 형제 node를 살펴 빈 자리가 있으면 정렬하여 재배치한다.

3. 인접 node에도 key overflow가 일어나서 더이상 빈 자리가 없을 경우 가득 찬 두 node를 분열하여 2/3정도 채워진 3개의 node로 만든다.

이 과정에서 재배치 동작은 2번 발생한다.(가득찬 두 node를 분열하여 3개의 node로 만들때 첫번째 node와 두번째 node간의 재배치 그리고 

두번째 node와 3번째 node 간의 재배치)

삭제 

B-Tree와 똑같이 삭제 후 key값의 개수가 모자라면 이웃한 형제 node로부터 재배치하고 재배치 할 수 없는 경우 합병한다.

합병할 때는 3개의 node를 2개의 node로 합병한다.

B+ Tree

B-Tree의 변형구조로 index부분과 leaf node로 구성된 순차 data부분으로 이루어 진다.

Index부분의 key값은 leaf에 있는 key값을 직접 찾아가는데 사용하고 모든 key값은 leaf node에 나열된다.

즉, index부분의 key값도 leaf node에 다시 한번 나열된다.

Leaf node는 순차적으로 linked list를 구성하고 있어서 순차적 처리가 가능하다.

삽입

1. B-Tree와 거의 동일하게 이루어진다.

2. Node의 분열이 일어나면 중간 Key값이 부모 node로 올라갈 뿐 아니라 새로 분열된 node에도 포함되어야 한다.

3. 새 node는 leaf node끼리의 linked list에도 삽입되어야 한다.

삭제

1. 재배치와 합병이 필요하지 않을때는 leaf node에서만 삭제된다.

2. Index 부분은 다른 key값을 찾는데 사용될 수 있기 때문에 leaf node의 값이 삭제되어도 삭제하지 않는다.

3. 재배치를 할 경우 index부분의 node의 key값은 변하지만 tree구조는 변하지 않는다.

4. 합병을 할 경우 index부분에서도 key값을 삭제한다.

공통점 

모든 leaf의 depth가 같다.

각 node에는 k/2 ~ k개의 item이 들어있어야 한다.

search가 비슷하다

add시 overflow가 발생하면 split한다.

delete시 underflow가 발생하면 redistribution이나 merge한다.

차이점

B-Tree는 각 node에 data가 저장이 된다.

B+ Tree는 index node와 leaf node가 분리되어서 존재하며 leaf node는 서로 연결되어 있어서 임의접근과 순차접근모두 성능이 우수하다.

B-Tree의 각 node에는 key뿐만 아니라 data도 들어갈 수 있으며 여기서 data는 disk block으로의 pointer가 될 수 있다.

B+ Tree는 각 node에서는 key만 들어가야 한다. 그러므로 B+Tree에서는 data는 오직 leaf에만 존재한다.

B+Tree는  add, delete가 leaf에서만 이루어진다.

B+Tree는 leaf node끼리 linked list로 연결되어 있다.

B tree / B+ Tree

https://potatoggg.tistory.com/174

https://ssup2.github.io/theory_analysis/B_Tree_B+_Tree/

https://wangin9.tistory.com/entry/B-tree-B-tree