B Tree (B 트리)

특징 및 개념
정렬된 데이터 보존.
로그시간내에 검색, 순차접근, 삽입, 삭제가 가능.
노드가 가득차 있지 않기 때문에 일정부분의 공간이 낭비됨.
모든 리프노드가 같은 깊이를 가지게 됨.

B트리의 노드들은 여러개의 키를 가지고 있고, 이 키를 기준으로 하위트리들을 나누게 됨.
자식노드의 개수는 키개수+1 이 됨.

정의
각 노드의 키값은 하위트리들을 나누는 값이 되어야 함.
차수가 m인 B 트리는 다음 속성들을 만족시켜야 함.
1. 모든 노드는 최대 m 개의 자식들을 가져야한다.
2. 리프노드가 아닌 모든 노드(루트노드 제외)는 최소한 m/2개의 자식을 가져야 한다.
3. 루트 노드는 최소한 2개의 자식을 가져야 한다.
4. k개의 자식을 가지고 있는 리프노드가 아닌 노드는 k-1개의 키를 가진다.
5. 모든 리프노드들은 같은 수준이어야 한다.


알고리즘

검색
이진 탐색 트리 검색과 비슷함. 루트에서 시작해서 재귀적으로 탐색함.

삽입
모든 삽입은 리프노드에서 시작함.
새 원소를 삽입하기 위해서는, 해당 원소가 삽입되어야 하는 리프노드를 찾은 다음 다음 단계를 따라서 삽입 진행.
1. 노드에 빈자리가 있다면 원소 순서에 맞게 새로운 원소를 삽입.
2. 노드가 꽉차있다면, 노드를 2개로 분할함.
   2.1 리프노드의 값들과 새로운 원소중에서 중간값을 선택함.
   2.2 선택된 중간값보다 작은 값들은 새로 만들어진 왼쪽 노드에 넣고 큰값들은 새로 만들어진 오른쪽 노드에 넣음. 즉, 중간값이 구분하는 값으로 작용.
   2.3 구분값을 부모노드에 입력함. 이때, 부모노드에 자리가 없으면 부모노드를 분할해야 함. 부모노드가 없으면(즉, 루트노드일때) 새로운 루트노드를 생성함.(트리의 단계가 늘어나게 됨.)

삭제
리프노드에서 삭제
1. 삭제하려는 값을 검색
2. 리프노드에 있는 값이면 노드에서 값을 삭제
3. 재배열(rebalancing)이 필요하면 재배열함.

내부노드에서 삭제
내부 노드의 값들은 하위트리의 구분값으로 작용하기 때문에 대체할수 있는 값을 찾아야 함.
왼쪽 하위트리의 가장 큰 원소 또는 오른쪽 서브트리의 가장 작은 원소가 구분자 역할을 할 수 있음.
1. 새로운 구분자를 선택, 해당 구분자가 속한 리프노드에서 삭제하고 삭제될 원소의 자리에 집어넣는다.
2. 1단계에서 원소가 삭제된 리프노드가 필요한 만큼의 원소를 가지고 있지 못하게 되면 해당 리프노드부터 트리를 재배열함.

삭제후 재배열(Rebalancing)
1. 부족한 노드의 오른쪽 사촌노드가 존재하고 원소가 최소 원소개수보다 많다면 왼쪽으로 회전한다.
    1.1 부모노드의 구분자를 부족한 노드의 끝으로 복사한다.(구분자가 한단계 아래로 내려감, 부족한 노드가 이제 최소 원소개수를 가지게 됨.)
    1.2 부모노드의 구분자를 오른쪽 사촌노드의 첫번째 원소로 변경함.
    1.3 트리의 균형이 맞춰짐.
2. 1번단계 조건이 아니고, 부족한 노드의 왼쪽 사촌노드가 존재하고 원소가 최소 원소개수보다 많다면 오른쪽으로 회전한다.
    2.1 부모노드의 구분자를 부족한 노드의 첫번째로 복사한다.(구분자가 한단계 아래로 내려감, 부족한 노드가 이제 최소 원소개수를 가지게 됨.)
    2.2 부모노드의 구분자를 왼쪽 사촌 노드의 마지막 원소로 변경함.
    2.3 트리의 균형이 맞춰짐.
3. 1, 2번 단계 조건이 아니고, 좌우 사촌노드들이 최소개수의 원소들만 가지고 있다면, 좌우 사촌노드들을 합친다.
    3.1 구분자를 왼쪽 노드의 마지막에 복사한다.
    3.2 오른쪽 노드의 모든 원소들을 왼쪽 노드로 옮긴다. (왼쪽노드가 최대 개수의 원소를 가지게 됨.)
    3.3 오른쪽 노드가 더이상 필요없게 되니 삭제함.
    3.4 부모노드에서 구분자를 삭제함.
          3.4.1 부모노드가 루트면서 원소가 없게되면, 기존 루트를 없애고 합쳐진 노드를 새로운 루트로 만듬.
          3.4.2 3.4.1의 경우가 아니고, 부모노드의 원소개수가 필요한 원소개수보다 줄어들면, 부모노드를 재배열한다.

초기구성(Initial Construction)
1에서 24까지의 정수를 리프노드의 최대크기가 4인 B트리로 구성하는 경우.

1. 개별 노드가 5개의 값을 가지는 4개의 리프노드를 만듬.

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24

2. 각 리프노드의 마지막 원소를 골라서 부모노드들을 만듬. 여기서는 내부 노드들이 최대 2개의 값을 가진다고 가정함. 그러니까 노드의 원소가 3개가 되도록 뽑아내서 구성함.

5 10 15

20

1 2 3 4

6 7 8 9

11 12 13 14

16 17 18 19

21 22 23 24

3. 최상단에 하나의 노드가 나올때까지 이 과정을 반복함.

15

5 10

20

1 2 3 4

6 7 8 9

11 12 13 14

16 17 18 19

21 22 23 24

참조
1. https://en.wikipedia.org/wiki/B-tree
2. http://ko.wikipedia.org/wiki/B_%ED%8A%B8%EB%A6%AC
3. http://sweeper.egloos.com/896423