B-트리

🟩 균형 탐색 트리

이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조

키의 개수 (t-1)~(2t-1) 개

자식 노드의 개수 t~2t 개

 

🟩 성질

1. 노드에는 2개 이상의 데이터가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다.

2. 내부 노드는 ceil(m/2) ~ m 개의 자식을 가질 수 있다. 최대 m개의 자식을 가질 수 있는 B트리를 m차 B트리라 한다.

 

ceil() 함수는 올림 함수이다. 즉, ceil(3/2) = 2이다.

즉, 3차 B트리의 리프 노드와 루트노드를 제외한 내부 노드는 2-3개의 자식을 가질  수 있다.

 

3. 특정 노드의 데이터(key)가 K개라면, 자식 노드의 개수는 K+1개여야 한다.

특정 노드의 데이터가 2개라면, 자식 노드는 3개이고, 특정 노드의 데이터가 1개이면, 자식 노드는 2개이다.

 

4. 특정 노드의 왼쪽 서브 트리는 특정 노드의 key보다 작은 값들로, 오른쪽 서브 트리는 큰 값들록 구성된다.

B-트리는 노드 내에 key 값이 2개 이상 들어갈 수 있기 때문에 자식 노드를 가리키는 포인터의 개수는 key의 개수보다 1개 더 많다. 따라서, 노드 내에서 key가 a1, a2, a3 등으로 존재한다면, a1의 왼쪽 서브 트리는 a1보다 작아야 하고, a1과 a2 사이의 서브 트리는 a1보다는 크면서 a2보다 작아야 한다.

10의 왼쪽 서브트리는 10보다 작은 값이 위치한다. (10, 21) 사이의 서브 트리는 10보다는 크지만, 21보다는 작은 값들이 위치한다.

 

5. 노드 내에 데이터는 ceil(m/2)-1개부터 최대 m-1개까지 포함될 수 있다.

3차 B트리는 노드 내에 1-2개의 데이터를 가질 수 있다.

 

6. 모든 리프 노드들은 같은 레벨에 존재한다.

모든 리프 노드들은 같은 레벨에 존재해야 한다. 즉, 루트 노드에서 모든 리프 노드로 가는 경로의 길이가 같다.

 

🟩 탐색

루트 노드에서 탐색을 시작하여 하향식으로 탐색을 진행한다.

K(찾고자 하는 값)과 노드의 key 값을 비교해 알맞은 자식 노드로 내려간다. 

 

🟩 삽입

상향식으로 진행된다.

트리가 비어있다면 루트 노드를 할당하고 k를 삽입한다.

비어있지 않다면, 데이터를 넣을 적절한 리프 노드를 탐색한다. 리프 노드가 부적절한 상태에 있다면 분리한다.

 

적절한 상태 : 해당 노드의 데이터 개수가 허용 범위 안에 있는 것

 

1. 노드 분할이 일어나지 않는 경우

1-1. 데이터를 삽입할 리프 노드를 탐색하고, 해당노드에 데이터를 삽입한다.

2. 해당 노드가 적절한 상태에 있다면, 삽입을 종료한다.

 

B-트리에 9를 삽입한다면, 9를 넣을 노드를 탐색 과정과 동일하게 탐색해서 찾는다.

9를 삽입할 노드를 찾았다면, 해당 노드에 9를 삽입한다. 이때 3차 트리는 한 노드에 최대 2개의 데이터를 담을 수 있으므로, 리프 노드는 적절한 상태에 있기에 삽입 과정을 종료한다.

 

2. 노드 분할이 일어나는 경우

2-1. 데이터를 삽입할 리프 노드를 탐색하고, 해당 노드에 데이터를 삽입한다.

2-2. 해당 노드의 왼쪽 키들은 왼쪽 자식으로, 오른쪽 키들은 오른쪽 자식으로 분리된다.

2-3. 부모 노드를 검사해 부모 노드가 부적절한 상태에 있다면 위와 같은 분리를 반복한다.

 

B-트리에 16을 삽입한다고 하면, 먼저 16을 넣을 노드를 탐색 과정과 동일하게 찾는다.

K를 삽입할 리프 노드를 찾았다면, 해당 노드에 K를 삽입한다. 이 때, 3차 트리는 한 노드에 최대 2개의 데이터를 담을 수 있으므로 리프 노드는 부적절한 상태에 있기 때문에 분리를 진행한다.

15는 왼쪽 자식으로, 17은 오른쪽 자식으로 설정한다.

부모 노드가  다시 부적절한 상태가 되었으므로, 분리를 진행한다.

1. 중앙값 16을 부모 노드에 삽입한다.

2. 14는 왼쪽 자식, 18은 오른쪽 자식으로 설정한다.

3. 부모 노드가 다시 부적절한 상태가 되었으므로, 분리를 진행한다.

1. 중앙값 16을 부모 노드에 삽입할 수 없으니, 새로 노드를 생성한다.

