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

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

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

B-Tree?

B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있습니다. 최대 $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를 $k$라고 하였을 때 검색 과정입니다.

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

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

key 삽입과정

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

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

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

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

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

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

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

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

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

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

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

key 삭제과정

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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