ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • B-트리 #1. 소개 및 검색/삽입
    Programming/College 2010. 6. 2. 13:30
    728x90
    반응형
    SMALL

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

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

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

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

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

    반응형
    LIST

    댓글

Designed by Tistory.