[알고리즘] B트리, B+트리

디스크에 접근하는 것은 메인 메모리의 접근에 비해 엄청난 시간이 든다.
디스크에 데이터를 읽고 쓰기 위해서는 블록 단위로 접근을 한다.
이 블록을 보통 소프트웨어에서 페이지 라고 한다.

검색트리가 방대하면 메모리에 모두 올려놓고 사용할 수 없다.
결국 검색트리가 디스크에 있는 상태에서 작업을 해야한다.(cpu가 디스크에 접근을 해야함)
검색트리가 균형을 완벽하게 이루고 있고(각 노드가 자식을 최대한으로 가지고 있고), 또한 분기 수(자식수)가 많을 수록 트리의 레벨은 낮아질 것이고 중앙처리장치가 디스크에 접근해야 하는 부담을 덜어줄 수 있을 것이다.

검색트리가 디스크에 있는 상태로 사용되면 이를 외부검색트리 라고 함
분기(자식노드)의 수가 2개를 넘으면 다진검색트리라고 함
B트리는 디스크 환경에서 사용하기에 적합한 외부 다진검색 트리이다.

B-트리는 다음과 같은 성질(조건)을 만족한다.

 1. 루트를 제외한 모든 노드는 k/2 ~ k 개의 키를 갖는다. k= 각 노드가 가지고있는 키의 갯수
 2. 모든 리프 노드는 같은 깊이를 가진다.
 3. 모든 노드는 자식노드를 가질 시 2개 이상의 자식노드를 갖는다.

4진 검색트리를 예로 삽입/삭제/검색 과정을 살펴본다.

검색

BST와 유사하지만 각 각 노드에서 키의 갯수만큼의 상수시간이 걸린다.

삽입 자식이 4개있는 예제, 각 노드에 키가 3개

모든 트리 검색 후 리프노드에 삽입
삽입 후 오버플로우가 발생한다면 적절히 조절해준다.

(123456을 삽입)

1

12

123

1234

12345 => 오버플로우 발생,
             형제 레벨의 노드에 여유가 있다면 남은 키를 넘김, 없다면 가운데 키를 부모노드로 넘긴다

3
12/45

3 
12/456

(6,7,8 삽입)

3
12 / 4567

3
12 / 45678 = >오버플로우,
                   이웃한 형제레벨에 여유가 있다면 넘긴다, 그렇지 않으면적당히 가운데 키를 부모노드로 넘긴다.

4
123 / 5678

4
123 / 56789 =>오버플로우

5
1234/6789

5
1234/6789 10 =>오버플로우

58
1234/67/9 10

삭제 자식이 5개있는 예제, 각 노드에 키가 4개

1.삭제하려는 값을 검색
2. 리프노드라면 삭제
3. 아니라면 해당 원소의 왼쪽자식노드의 제일 큰값이나 오른쪽 자식의 가장 작은값과 교환하여 (왼쪽일지 오른쪽일지는 코드작성 전에 미리 정해두어야 한다.)리프노드에서 삭제.

                          5
            4 8          /           19 22
1 2 3 / 5 6 / 9 10  // 16 18 / 20 21 / 24 25 26

(4 삭제)
4의 오른쪽 트리에서 가장 작은값과 교환

                          5
            5 8          /           19 22
1 2 3 / 4 6 / 9 10  // 16 18 / 20 21 / 24 25 26

(4 삭제)

                          5
            5 8          /           19 22
1 2 3 /  6 / 9 10  // 16 18 / 20 21 / 24 25 26
           ㄴ> 언더플로우 발생

                          5
            3 8          /           19 22
1 2  / 5 6 / 9 10  // 16 18 / 20 21 / 24 25 26
         ㄴ> 이웃한 형제노드에서 원소를 가져온다

(9삭제)

                          5
            3 8          /           19 22
1 2  / 5 6 /  10  // 16 18 / 20 21 / 24 25 26
                 ㄴ>언더플로우, 형제노드의 원소갯수 역시 최소갯수인 2개

                          5
            3           /           19 22
1 2  / 5 6 8 10  // 16 18 / 20 21 / 24 25 26          => 병합을 했더니 3에서 언더플로우 발생

                      
                3   5   19  22
1 2  / 5 6 8 10  /16 18 / 20 21 / 24 25 26             => 병합

B+트리

b트리와 달리 트리의 최하위 레벨의 리프노드에만 데이터 들이 정렬되어있음. 
나머지 노드들은 키값만 가지고 있다.
파일시스템 같은 블록기반 스토리지에서 저장데이터의 효율적인 검색에 유용함

58
1234/567/89 10

이와같이 인덱스에 사용되던 키값마저 리프노드에 중복되어있다.
또한 1->2->3->4->5->.,...->10순으로 각 리프로드가 링크되어 linked list를 구성하고 있기 때문에
데이터의 순차적 처리가 가능하다.