[자료구조] B-Tree

목차

B-트리

내장 색인: 메모리에 올려서 사용 (이진 검색 트리)

외장 색인: 메인 메모리 외부에 놓고 사용하는 색인 (B-트리)

색인의 규모가 클 경우 or 메인 메모리가 충분하지 않을 때 디스크에 두고 사용

디스크 접근 시간으로 인한 비효율을 최대한 줄여야 함

• B-트리: 디스크 환경에서 사용하기 적합한 외장 다진 검색 트리

최대 M개의 자식을 가질 수 있는 B트리=M차 B트리

$$key_i−1<T_i<key_i$$

성질

1. 루트를 제외한 모든 노드는 k/2 ~k개의 키를 갖는다.
   1. k: 한 블록이 수용할 수 있는 최대 키의 개수
   2. 예외: 루트 노드는 적어도 2개 이상의 자식을 가짐
2. 모든 리프 노드는 같은 깊이를 가진다.
3. 노드의 자료수가 N이면, 자식 수는 N+1이어야 함
   1. 노드의 자료수(key)가 3개라면, 그 노드의 자식 수는 4개

$$key_1, key_2, key_3$$ $$node_1 < key_1$$ $$key_1 < node_2 < key_2$$ $$key_2 < node_3 < key_3$$ $$node_4 > key_3$$

1. 각 노드의 자료는 정렬된 상태여야함
2. 입력 자료는 중복 될 수 없음

알고리즘

검색

기본적으로 이진 검색 트리의 검색과 같음

1. 노드의 여러 키 중 검색 키와 일치하는 것이 있는지 확인
2. $$key_i−1 < x <  key_i $$인 두 키를 찾아 분기해야 할 자식 노드를 찾음
3. 자식으로 분기하고 나면 깊이만 하나 내려간 똑같은 검색 문제(다시 자식 노드를 찾음) → 재귀적 과정

삽입

ex) 각 노드가 최대 5개의 키를 가질 수 있다고 가정

루트 노드를 제외하고 2~5개의 키를 가져야 한다.

1. x를 삽입할 리프 노드 r을 찾는다.
2. 노드 r에 공간의 여유가 있으면 키를 삽입하고 끝낸다. (case 1)
3. 노드 r에 여유가 없으면 형제 노드에 공간의 여유가 있는지 살펴본다.
   • 형제 노드에 공간의 여유가 있으면 키를 하나 넘기고 끝낸다. (case 2)

     

   • 형제 노드에 여유가 없으면 노드를 2개로 분리한다. 분리 작업은 부모 노드로 키를 하나 넘기는 작업을 포함한다. (case 3)

   • 

삭제

1. x를 키로 갖고 있는 노드를 찾는다.
2. 리프노드인지 아닌지 확인
   1. 리프노드라면 바로 삭제 (case 1)
   2. 리프노드가 아니라면 x의 직후 원소 r과 x를 교환한 후, 리프 노드 x 제거 (case 2)
3. x를 제거한 후 노드에 언더플로우가 발생하면 해소한다. (case 3)

작업 성능

d진 검색 트리가 균형을 잘 맞추면 높이가 logdn 에 근접

B-트리에서 임의의 노드가 최대 d개의 자식을 가질 수 있다면, 최소한 d−12+1개에서 d2개의 자식을 가져야 함

→ 높이는 O(logn)

• 작업 수행시간은 디스크 접근 횟수를 기준으로 함

검색

O(logn) (높이)

삽입

실패하는 검색을 한 번 수행 O(logn)

오버플로우가 최대한 발생하더라도 높이에 비례하는 시간 O(logn)

→ O(logn)

삭제

삭제 원소 검색 + 직후 원소를 찾는 작업 O(logn)

언더플로우 최대 O(logn)

→ O(logn)

→ 두 작업 모두 이진 검색 트리에 비해 빠름