B 트리란?

B 트리란?

• B트리는 데이터베이스와 파일 시스템에서 널리 사용되는 자가 균형 이진 검색 트리의 일종입니다.
• B트리의 설계는 디스크 I/O 작업의 최소화를 목표로 하며, 이를 위해 트리의 높이를 가능한 낮게 유지합니다.
• 해당 포스팅에선 B트리의 규칙과 조회, 삽입, 삭제 방법에 대해서 다뤄보겠습니다.

규칙

• 노드
  • 노드 차수(M): 각 노드가 가질 수 있는 자식 노드의 최대 개수
    • 각 노드는 최소 M/2개에서 최대 M개의 자식 노드를 가질 수 있습니다.
  • 루트 노드: 최소 2개의 자식 노드 (트리 생성/삭제 시 예외 가능)
  • 내부 노드: 최소 ⌈M/2⌉개의 자식 노드
  • 리프 노드: 모든 리프 노드는 동일한 레벨에 있어야 함 (데이터 접근 시간 균일화)
• 키
  • 각 노드에 저장된 값입니다.
  • 키 개수 범위: 최소 (M/2)-1개, 최대 M-1개 (최소 키 개수는 1개)
  • 키는 노드 내부에서 정렬된 상태로 유지되어야 합니다.

조회 방법

• B트리에서 데이터를 조회할 때는 루트에서 시작하여 재귀적으로 자식 노드를 탐색하며, 리프 노드에서 최종적으로 키의 존재 유무를 판단하는 방식입니다.
  1. 루트 노드에서 시작: 루트 노드에서 검색할 키 값과 노드 내 키 값들을 비교합니다. 검색 키가 노드 내 키들보다 작으면 왼쪽 자식 노드로, 크면 오른쪽 자식 노드로 이동합니다.
  2. 재귀적 탐색: 선택된 자식 노드에서 동일한 과정을 반복하여 리프 노드에 도달하거나 검색 키를 찾을 때까지 탐색을 진행합니다.
  3. 키 발견 또는 실패: 리프 노드에서 검색 키를 발견하면 검색에 성공한 것이고, 발견하지 못하면 해당 키가 트리에 없는 것이므로 검색에 실패한 것입니다.

삽입 방법

• B트리에 새 키를 삽입할 때는 먼저 적절한 리프 노드를 찾고, 그 노드에 여유 공간이 있으면 삽입하고, 없으면 노드를 분할하여 상위 노드로 중간값을 올리는 과정을 거치게 됩니다.
  1. 적절한 리프 노드 찾기 : 삽입하려는 키에 대해 조회 과정을 수행하여 적절한 리프 노드를 찾습니다.
  2. 리프 노드에 삽입 : 해당 리프 노드에 여유 공간이 있다면 키를 삽입합니다.
  3. 노드 분할 : 여유 공간이 없다면 노드를 분할하여 새로운 키와 기존 키들을 두 노드에 분배합니다. 중간값은 상위 노드로 올라갑니다.
  4. 재귀적 분할 : 상위 노드도 꽉 차 있다면 이 과정을 재귀적으로 반복하여, 필요한 경우 루트까지 분할합니다.

삽입 예제

• 차수(M)가 3인 B트리를 통해 삽입 과정 및 노드 분할을 설명하겠습니다.

                 [10, 20]
                /    |    \
             [5]   [15]   [25, 30]

삽입 시 노드 분할이 일어나지 않는 경우

• '17' 삽입 과정

  • 적절한 리프 노드 찾기

    • 루트 노드 [10, 20]에서 17은 10과 20 사이에 위치하므로, 중간 자식 노드 [15]로 이동합니다.

  • 리프 노드 삽입

    • 리프 노드 [15]에 17을 삽입하면 [15, 17]이 됩니다.
    • 리프 노드에 여유 공간이 있어 17을 바로 삽입할 수 있습니다.

  • 노드 분할 없이 삽입 완료

    • 리프 노드에 바로 삽입이 가능하므로 노드 분할 과정 없이 삽입이 완료됩니다.

           [10,    20]
          /     |     \
       [5]   [15, 17] [25, 30]

삽입 시 노드 분할이 일어나는 경우

• '22' 삽입 과정

  • 적절한 리프 노드 찾기

    • '22'는 루트 노드 [10, 20]를 거쳐 리프 노드 [25, 30]로 이동합니다.

  • 리프 노드 삽입 시도

    • 리프 노드 [25, 30]에 '22'를 삽입하려 하지만, 이미 최대 키 수(2개)를 가지고 있어 노드 분할이 필요합니다.

             [10,    20]
            /     |     \
         [5]   [15, 17] [22, 25, 30]

  • 노드 분할 준비

    • [22, 25, 30]에서 중간값 '25'를 기준으로 노드 분할을 준비합니다.

  • 분할 실행

    • 왼쪽 새 노드 [22], 오른쪽 새 노드 [30]이 생성됩니다.

    • 중간값 '25'는 상위 노드로 이동합니다.

             [10,   20,   25]
            /    |      |    \
         [5]   [15,17] [22]  [30]

  • 루트 노드 분할

    • 루트 노드 [10, 20, 25]도 최대 키 수(2개)를 넘어서므로 중간값 '20'을 기준으로 분할합니다.

    • 분할 결과 '20'이 새로운 루트 노드가 되고, [10]과 [25]가 자식 노드가 됩니다.

               [20]
              /       \
         [10]        [25]
        /    |      /    \
      [5]   [15,17] [22]  [30]

