[자료구조] 그림으로 알아보는 B-Tree

emplam27·2021년 1월 11일
29
post-thumbnail

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

실제 DB에서는 B트리에서 발전한 B+트리를 실제로 사용한다고 합니다. 2번에 걸쳐 B트리와 B+트리에 대해 포스팅 해보겠습니다.


B-Tree?

B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있습니다. 최대 MM개의 자식을 가질 수 있는 B트리를 MM차 B트리라고 하며 다음과 같은 특징을 같습니다.

  • 노드는 최대 MM개 부터 M/2M/2개 까지의 자식을 가질 수 있습니다.
  • 노드에는 최대 M1M - 1개 부터 [M/2]1[M/2] - 1개의 키가 포함될 수 있습니다.
  • 노드의 키가 xx개라면 자식의 수는 x+1x+1개 입니다.
  • 최소차수는 자식수의 하한값을 의미하며, 최소차수가 t라면 M=2t1M = 2t - 1을 만족합니다. (최소차수 tt가 2라면 3차 B트리이며, key의 하한은 1개입니다.)

다음은 차수가 3인 B트리 입니다. 파란색 부분은 각 노드의 key를 나타내며, 빨간색 부분은 자식 노드들을 가르키는 포인터입니다. key들은 노드 안에서 항상 정렬된 값을 가지며, 이진검색 트리처럼 각 key들의 왼쪽 자식들은 항상 key보다 작은 값을, 오른쪽은 큰 값을 가집니다.



key 검색과정

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

  1. 루트 노드에서 시작하여 key들을 순회하면서 검사합니다.
    1-1. 만일 kk와 같은 key를 찾았다면 검색을 종료합니다.
    1-2. 검색하는 값과 key들의 대소관계를 비교해봅니다. 어떠한 key들 사이에 kk가 들어간다면 해당 key들 사이의 자식노드로로 내려갑니다.

  2. 해당 과정을 리프노드에 도달할 때까지 반복합니다. 만일 리프노드에도 kk와 같은 key가 없다면 검색을 실패합니다.



key 삽입과정

key를 삽입하기 위해서는 1. 요소 삽입에 적절한 리프 노드를 검색하고, 2. 필요한 경우 노드를 분할해야 합니다. 리프노드 검색은 하향식이지만 노드 분할의 과정은 상향식으로 이루어진다고 볼 수 있습니다. 삽입하고자 하는 값을 kk로 하였을 때 삽입 과정입니다.

  1. 트리가 비어있으면 루트 노드를 할당하고 kk를 삽입합니다. 만일 루트노드가 가득 찼다면, 노드를 분할하고 리프노드가 생성됩니다.

  2. 이후부터는 삽압하기에 적절한 리프노드를 찾아 kk를 삽입합니다. 삽입위치는 노드의 key값과 kk값을 검색 연산과 동일한 방법으로 비교하면서 찾습니다.

이후 두가지 케이스로 나뉘게 됩니다.


💡 Case 1. 분할이 일어나지 않는 경우

리프노드가 가득차지 않았다면, 오름차순으로 kk를 삽입합니다.


💡 Case 2. 분할이 일어나는 경우

만일 리프노드에 key노드가 가득 찬 경우, 노드를 분할해야 합니다.

  1. 오름차순으로 요소를 삽입합니다. 노드가 담을 수 있는 최대 key 개수를 초과하게 됩니다.

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

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



key 삭제과정

요소를 삭제하기 위해선 1. 삭제할 키가 있는 노드 검색, 2. 키 삭제, 3. 필요한 경우, 트리 균형 조정을 해야합니다.

삭제 과정을 이해하기 위해서 몇가지 용어를 정의하였습니다.

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

💡 Case 1. 삭제할 key kk가 리프에 있는 경우

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

다른 노드들에 영향 없이 해당 kk를 단순 삭제합니다.


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

  1. 부모 key 값으로 kk를 대체합니다.
  2. 최소키 개수 이상의 키를 가진 형제 노드가 왼쪽 형제라면 가장 큰 값을, 오른쪽 형제라면 가장 작은 값을 부모key로 대체합니다.


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

  1. kk를 삭제한 후, 부모key를 형제 노드와 병합합니다.
  2. 부모노드의 key개수를 하나 줄이고, 자식 수 역시 하나를 줄여 B-Tree를 유지합니다.


Case 1.4) 자신과 형제, 부모 노드의 key 개수가 모두 최소 key 개수라면

부모노드를 루트노드로 한 부분 트리의 높이가 줄어드는 경우이기 때문에 재구조화의 과정이 일어납니다. case3의 2번 과정으로 이동합니다.


💡 Case 2. 삭제할 key kk가 내부 노드에 있고, 노드나 자식에 키가 최소 키수보다 많을 경우

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


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

삭제할 key kk가 있는 노드도 최소, 자식노드들도 최소의 key 개수를 가지므로, kk를 삭제하면 트리의 높이가 줄어들어 재구조화가 일어나는 케이스입니다. 재구조화의 과정은 다음과 같습니다.

  1. kk를 삭제하고, kk의 양쪽 자식을 병합하여 하나의 노드로 만듭니다.
  2. kk의 부모key를 인접한 형제 노드에 붙입니다. 이후, 이전에 병합했던 노드를 자식노드로 설정합니다.
  3. 해당 과정을 수행하였을 때 부모노드의 개수가 에 따라 이후 수행 과정이 달라집니다.
    3-1. 만일 새로 구성된 인접 형제노드의 key가 최대 key 개수를 넘어갔다면, 삽입 연산의 노드 분할 과정을 수행합니다.
    3-2. 만일 인접 형제노드가 새로 구성되더라도 원래 kk의 부모 노드가 최소 key의 개수보다 작아진다면, 부모 노드에 대하여 2번 과정부터 다시 수행합니다.

Case 3-3-2) 새로운 트리에서 예시



profile
내가 다시 보고 싶은 글이어야 남들도 보고 싶은 글이라 생각하며 작성합니다. 공부한 내용들을 건강하게 공유하며 함께 성장하고자 합니다😊😊

9개의 댓글

comment-user-thumbnail
2021년 1월 12일

진짜 대박입니당... 용욱쓰 파이팅!!

1개의 답글
comment-user-thumbnail
2021년 7월 11일

B 트리 관련 글 찾고 있었는데 정말 자세히 설명해주셔서 이해가 잘 됩니다! 정말 감사합니다!

답글 달기
comment-user-thumbnail
2021년 8월 12일

삭제에서 첫번째 예가 잘못 된거 아닌가용? root node가 15가 되어야 하는거 아닌가요?

답글 달기
comment-user-thumbnail
2021년 8월 31일

좋은 글 감사합니다! 너무 깔끔하게 설명이 잘 되어있네요

답글 달기
comment-user-thumbnail
2021년 9월 2일

case 3-1 에서 부모 노드가 10일 때 왼쪽 노드가 14인 경우가 있을 수 있나요??

답글 달기
comment-user-thumbnail
2022년 2월 17일

아름다운 글이네요..잘 이해가 되었습니다!

답글 달기
comment-user-thumbnail
2022년 6월 4일

노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있습니다.
노드의 키가 x개라면 자식의 수는 x+1개 입니다.

위 2조건이 서로 맞을수가 없지않나요?

답글 달기
comment-user-thumbnail
2022년 6월 14일

B트리 정리된 글중에서 너무너무 쉽게 작성해주셔서 이해가 정말 잘 됐습니다!
덕분에 시험준비도 찡긋^^

답글 달기