2. 10을 왼쪽 자식, 21을 오른쪽 자식으로 설정한다.

3. 모든 노드가 적절한 상태에 있으므로 삽입을 종료한다.

 

🟩 삭제

Lmax = 현재 노드의 왼쪽 자식들 중 가장 큰 키

Rmin = 현재 노드의 오른쪽 자식들 중 가장 작은 키

parent = 현재 노드를 가리키는 부모 노드의 자식 포인터 오른쪽에 있는 키. 단, 마지막 자식 노드의 경우, 부모의 마지막 키

k = 삭제할 키

 

노드를 삭제하는 과정 중 트리를 재구조화시켜야 한다.

3차 트리를 예시로 들면, 2-3개의 자식을 가질 수 있고, 1-2개의 키 값을 가질 수 있다.

이것이 최소 유지 개수

 

1. 리프 노드에서 삭제

1-1. 리프 노드에서 값을 삭제하더라도 최소 유지 개수를 조건을 만족하는 경우 👉 이 경우 바로 노드 삭제해주면 된다.

 

1-2. 리프 노드에서 값을 삭제할 때, 최소 유지 개수를 만족하지 못하지만, 바로 옆 형제 노드들에게 값을 빌려올 수 있는 경우

👉 k를 parent로 바꿔준다. 이후 왼쪽 형제 노드에게서 값을 빌려올 수 있다면 Lmax와 parent를, 오른쪽 형제에게서 값을 빌려올 수 있다면 Rmin과 parent를 바꿔주면 된다. 둘 다 가능하면 하나 선택하면 된다.

위와 같은 경우 19를 제거하게 되면, (14,17)의 자식 노드의 개수는 3개여야하는 조건을 위반하게 된다. 하지만 이때 왼쪽  형제 노드에게서 값을 빌려올 수 있다.

가장 먼저 k를 parent로 바꿔준다. 여기서 19는 마지막 자식이었으므로 (14,17) 중 마지막 key인 17이 parent가 된다.

왼쪽 형제에게서 값을 빌릴 수 있으므로, Lmax와 parent를 바꿔준다.

제거가 완료되었다. 최소 유지 개수를 만족한다.

 

1-3. 리프 노드에서 값을 삭제할 때, 최소 유지 개수를 만족하지 못하고 형제 노드들에게 값을 빌려올 수 없지만, 부모 노드를 분할할 수 있을 때

👉 key를 삭제하고, parent를 부모 노드에서 분할하여 형제 노드에 합친다. 이렇게 하면 부모 노드의 key가 하나 줄고, 자식 노드의 수도 하나 줄어들어 최소 유지 개수를 만족한다.

위와 같은 경우 22를 삭제하면 (23,28)의 자식 수가 2개가 되어 최소 유지 개수를 만족하지 못한다.

이때 parent를 분할하여 형제 노드에 합치면 된다.

22의 제거가 완료되었다.

 

1-4. 리프 노드에서 값을 삭제할 때, 최소 유지 개수를 만족하지 못하고, 형제 노드들에게서 값을 빌려올 수도 없고, 부모 노드도 분할할 수 없을 때

👉 2-2와 동일하다.

 

2. 리프 노드가 아닌 내부 노드에서 삭제

2-1. 내부 노드에서 값을 삭제할 때, 현재 노드 혹은 자식 노드의 최소 유지 개수의 최소보다 큰 경우

👉 k의 Lmax 또는 Rmin과 자리를 바꿔준다. 이후 리프 노드에서의 k 삭제와 과정이 동일하다.

21을 삭제하면, 자식 노드의 개수가 2개여야 하는데, 3개로 너무 많다.

k의 Lmax인 19와 바꾸거나, Rmin인 22와 바꾼다. 이후는 리프 노드의 삭제와 과정이 동일하다.

 

2-2. 내부 노드에서 값을 삭제할 때, 현재 노드와 자식 노드 모두 key 개수가 최소인 경우

👉 이 경우 다음과 같이 트리의 재구조화가 필요하다.

 

1. k를 삭제하고 k의 자식을 하나로 합친다.

2. k의 parent를 k의 형제 노드에  합친다. 합쳐진 노드를 n2라 하자.

3. n1을 n2의 자식이 되도록 연결한다.

4-1. 만약 n2의 키 수가 최대보다 크다면 키 삽입 과정과 동일하게 분할한다.

4-2. 만약 n2의 키 수가 최소보다 작다면 2번 과정으로 도아가서 동일한 과정을 반복한다.

4를 제거하면, 현재 노드 및 자식 노드들의 최소 유지 개수를 만족할 수 없다.

k의 자식 노드를 모두 합쳐준다(n1)

k의 parent 인 10을 형제 노드에 합쳐준다(n2)

또한 n1을 n2의 자식으로 연결해준다. 예시의 b-트리가 3차 트리라 가정하면, 키의 개수가 3개로 너무 많아서 분할을 진행한다.

 

🟩 시간복잡도

O(logn)