B트리

B trees(다진 검색트리)

- 디스크의 접근 단위는 블록(페이지)

- 디스크에 한 번 접근하는 시간은 수십만 명령어의 처리 시간과 맞먹는다.

- 검색트리가 디스크에 저장되어 있다면 트리의 높이를 최소화하는 것이 유리하다.

- B-트리는 다진검색트리가 균형을 유지하도록 하여 최악의 경우 디스크 접근 횟수를 줄이는 것이다.

---

 

요약

1. 검색트리는 데이터를 저장, 검색, 삭제하기 위한 자료구조이다.

2. n개의 원소로 구성된 이진검색트리에서 한 원소를 저장, 검색, 또는 삭제하기 위해 평균 O(log n)의 시간이 든다. 트리의 균형이 나쁘면 최악의 경우 O(n)의 시간이 들 수 있다.

3. 균형잡힌 검색트리는 저장, 검색, 삭제하기 위해 최악의 경우에도 O(log n)의 시간이 보장되도록 해준다.

예) 레드블랙트리, B-트리

4. B-트리는 검색트리가 디스크에 저장되어 있는 겨우에 유용한 검색트리다. B-트리는 디스크의 블록 크기와 트리의 노드 크기를 일치시킴으로써 가능한 최대의 분기를 추구한다. 디스크 접근 횟수를 현저히 떨어뜨려 검색트리에서의 저장, 검색, 삭제의 효율을 높인다.

5. 키가 하나의 필드로 이루어지면 일차원 키, 여러 개의 필드로 이루어지면 다차원 키라고 한다.

- 이진검색트리, 레드블랙트리, B-트리는 일차원 검색

- KD-트리, KDB-트리, 그리드 파일은 다차우너 검색

6. 일차원 검색트리의 기본 작업을 깊이 이해하면 다차원 검색 트리의 기본 작업은 매우 유사한 방법으로 쉽게 할 수 있다.

 

출처 : http://fromvenus.tistory.com/145

 

 

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

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

출처 : http://arisu1000.tistory.com/27715