B Tree

이미지가 깨지니 아래 notion링크로 이동 바람
https://teal-poultry-405.notion.site/B-B-cde90e43940f42ed95242dfab453b8fd

B-Tree

: B트리는 Binary Tree에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리이다. 정렬된 순서를 보장하고, 멀티레벨 인덱싱을 통해 빠른 검색을 할 수 있기 때문에 DB에서 사용하는 자료구조이다.

최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 한다.

• 노드는 최대 M개부터 M/2개 까지의 자식을 가질 수 있다.
• 노드에는 최대 M - 1 개 부터 [M/2] - 1 개의 키가 포함될 수 있다.
• 노드의 키가 x개라면 자식의 수는 x + 1 개이다
  • 포인터가 앞과 뒤에 추가로 붙기 때문
• 최소차수는 자식 수의 하한 값이며, 최소차수가 t라면 M = 2t - 1을 만족한다 (최소차수 t가 2라면 3차 B트리이며, Key의 하한은 1개이다)

3차 B 트리의 예

• 각 key의 앞 쪽 포인터는, 해당 key 보다 작은 key를 가르키는 포인터가 존재한다.
• 각 key의 뒤 쪽 포인터는, 해당 key 보다 큰 key를 가르키는 포인터가 존재한다.
• key들은 노드 안에서 항상 정렬된 값을 가진다.

Key 검색 과정

검색하고자 하는 값을 k 라고 가정한다면,

1. 루트 노드에서 시작하여 key들을 순회하며 k값의 범위를 찾는다
   • k와 같은 key를 찾았다면 검색을 종료한다.
   • 검색하는 key들의 대소관계를 비교하여 k값이 해당하는 자식으로 내려간다
2. 리프노드에 도달할 때 까지 1번을 반복한다, 만약 리프노드에 도달하여 k와 같은 key가 없을 경우, 검색을 실패한다.

위의 예시에서 만약 k 값이 18이라고 한다면,

1. root의 첫번째 key값(10)을 확인한다
2. k(18)은 10보다 크므로, 해당 key를 넘어서고, 다음 key(20)과 비교한다.
3. 18은 20보다 작으므로 10과 20사이에 있는 pointer의 자식노드로 내려간다.
4. 이후 다시 1번에서 했던 것처럼, 첫번째 key와 비교한다.
5. 18은 14보다 크기에 넘어가며, 마찬가지로 17보다 크기에 넘어가서 맨 오른쪽 포인터의 자식노드로 간다.
6. 18 검색 성공

Key 삽입 과정

• 적절한 리프노드를 검색한다
• 필요한 경우 노드를 분할한다

1. 트리가 비어있으면, 루트노드를 할당하고 k를 삽입한다. 만일 루트노드가 가득 찼다면, 노드를 분할하고 리프노드가 생성된다
2. 삽입하기에 적절한 리프노드를 찾아 k를 삽입한다. k값을 검색 했던 방법과 동일한 방법으로 삽입할 리프노드를 찾는다.

case 1 : 분할이 일어나지 않는 경우

9를 삽입하는 것을 예시로 한다.

블로그에 예시가 워낙 좋기 때문에 그대로 가지고 온다.

검색방법과 동일하게 진행하고, 리프 노드에 도달하면 해당하는 위치에 삽입해준다.

case 2 : 분할이 일어나는 경우

• 리프노드에 key가 가득 찬 경우, 노드를 분할해야 한다.

1. 오름차순으로 위에서 했던 방법으로 요소를 삽입한다. 이때 노드에 담을 수 있는 최대 Key개수가 초과하면
2. 중앙값에서 분할을 수행한다. 중앙값은 부모노드로 병합하거나 새로 생성된다.
   • 왼쪽 키들은 왼쪽 자식으로, 오른쪽 키들은, 오른쪽 자식으로 분할
3. 또한 해당 부모노드를 검사해서 또 다시 가득 찼다면, 부모노드도 1,2 과정을 반복한다.

case 1에서와 똑같이 검색하며 리프노드에 도달할 때 까지 나아간다.

이후 리프노드에 도달하면, 해당하는 위치에 삽입하고, 이후 중앙값을 찾는다 (12)

이후 마찬가지로 리프노드의 부모인 12, 14, 17이 들어있는 노드도 중앙값을 기준으로 분할을 진행한다.

또 마찬가지로 부모노드의 최대 key의 개수가 초과되었으므로, 분할을 진행한다.

다음과 같이 depth가 하나 증가한 2차 B트리가 완성되었다.

Key 삭제

1. 삭제할 키가 있는 노드 검색
2. 키 삭제
3. 트리 균형 조정

• inorder predecessor : 노드의 왼쪽 자손에서 가장 큰 key
• inorder successor : 노드의 오른쪽 자손에서 가장 작은 key
• 부모key: 부모노드의 key들 중 왼쪽 자식으로 본인 노드를 가지고 있는 key값입니다. 단, 마지막 자식노드의 경우에는 부모의 마지막 key입니다.

case 1 : 삭제할 key K 가 리프에 있는 경우

• 1.1: 현재 노드의 key 개수가 최소 key 개수보다 클 때

  • 트리 균형 조정할 필요 없이 그냥 삭제

• 1.2: 삭제할 시 최소 key 개수보다 작아지고, 왼쪽 또는 오른쪽 형제 노드의 key가 최소 key 개수 이상일 때

  • 부모 key 값으로 k를 대체한다.

  • 이후 형제노드가 왼쪽 형제라면 가장 큰 값을, 오른쪽 형제라면 가장 작은 값을 부모 key로 대체한다 (트리 균형 조정)

    

다음과 같은 방법으로, 최소 노드의 개수를 만족시키며 B트리의 균형을 유지시킨다.

• 1.3 왼쪽, 오른쪽 형제 노드의 key가 최소 key 개수이고, 부모노드의 key가 최소개수 이상일 때
  • k를 삭제한 후, 부모 Key를 형제노드와 병합한다 (부모노드는 줄어들게 된다).

• case 1.4) 자신과 형제, 부모 노드의 key 개수가 모두 최소일 때
  • 트리의 높이가 줄어드는 경우이므로 재 구조화 과정이 일어난다.

Case 2: 삭제할 key K가 내부 노드에 있고, 노드나 자식에 키가 최소 키 수보다 많은 경우

즉 삭제할 key가 리프노드가 아니며, 해당 노드와 그 자식의 키가 최소 키수보다 많은경우

1. 현재 노드의 inorder predecessor 또는 inorder successor와 k의 자리를 바꿉니다.
2. 리프노드의 k를 삭제하게 되면, 리프노드가 삭제 되었을 때의 조건으로 변합니다. 삭제한 리프노드에 대해서 case 1 조건으로 이동합니다.

이후 10의 노드가 삭제 되었을 때의 조건으로 만약 트리 균형이 필요할 경우 진행한다.

Case 3 : 삭제할 key K 가 내부 노드에 있고, 노드에 key 개수가 최소 key 개수만큼, 노드의 자식 key 개수도 모두 최소 key 개수인 경우

→ key를 삭제하면 트리의 높이가 줄어들어 재구조화가 일어나야 함

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

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

3. -1 새로 구성된 인접 형제노드와의 병합 후 최대 key의 개수를 넘겼다면, 삽입연산에서 했었던 노드 분할 과정을 수행한다.

4. -2 형제노드가 새로 구성되어도 부모노드의 개수가 최소 key의 개수보다 작아진다면 해당 노드에 다시 2번 과정을 반복한다.

+++++