블로그 이사했습니다
아래에서 해당 글을 보실 수 있습니다.
[자료구조] B-트리(B-Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정 - 코드 연
보통 B트리라고 하면 B- 트리를 의미한다. B 트리는 트리 자료구조의 일종으로 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.
code-lab1.com
B- 트리란?
보통 B 트리라고 하면 B- 트리를 의미한다. B 트리는 트리 자료구조의 일종으로 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.
이러한 B 트리의 다음과 같은 특징을 그림과 함께 알아보자.
1. 노드에는 2개 이상의 데이터(key)가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다.
[그림 1]처럼 한 노드에 2개, 3개의 데이터가 들어가 있을 수 있으며, 항상 정렬된 상태로 저장된다.
2. 내부 노드는 ceil(M/2) ~ M개의 자식을 가질 수 있다. 최대 M개의 자식을 가질 수 있는 B 트리를 M차 B트리라고 한다.
[그림 1]은 3차 B트리를 나타낸다. ceil() 함수는 올림 함수를 뜻한다. 즉, ceil(3/2) = 2이다.
즉, 3차 B트리의 리프 노드와 루트 노드를 제외한 내부 노드는 2개~3개의 자식을 가질 수 있다.
3. 특정 노드의 데이터(key)가 K개라면, 자식 노드의 개수는 K+1개여야 한다.
[그림 2]를 보자. 특정 노드의 데이터가 2개면 자식 노드는 3개이고, 특정 노드의 데이터가 1개면 자식 노드는 2개이다.
4. 특정 노드의 왼쪽 서브 트리는 특정 노드의 key 보다 작은 값들로, 오른쪽 서브 트리는 큰 값들로 구성된다.
B-트리는 노드 내에 key값이 2개 이상 들어갈 수 있기 때문에 자식 노드를 가리키는 포인터의 개수는 key의 개수보다 1개 더 많다. 따라서, 노드 내에서 key가 a1, a2, a3... 등으로 존재한다면, a1 왼쪽 서브 트리는 a1보다 작아야 하고, a1과 a2 사이의 서브 트리는 a1보다는 크면서 a2보다는 작아야 한다.
예를 들어 [그림 4]를 보자. 10의 왼쪽 서브 트리는 10보다 작은 값이 위치한다. (10, 21) 사이의 서브 트리는 10보다는 크지만 21보다는 작은 값들이 위치한다.
5. 노드 내에 데이터는 ceil(M/2)-1개부터 최대 M-1개까지 포함될 수 있다.
3차 B트리는 노드 내에 1~2개의 데이터를 가질 수 있다.
6. 모든 리프 노드들이 같은 레벨에 존재한다.
모든 리프 노드들은 같은 레벨에 존재해야 한다. 즉, 루트 노드에서 모든 리프 노드로 가는 경로의 길이가 같다.
혹시라도 리프 노드, 이진트리 등의 트리 관련 용어에 대해 잘 모르겠다면 다음을 참고하자.
[자료구조] 트리(Tree)의 개념 | 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐
트리(Tree)의 개념 트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같은 특징들을
code-lab1.tistory.com
B- 트리 탐색 과정
B- 트리는 루트 노드에서 탐색을 시작하여 하향식으로 탐색을 진행한다. 찾고자 하는 값이 K라면 다음과 같은 과정을 거친다.
1. 루트 노드에서 탐색을 시작한다.
2. K를 찾았다면 탐색을 종료한다.
3. K와 노드의 key값을 비교해 알맞은 자식 노드로 내려간다.
4. 해당 과정을 리프 노드에 도달할 때까지 반복한다.
5. 리프 노드에서도 K를 찾지 못한다면 트리에 값이 존재하지 않는 것이다.
예를 들어 다음과 같은 과정을 살펴보자
위와 같은 B- 트리에서 16을 찾는다고 하자.
가장 먼저 루트 노드에서 K와 key값들을 비교한다. 그 결과 16은 10과 21 사이의 값이기 때문에 10과 21 사이의 자식 포인터를 타고 내려간다.
마지막으로 리프 노드에서 해당 값을 탐색해서 16을 찾아낸다.
B- 트리 삽입 과정
B- 트리에 데이터를 삽입하는 과정은 탐색과는 다르게 상향식으로 진행된다. B- 에서의 데이터 삽입은 항상 리프 노드에서 시작된다.
1. 트리가 비어있다면 루트 노드를 할당하고 K를 삽입한다.
2. 트리가 비어있지 않다면, 데이터를 넣을 적절한 리프 노드를 탐색한다.
3. 리프 노드에 데이터를 넣고 리프 노드가 적절한 상태에 있다면 종료한다.
4. 리프 노드가 부적절한 상태에 있다면 분리한다.
이때, 적절한 상태란 해당 노드의 데이터 개수가 허용 범위 안에 있는 것이다. 반대로 부적절한 상태란 해당 노드의 데이터 개수가 허용 범위를 벗어나 너무 많은 상태를 뜻한다.
역시 예시를 들어 이해해보자. 아래 B-트리는 3차 트리라고 가정한다.
Case 1 : 분리가 일어나지 않는 경우
1. 데이터를 삽입할 리프 노드를 탐색하고, 해당 노드에 데이터를 삽입한다.
2. 해당 노드가 적절한 상태에 있다면, 삽입을 종료한다.
위와 같은 B- 트리에 9를 삽입한다고 하자. 먼저 9를 넣을 노드를 탐색과정과 동일하게 탐색해서 찾는다.
K를 삽입할 리프 노드를 찾았다면, 해당 노드에 K를 삽입한다. 이때 3차 트리는 한 노드에 최대 2개의 데이터를 담을 수 있으므로 리프 노드는 적절한 상태에 있으므로 삽입 과정을 종료한다.
Case 2 : 분리가 일어나는 경우
1. 데이터를 삽입할 리프 노드를 탐색하고, 해당 노드에 데이터를 삽입한다.
2-2. 해당 노드의 왼쪽 키들은 왼쪽 자식으로, 오른쪽 키들은 오른쪽 자식으로 분리된다.
2-3. 부모 노드를 검사해 부모 노드가 부적절한 상태에 있다면 위와 같은 분리를 반복한다.
위와 같은 B- 트리에 16을 삽입한다고 하자. 먼저 16을 넣을 노드를 탐색과정과 동일하게 탐색해서 찾는다.
K를 삽입할 리프노드를 찾았다면, 해당 노드에 K를 삽입한다. 이때 3차 트리는 한 노드에 최대 2개의 데이터를 담을 수 있으므로 리프노드는 부적절한 상태에 있으므로 분리를 진행한다.
2. 15는 왼쪽 자식으로, 17은 오른쪽 자식으로 설정한다.
3. 부모 노드가 다시 부적절한 상태가 되었으므로, 분리를 진행한다.
1. 중앙값 16을 부모 노드에 삽입한다.
2. 14는 왼쪽 자식, 18은 오른쪽 자식으로 설정한다.
3. 부모 노드가 다시 부적절한 상태가 되었으므로, 분리를 진행한다.
1. 중앙값 16을 부모 노드에 삽입할 수 없으니, 새로 노드를 생성한다.
2. 10을 왼쪽 자식, 21을 오른쪽 자식으로 설정한다.
3. 모든 노드가 적절한 상태에 있으므로 삽입을 종료한다.
B- 트리 삭제 과정
B- 트리의 데이터 삭제 과정은 삽입하는 과정보다 조금 더 복잡하다. 우선 설명의 편의를 위해 다음과 같은 용어들을 임의로 정의했다.
Lmax = 현재 노드의 왼쪽 자식들 중 가장 큰 key
Rmin = 현재 노드의 오른쪽 자식들 중 가장 작은 key
Parent : 현재 노드를 가리키는 부모 노드의 자식 포인터 오른쪽에 있는 key. 단, 마지막 자식 노드의 경우는 부모의 마지막 key.
K : 삭제할 key
위에서 살펴봤듯이, M차 트리는 다음과 같은 조건을 만족해야 한다.
- 내부 노드는 M/2 ~ M개의 자식을 가질 수 있다.
- 각 노드는 floor(M/2)-1 ~ M-1 개의 데이터(key)를 가질 수 있다.
- 노드의 key가 K개 라면 자식 노드의 개수는 K+1 개여야 한다.
노드를 삭제하는 과정 중 이러한 조건이 위반되면 조건에 맞도록 트리를 재구조화시켜야 한다.
3차 트리를 예시로 들어보자. 1~3개의 자식을 가질 수 있고, 0~2개의 key 값을 가질 수 있다. 이 조건을 최소 유지 개수라고 부르겠다.
3차 트리에서의 삭제 과정을 다음과 같은 Case들로 나누어 살펴보자.
Case 1. 리프 노드에서 삭제
Case 1-1) 리프 노드에서 값을 삭제하더라도 최소 유지 개수 조건을 만족하는 경우
-> 이 경우 바로 노드를 삭제해주면 된다.
위와 같은 경우 16을 제거하더라도 최소 유지 개수를 만족하므로 바로 제거하면 된다.
Case 1-2) 리프 노드에서 값을 삭제할 때, 최소 유지 개수를 만족하지 못하지만 바로 옆 형제 노드들에게 값을 빌려올 수 있는 경우
-> 이 경우 K를 Parent와 바꿔준다. 이후 왼쪽 형제 노드에게서 값을 빌려올 수 있다면 Lmax와 Parent를, 오른쪽 형제에게서 값을 빌려올 수 있다면 Rmin과 Parent를 바꿔주면 된다. 둘 다 가능하면 하나를 선택하면 된다.
위와 같은 경우 19를 제거하게 되면, (14,17)의 자식 노드의 개수는 3개여야 하는 조건을 위반하게 된다. 하지만 이때 왼쪽 형제 노드에게서 값을 빌려올 수 있다.
가장 먼저 K를 Parent로 바꿔준다. 여기서 19는 마지막 자식이었으므로 (14,17) 중 마지막 key인 17이 Parent가 된다.
왼쪽 형제에게서 값을 빌릴 수 있으므로, Lmax와 Parent를 바꿔준다.
제거가 완료되었다. 최소 유지 개수를 만족한다.
Case 1-3) 리프 노드에서 값을 삭제할 때, 최소 유지 개수를 만족하지 못하고 형제 노드들에게 값을 빌려올 수 없지만, 부모 노드를 분할할 수 있을 때
-> K를 삭제하고, Parent를 부모 노드에서 분할하여 형제 노드에 합친다. 이렇게 하면 부모 노드의 key가 하나 줄고, 자식 노드의 수도 하나 줄어들어 최소 유지 개수를 만족한다.
위와 같은 경우 22를 삭제하면 (23,28)의 자식 수가 2개가 되어 최소 유지 개수를 만족하지 못한다.
이때 Parent를 분할하여 형제 노드에 합치면 된다.
22의 제거가 완료되었다.
Case 1-4) 리프 노드에서 값을 삭제할 때, 최소 유지 개수를 만족하지 못하고, 형제 노드들에게 값을 빌려올 수 없고 부모 노드도 분할할 수 없을 때
-> 이 경우는 Case 2-2)의 경우와 동일하므로 뒤의 설명을 참고하자.
Case 2. 리프 노드가 아닌 내부 노드에서 삭제
Case 2-1) 내부 노드에서 값을 삭제할 때, 현재 노드 혹은 자식 노드의 최소 유지 개수의 최소보다 큰 경우
-> 이 경우 K의 Lmax 혹은 Rmin과 자리를 바꿔준다. 이후 리프 노드에서의 K 삭제와 과정이 동일하다.
위와 같은 경우 21을 삭제하면, 자식 노드의 개수가 2개여야 하는데 3개로 너무 많다.
이 경우 K의 Lmax인 19와 바꾸거나, Rmin인 22와 값을 바꾸면 된다. 이후는 리프 노드에서의 삭제와 과정이 동일하므로 생략한다.
Case 2-2) 내부 노드에서 값을 삭제할 때, 현재 노드와 자식 노드 모두 key 개수가 최소인 경우
-> 이 경우 다음과 같은 트리의 재구조화가 필요하다.
1. K를 삭제하고 K의 자식을 하나로 합친다. 합쳐진 노드를 N1이라고 하자.
2. K의 Parent를 K의 형제 노드에 합친다. 합쳐진 노드를 N2라고 하자.
3. N1을 N2의 자식이 되도록 연결한다.
4-1. 만약 N2의 key수가 최대보다 크다면 key 삽입 과정과 동일하게 분할한다.
4-2. 만약 N2의 key수가 최소보다 작다면 2번 과정으로 돌아가서 동일한 과정을 반복한다.
위와 같은 경우 4를 제거하면 현재 노드 및 자식 노드들의 최소 유지 개수를 만족할 수 없다.
K의 자식 노드를 모두 합쳐준다(N1)
K의 Parent인 10을 형제 노드에 합쳐준다(N2). 또한 N1을 N2의 자식으로 연결해준다. 위 B-트리는 3차 트리라고 가정했는데, key의 개수가 3개로 너무 많다. 따라서 분할을 진행한다.
key의 개수가 너무 많을 때 분할하는 방법은 삽입 과정에서 설명했으므로 생략한다.
B- 트리 시뮬레이션
아래 사이트를 이용하면 B- 트리에 데이터가 삽입되고 삭제되는 과정을 눈으로 확인할 수 있다.
https://www.cs.usfca.edu/~galles/visualization/BTree.html
B-Tree Visualization
www.cs.usfca.edu
참고
'Computer Science > [자료구조]' 카테고리의 다른 글
| [자료구조] 레드-블랙 트리(Red-Black Tree)란? | 레드-블랙 트리 쉽게 이해하기 (7) | 2021.12.31 |
|---|---|
| [자료구조] AVL트리란? AVL트리 쉽게 이해하기, AVL트리 시뮬레이터 (6) | 2021.12.29 |