btree.md

B - tree

• 이진 트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞추는 트리 (이진트리 : 자식 노드가 최대 2개)

• ‘자식 노드의 개수가 2개 이상인 트리 + 한 노드 내의 데이터가 1개 이상’ (이진트리와 다른점, 최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 함)

• ex) 3차 B-트리 (노드에 데이터 2개, 자식은 3개까지 가능)

• 

• 특징

  • 삽입과 삭제가 일어나더라도 최대한 균형있는 트리 형태를 유지한다.

    즉, 리프노드로 가는 경로의 길이는 모두 같다 = 리프노드는 모두 같은 레벨에 있다. ⇒ 이진트리의 장점(검색 속도)을 가져감

    (균형이 맞춰지지 않은 편향 트리의 경우, 검색 시 선형 검색과 같은 O(n) 시간이 걸려 비효율적이다.)

  • 노드의 자료수가 K 이라면, 자식의 수는 K + 1 개이어야 한다.

  • 자료는 정렬된 상태로 저장된다.

  • 한 노드 N 의 왼쪽 서브트리는 N보다 작은 값으로 되어 있고, 오른쪽 서브트리는 큰 값으로 되어 있다.

  • 노드는 최대 M개 부터 M/2개 까지의 자식을 가진다.

  • 노드에는 최대 M−1개 부터 최소 [M/2]−1개의 키가 포함될 수 있습니다.

    • 삽입 시 최대 키값 초과일 경우 : 분할하는 과정 필요
    • 삭제 시 최소 키값 미만일 경우 : 재분배, 병합하는 과정 필요

B - tree의 key 검색

• 루트노드에서 시작하여 하향식으로 검색을 수행합니다.
• 검색하고자 하는 key를 k라 하자.
• 검색 과정

  1. 루트 노드에서 시작하여 key들을 순회하면서 검사합니다.

     case a) 만일 k와 같은 key를 찾았다면 검색을 종료합니다.

     case b) 검색하는 값과 key들의 대소관계를 비교해봅니다. 어떠한 key들 사이에 k가 들어간다면 해당 key들 사이의 자식노드로 내려갑니다.

  2. 해당 과정을 리프노드에 도달할 때까지 반복합니다.

  • ex) 탐색 과정
  • 

B - tree의 key 삽입

• 삽입 과정

  1. 삽입할 위치의 노드를 탐색 (검색 연산과 동일한 방법)

  2. 리프노드의 상황에 따라, 필요할 경우 분할하여 삽입한다.

     2-1) 분할 X : 리프노드가 가득차지 않았다면, 오름차순으로 k를 삽입합니다.

     2-2) 분할 O : 리프노드에 key 노드가 가득 찬 경우, 노드를 분할해야 합니다.

     a. 오름차순으로 요소를 삽입한다. 이때, 노드의 최대 key 개수를 초과하게 된다.

     b. 분할을 수행합니다. 중앙값은 부모 노드로 병합하거나 새로 생성됩니다. 왼쪽 키들은 왼쪽 자식으로, 오른쪽 키들은 오른쪽 자식으로 분할한다.

     c. 부모 노드를 검사해서 또 다시 가득 찼다면, 다시 부모노드에서 위 과정을 반복합니다.

  • ex) 삽입 시 분할이 필요한 경우
  • 

B - tree의 key 삭제

삭제를 했더니 노드에 최소 키값인 [(M-1)/2)] 보다 적으면 언더 플로가 발생하기 때문에 재분배나 병합을 해야한다.

• 재분배 : 형제 노드중에서 최소보다 많은 키값을 가진 노드에게 키 값을 받아 오는 것

• 병합 : 재분배가 안될 때, 형제노드에 있는 키 값과 이 두 노드의 부모노드에 있는 키값을 합병

• 삭제 과정

  1. 삭제할 키가 있는 노드 검색
  2. 키 삭제
  3. 필요한 경우, 트리 균형 조정

• 용어

  • inorder predecessor : 노드의 왼쪽 자손에서 가장 큰 key
  • inorder successor : 노드의 오른쪽 자손에서 가장 작은 key

• Case 1. 삭제할 key k가 리프에 있는 경우

  • Case 1-1) 현재 노드의 key 개수가 최소 key 개수보다 크다면

    • 해당 k를 단순 삭제

  • Case 1-2) 왼쪽 또는 오른쪽 형제 노드의 key가 최소 key 개수 이상이라면

    1. 부모 key 값으로 k를 대체합니다.
    2. 최소키 개수 이상의 키를 가진 형제 노드가 왼쪽 형제라면 가장 큰 값을, 오른쪽 형제라면 가장 작은 값을 부모key로 대체합니다.
    • ex) 삭제 시, 본인은 최소 키값보다 적고, 형제는 최소 키값 이상일 경우
    • 

  • Case 1-3) 왼쪽, 오른쪽 형제 노드의 key가 최소 key 개수이고, 부모 노드의 key가 최소 개수 이상이면

    1. k를 삭제한 후, 부모key를 형제 노드와 병합합니다.
    2. 부모노드의 key개수를 하나 줄이고, 자식 수 역시 하나를 줄여 B-Tree를 유지합니다.
    • ex) 삭제 시, 본인과 형제는 최소 키값보다 적고 부모는 최소 키값 이상일 경우
    • 