삭제 방법

• 먼저 삭제할 키를 찾고, 그 키를 삭제한 후 트리의 균형이 깨지면 인접 노드들과 병합하거나 키를 재분배하여 균형을 유지하는 작업을 수행하게 됩니다.
  • 키 위치 찾기
    • 삭제하려는 키의 위치를 트리에서 탐색하여 찾습니다.
  • 키 삭제
    • 키가 리프 노드에 있다면 그 노드에서 바로 삭제합니다.
    • 키가 내부 노드에 있다면, 그 키를 리프 노드로 내리고 리프 노드에서 삭제합니다.
  • 트리 균형 조정
    • 키 삭제 후 해당 노드의 키 개수가 최소 요구 개수(M/2 - 1) 미만이 되면 트리의 균형을 맞추기 위해 조정이 필요합니다.
    • 인접한 노드와 병합(merge)하거나 키를 재배치(redistribution)하여 균형을 맞춥니다.

리프 노드에서 삭제하는 경우

• 키 삭제 후 노드의 키 개수가 최소 개수 이상인 경우

  • 단순히 해당 키를 삭제하면 됩니다.

  • 트리 재조정이 필요하지 않습니다.

        # 키(17) 삭제
    
                      [20]
                    /       \
                [10]        [25]
              /    |       /    \
           [5]   [15,17] [22]  [30]

                      [20]
                    /       \
               [10]        [25]
              /    |      /    \
           [5]   [15]   [22]  [30]

• 키 삭제 후 노드의 키 개수가 최소 개수 미만인 경우

  • A. 형제 노드의 키 개수가 최소 개수를 초과하는 경우

    • 삭제하려는 키를 부모의 키로 대체합니다.

    • 왼쪽 형제라면 왼쪽 형제의 가장 큰 값을, 오른쪽 형제라면 오른쪽 형제의 가장 작은 값을 부모 키로 대체합니다.

          # 키(5) 삭제
                         [20]
                      /       \
                   [10]        [25]
                /    |        /    \
             [5]   [15,17] [22]  [30]

                        [20]
                      /       \
                 [15]        [25]
                /    |      /    \
             [10]   [17] [22]   [30]

  • B. 형제 노드의 키 개수도 최소 개수인 경우

    • a) 부모 노드의 키 개수가 최소 개수를 초과하는 경우

      • 키를 삭제하고 부모 키를 내려 형제 노드와 병합합니다.

          # 키(13) 삭제
                              [20]
                           /        \
                   [10, 15]         [25]
                  /    |   \      /    \
               [5]   [13] [17] [22]   [30]

                         [20]
                       /      \
                   [15]       [25]
                  /   \      /    \
              [5, 10] [17] [22]   [30]

    • b) 부모 노드의 키 개수도 최소 개수인 경우

      1. 키를 삭제합니다.

      2. 삭제된 키의 부모 노드의 키를 인접한 형제 노드에 붙입니다.

      3. 만약 새로 구성된 형제 노드가 최대 키 개수를 넘어갔다면, 삽입 연산에 따른 노드 분할 과정을 수행합니다.

      4. 형제 노드가 최대 키 개수를 넘지 않았지만, 부모 노드의 키 개수가 최소 개수를 만족하지 못한다면, 부모 키를 기준으로 2번을 다시 진행합니다.

      5. 삽입에 따른 분할 과정을 수행합니다.

          # 키(22) 삭제
                            [20]
                          /        \
                  [10, 15]        [25]
                 /    |   \      /    \
              [5]   [13] [17] [22]   [30]

                            [20]
                         /        \
                   [10, 15]       []
                 /    |    \        \
              [5]   [13]  [17]      [25, 30]

                  [10, 15, 20]
                 /    |   \    \
              [5]   [13] [17]  [25, 30]

                       [15]
                      /    \
                  [10]      [20]
                 /   \     /    \
              [5]   [13] [17]    [25, 30]

내부 노드에서 삭제하는 경우

• 리프 노드에 있는, 삭제하려는 키의 선임자 또는 후임자 키와 위치를 바꿉니다.

  • 선임자 : 나보다 작은 데이터들 중 가장 큰 데이터
  • 후임자 : 나보다 큰 데이터들 중 가장 작은 데이터

• 리프 노드에서 키 삭제

  • 위치가 바뀐 선임자 또는 후임자 키를 리프 노드에서 삭제합니다.

  • 이때 리프 노드에서의 삭제 방식은 앞서 설명한 리프 노드 삭제 규칙을 따릅니다.

        # 키(10) 삭제
                      [20]
                    /       \
                 [10]      [25]
              /    |      /    \
           [5]   [15,17] [22]  [30]

                     [20]
                    /       \
                [15]       [25]
              /    |      /    \
           [5]   [10, 17] [22]  [30]

                    [20]
                  /       \
               [15]        [25]
              /    |      /    \
           [5]   [17]   [22]  [30]