1. B-Tree

📍개념

Balanced Tree

항상 log(N)의 검색 성능

이진 트리를 확장해, 트리의 균형을 맞춰주는 것이 B트리의 핵심 기능이다.

정렬된 순서를 보장하고, 멀티레벨 인덱싱을 통한 빠른 검색을 할 수 있기 때문에 DB 에서 사용되는 자료구조 중 하나이다.

(실제 DB에서는 B트리에서 발전된 B+트리를 사용함.)

📍특징

B트리는 이진트리와 다르게 하나의 노드가 많은 정보를 가질 수 있다. 최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 하며

다음과 같은 특징을 갖는다.

• 노드는 최소 M/2개 부터 최대 M개 까지의 자식을 가질 수 있다.
• 노드에는 최소 [M/2]−1개부터 최대 M-1개의 키가 포함될 수 있다.
• 노드의 키가 x개라면 자식 노드의 수는 x+1개 이다.
• 루트 노드는 항상 2개 이상의 자식 노드를 갖는다.(루트 노드가 리프 노드인 경우 제외)

ex) 차수가 3인 B트리(최대 2개의 키를 포함할 수 있다.)

파란색 부분은 각 노드의 key를 나타내고, 빨간색 부분은 자식 노드들을 가리키는 포인터이다.

정렬방식은 이진 탐색 트리와 동일하게 오른쪽으로 갈수록 큰 값을 가진다.

📍동작

key 검색 과정

루트노드에서 시작하여 하향식으로 검색을 수행한다. (이진 탐색 트리의 검색 과정과 동일하기에 자세한 설명 생략)

key 삽입 과정

🔍 Case 1. 분할이 일어날 경우

리프노드에 key노드가 가득 찼다면, 노드를 분할해야 한다.

1. 오름차순으로 요소를 삽입한다. 노드가 담을 수 있는 최대 key 개수를 초과하게 된다.
2. 중앙값에서 분할을 수행한다. 중앙값은 부모 노드로 병합하거나 새로 생성된다.
3. 부모 노드를 검사해 또 다시 가득 찼다면, 부모노드에서 위 과정을 반복한다.

🔍 Case 2. 분할이 일어나지 않는 경우

오름차순으로 요소를 삽입한다.

key 삭제 과정

용어 정리

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

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

• Case 1.1 왼쪽 또는 오른쪽 형제 노드의 key가 최소 key 개수보다 많은 경우 최소 key 개수보다 큰 쪽의 노드가 왼쪽이라면 가장 큰 값을, 오른쪽이라면 가장 작은 값을 부모 key로 대체한다.
  

• Case 1.2 형제노드의 key 개수가 최소이고, 부모노드의 key 개수가 최소개수보다 많은 경우
  1. 요소를 삭제한 후, 부모 key를 형제 노드와 병합한다.
  2. 부모노드의 key 개수를 하나 줄이고, 자식 수 역시 하나를 줄여 B트리를 유지한다.

• Case 1.3 자신과 형제, 부모 노드의 key 개수가 모두 최소 key 개수라면 부분 트리의 높이가 줄어드는 경우이기 때문에 재구조화 과정이 일어난다. Case 3.2 과정으로 이동
  

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

1. 현재 노드의 inorder predecessor 또는 inorder successor와 삭제할 k의 자리를 바꾼다.
2. 리프노드의 k를 삭제하게 되면, 리프노드가 삭제 되었을 때의 조건으로 변한다. (Case 1.2)

🔍 Case 3. 삭제할 key k가 내부 노드에 있고, 노드나 자식의 키가 최소 키 개수인 경우

key를 삭제하면 트리의 높이가 줄어들어 재구조화가 일어난다.

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

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

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

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

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

2. B+ Tree

📍B-Tree와의 차이점

동작 방식은 B-Tree와 유사하지만 리프노드가 연결리스트의 형태를 띄어 선형 검색이 가능하다.

이러한 특징 때문에 굉장히 작은 시간복잡도로 검색을 수행할 수 있다.

1. 모든 key, data가 리프노드에 모여있다. B트리는 각 노드에서 key와 data가 모두 들어갈 수 있지만 B+트리는 data가 모두 리프 노드에 존재한다.
2. 모든 리프노드가 연결 리스트의 형태를 띄고 있다. B트리는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어든다.
3. 삽입과 삭제가 모두 리프 노드에서만 이루어진다.

📍동작

key 검색 과정

B트리와 동일하다.

key 삽입 과정

💡Case 1. 분할이 일어나지 않고, 삽입 위치가 리프노드의 가장 앞 key 자리가 아닌 경우

B트리와 똑같은 삽입 과정을 수행한다.

💡Case 2. 분할이 일어나지 않고, 삽입 위치가 리프노드의 가장 앞 key 자리인 경우

삽입 후 부모 key를 삽입된 key로 갱신하고, data를 넣어준다.

💡Case 3. 분할이 일어나는 삽입과정

1. 분할이 일어나는 노드가 리프노드가 아니라면 기존 B트리와 똑같이 분할을 진행한다. 중간 key를 부모 key로 올리고, 분할한 두개의 노드를 왼쪽, 오른쪽 자식으로 설정한다.
2. 분할이 일어나는 노드가 리프노드라면 중간 key를 부모 key로 올리고, 오른쪽 노드에 중간 key를 포함하여 분할한다. 또한 리프노드는 연결리스트이기 때문에 왼쪽 자식노드와 오른쪽 자식 노드를 이어줘 연결리스트 형태를 유지한다. 해당 부분이 B트리의 분할과 다른 부분이다.

key 삭제 과정

💡 Case 1. 삭제할 key k가 index에 없고, 리프노드의 가장 처음 key가 k가 아닌경우

기존의 B트리 삭제과정과 동일하다.

💡 Case 2. 삭제할 key k가 리프노드의 가장 처음 key인 경우

삭제할 key k가 리프노드의 가장 처음 key인 경우에는 항상 k가 index 내에 존재한다.

1. 먼저 리프노드의 k를 삭제하는 과정을 수행한다. key의 개수가 최소 key의 개수라면 B트리의 삭제 과정 중 형제노드의 key를 빌려오는 경우나 부모 key와 병합하는 등 과정들은 동일하게 수행한다. 단, 리프노드를 병합할 때는 부모key와 오른쪽 자식의 처음 key가 동일하기 때문에 부모key를 가져오는 과정만 생략하고 왼쪽 자식과 오른쪽 자식을 병합한다.
2. 리프노드의 k를 삭제한 후, index내의 k를 inorder successor로 변경한다.

참고문헌

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

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

[DB] 10. B-Tree (B-트리)

B-Tree & B+ Tree 자료구조 알아보기