• Case 2. 삭제할 key k가 내부 노드(리프노드가 아닌 노드)에 있고, 노드나 자식에 키가 최소 키수보다 많을 경우

  1. 현재 노드의 inorder predecessor 또는 inorder successor와 k의 자리를 바꿉니다.
  2. 리프노드의 k를 삭제하게 되면, 리프노드가 삭제 되었을 때의 조건으로 변합니다. 삭제한 리프노드에 대해서 case 1 조건으로 이동합니다.
  • ex) 본인 노드나 자식이 최소 key값보다 많을 경우
  • 

• Case 3. 삭제할 key k가 내부 노드에 있고, 노드와 노드의 자식이 모두 최소 key 개수인 경우

  • k를 삭제하면 트리의 높이가 줄어들어 재구조화가 일어나는 케이스이다.

  1. k를 삭제하고, k의 양쪽 자식을 병합하여 하나의 노드로 만듭니다.

  2. k의 부모key를 인접한 형제 노드에 붙입니다. 이후, 이전에 병합했던 노드를 자식노드로 설정합니다.

  3. 해당 과정을 수행하였을 때 부모노드의 개수가 에 따라 이후 수행 과정이 달라집니다.

     3-1) 만일 새로 구성된 인접 형제노드의 key가 최대 key 개수를 넘어갔다면, 삽입 연산의 노드 분할 과정을 수행합니다.

     3-2) 만일 인접 형제노드가 새로 구성되더라도 원래 k의 부모 노드가 최소 key의 개수보다 작아진다면, 부모 노드에 대하여 2번 과정부터 다시 수행합니다.

     • 

---

B + tree

• 실제 DB의 인덱싱은 B+트리로 구현된다.
• 특징
  • 키값이 저장된 인덱스노드와 데이터가 함께 저장된 리프노드로 구성된 트리 구조
  • 리프노드들은 모두 연결리스트의 형태를 가져 선형 검색을 할 수 있다.
• B-tree와 B+tree의 다른 점?

  1. B-tree의 노드에 key 와 data가 들어가는 반면, B+tree의 노드는 key만 들어가고, 리프노드에만 data가 들어감.

     • 장점 : B+트리에서 인덱스 노드들의 메모리가 절약되어 더 많은 키값을 저장할 수 있어, 트리 레벨이 낮아질 수 있음.
     • 단점 : B+트리는 항상 리프노드까지 검색해야 함.

  2. 리프노드가 연결리스트의 형태를 띄어 선형 검색이 가능함.

     ⇒ 특정 키값 검색, 순차적으로 처리할 때 효율적임

(검색 과정은 B-트리와 동일)

key 삽입과정

• 일반적으로는 B-트리와 같으나, 다음의 경우 B-트리와 다르다.

  • Case 1. 분할 X,리프노드의 가장 앞 key 자리에 삽입할 경우

    • 삽입 후 부모 key를 삽입된 key로 갱신
    • 

  • Case 2. 분할이 일어나는 삽입과정

    2-1) 분할이 인덱스노드에서 일어난다면, B트리 동일하게 진행

    2-2) 분할이 리프노드에서 일어난다면, 오른쪽 노드에 중간 key를 포함하여 분할하고 연결리스트 유지

    • ex) 리프노드에서 분할이 일어날 경우
    • 

key 삭제과정

• 삭제는 리프노드에서만 이루어진다.
• 재분배 : 형제 노드중에서 최소보다 많은 키값을 가진 노드에게 키 값을 받아 오는 것
• 병합 : 재분배가 안될 때, 형제노드에 있는 키 값과 이 두 노드의 부모노드에 있는 키값을 합병
• Case 1. 삭제할 key k가 인덱스 노드에 없는 경우
  • B트리와 동일
• Case 2. 삭제할 key k가 인덱스 노드에 있는 경우(리프노드의 가장 처음 key인 경우)
  • 리프노드의 k를 삭제한 후, 인덱스 노드의 k를 inorder successor와 바꾼다.
  • ex) 삭제할 대상의 키값이 인덱스 노드에도 있는 경우
  • 

---

정리

• B - tree란?
  • 모든 리프노드들이 같은 레벨을 가질 수 있도록 삽입/삭제 시 밸런스를 맞추는 트리
  • 리프노드로 가는 경로의 길이는 모두 같아서, 이진트리의 장점대로 검색 속도가 O(longN)으로 빠르다. (편향 트리라면, 선형 검색처럼 O(n)의 시간이 걸림)
• B - tree와 B + tree의 차이점?

  1. B-tree의 노드에 key 와 data가 들어가는 반면, B+tree의 노드는 key만 들어가고, 리프노드에만 data가 들어감.

     • 장점 : B+트리에서 인덱스 노드들의 메모리가 절약되어 더 많은 키값을 저장할 수 있어, 트리 레벨이 낮아질 수 있음.
     • 단점 : B+트리는 항상 리프노드까지 검색해야 함.

  2. B + tree는 리프노드가 연결리스트의 형태를 띄어 선형 검색이 가능함.

     ⇒ 특정 키값 검색, 순차적으로 처리할 때 효율적임