티스토리 뷰

B-트리는 인덱스를 조직하는 트리 구조로 가장 많이 사용되는 것으로써
Bayer와 McCreight에 의해 제안되었다.
이것은 m-원 균형 탐색 트리로서 효율적인 균형 알고리즘을 제공한다.

이어지는 내용에서 이해하기 쉽게 설명하기 위해 노력하겠지만
일단 위키피디아의 B-트리 링크를 제공하겠다.
위키피디아 B-트리 보기

특성 : m-원 탐색트리이다.
         각 노드가 적어도 반 이상이 키 값으로 채워져 있어야 한다.
         트리가 공백이 아닌 이상 처음부터 분기해야 한다.
         트리가 균형을 유지해야 한다.

▣ 검색과 삽입
◇ 검색 : B-트리의 검색은 m-원 탐색 트리의 직접 검색과 똑같은 과정을 거치게 된다.

m-원 탐색 트리 알고리즘 펼치기

◇ 삽입 : 새로운 키 값은 항상 리프 노드에 삽입된다.
             따라서 새로운 키 값을 삽입해야 되는 리프 노드에 키 값을 삽입할 수 있는
             여유 공간이 있느냐 없느냐에 따라 두 가지 경우가 발생한다.
    ▷ 해당 노드에 키 값이 가득 차 있지 않아 빈 공간이 있는 경우
       - 새로운 키 값을 단순히 순서에 맞게 삽입하기만 하면 된다.
    ▷ 해당 노드가 키 값으로 만원이 되어 새로운 키 값을 삽입할 공간이 없는 경우
       - 노드에서 오버플로(overflow)가 발생하였으므로
         이 노드를 두 개의 노드로 분할(split)한다.
         그리하여 키 값의 반은 한 쪽 노드에 들어가고, 나머지 반은 다른 노드에 들어가게
         된다. 이 때 중간 키 값은 노드의 부모 노드(parent node)로 올라가서 삽입되는데,
         분할된 노드들을 가리키는 포인터도 함께 첨가된다.

B-트리 삽입 알고리즘 펼치기

댓글
댓글쓰기 폼