데이터베이스에서 물리적 저장 장치에 데이터를 배치하고 접근하는 방법으로 인덱스가 있다. B-트리는 가장 대표적인 인덱스 구조이다. B-트리란 무엇일까?
📖B Tree
B-트리는 이진 트리를 확장하여 더 많은 수의 자식 노드를 가질 수 있도록 일반화한 트리 구조이다.
📁차수가 m인 B-트리의 특성
- m-원 탐색 트리(m-way search tree)이다.
차수가 m이므로 자식 노드의 수가 최대 m이다. 따라서 최대 m개의 서브 트리를 가질 수 있다.
- 루트 노드는 그 자체가 리프 노드가 아닌 이상 적어도 두개의 서브 트리를 가진다.
- 내부 노드는 최소 m/2, 최대 m개의 서브 트리를 가진다. (적어도 m/2 - 1개의 키 값을 가진다.)
- 모든 리프 노드가 같은 레벨에 있는 균형 트리이다.
다음은 3차 B-트리를 나타낸 것이다.
차수가 3이므로 내부 노드가 최소 2개의 서브 트리, 최소 1개의 키 값을 가지며, 모든 리프 노드가 같은 레벨에 있는 것을 확인할 수 있다.
📁B-트리의 노드의 구조 및 특성
- 하나의 노드는 여러 개의 키 값과 서브 트리에 대한 포인터를 갖는다.
이때, 각 키 값은 그 키 값을 가지고 있는 레코드에 대한 포인터를 함께 포함한다. 위의 3차 B-트리의 경우, 키 값과 서브 트리에 대한 포인터만 나타나 있다.
- 한 노드 안에 있는 키 값들은 오름차순으로 정렬되어있다.
- 특정 키 값의 왼쪽 포인터가 가리키는 서브 트리에 있는 모든 노드들의 모든 키 값들은 특정 키 값보다 작다.
- 특정 키 값의 오른쪽 포인터가 가리키는 서브 트리에 있는 모든 노드들의 모든 키 값들은 특정 키 값보다 크다.
📁B-트리의 삽입
B-트리는 모든 리프 노드가 같은 레벨에 있는 균형 트리이므로 새로운 키 값이 삽입되더라도 균형을 유지해야한다.
노드에 빈 공간이 있는 경우, 단순히 빈 공간에 새로운 키 값을 삽입하면 된다. 그러나, 빈 공간이 없어 오버플로우가 발생한다면 노드를 두 개로 분할해야한다.
분할하는 과정은 다음과 같다.
- 노드를 두 개로 나눈다.
- m/2번째 키 값(중간값)을 부모 노드에 삽입한다.
- 나머지 키 값은 왼쪽, 오른쪽 서브 트리에 반씩 나누어 삽입한다.
다음은 위의 3차 B-트리에서 새로운 키 값 59를 삽입하는 과정이다.
59는 60보다 작으므로 노드 o에 삽입되어야하지만 빈 공간이 없어 오버플로우가 발생한다. 이때, 노드를 두 개로 나누고, 50, 58, 59 중 중간값인 58을 부모 노드에 삽입한다. 나머지 키 값 50, 59는 각각 왼쪽 서브 트리와 오른쪽 서브 트리에 삽입한다.
이후, 새로운 키 값 57을 삽입한다면 58보다 작으므로 노드 o에 삽입해야하고, 노드 o에 빈 공간이 있으므로 그대로 삽입하면 된다.
📁B-트리의 삭제
키 값을 삭제하는 경우에도 트리의 균형은 유지되어야 한다. 따라서 삭제는 리프 노드에서 수행되어야하고, 삭제 키가 리프가 아닌 노드에 존재한다면 후행 키 값과 자리를 교환하여 키 값을 리프 노드로 보내 삭제를 수행한다.
다음은 키 값 60을 삭제하는 과정이다.
삭제 키가 리프가 아닌 노드에 존재하므로 62와 자리를 교환한 후 삭제를 진행한다.
앞서 언급한 B-트리의 특성 중 내부 노드가 적어도 m/2 - 1개의 키 값을 가진다는 특성이 있었다. 삭제를 수행하면서 키 값의 수가 m/2 - 1개보다 적어지는 것을 언더플로우라고 한다.
언더플로우가 발생하는 경우, 먼저 사용하는 방법은 재분배이다.
- 최소 키 값의 수 이상을 포함한 형제 노드에서 한 개의 키를 차출한다.
- 부모 노드의 키는 키 값이 삭제 키가 있는 자식 노드로 이동한다.
- 차출된 키는 부모 노드로 이동한다.
다음은 재분배를 사용하여 20을 삭제하는 과정이다.
3차 B-트리는 노드가 최소 1개의 키를 가져야하므로 20을 삭제하게 되면 언더플로우가 발생한다. 따라서 부모 노드의 키 26은 자식 노드 l로 이동하고, 2개의 키를 가진 형제 노드 m에서 키 30을 차출하여 부모 노드로 이동한 후 삭제를 진행한다.
언더플로우가 발생했을 때, 형제 노드들이 모두 최소의 키 수만 가진다면 어떻게 해야할까? 이때 사용하는 방법이 합병이다.
- 삽입에서 사용한 분할 과정과 정반대로 동작한다.
- 삭제 키가 있는 노드의 오른쪽(혹은 왼쪽) 형제 노드에 있는 키 값들과 부모 노드의 키 값을 합병한다.
다음은 합병을 사용하여 26을 삭제하는 과정이다.
삭제 키가 있는 노드의 오른쪽 형제 노드에 있는 키 값 36과 부모 노드의 키 값 30을 합병한다.
📖B+ Tree
B-트리에서 순차 탐색을 하는 경우, 중위 순회를 하면 모든 키 값이 정렬된 결과가 나온다. 이때, 재귀를 사용해야하므로 시간이 오래 걸리게 되고, 이러한 순차 탐색에서의 단점을 해결한 것이 B+ Tree이다.
B+ 트리는 노드를 인덱스 세트와 순차 세트로 구분한다.
- 인덱스 세트 (index set)
- 내부 노드(리프 제외 나머지 노드)이다.
- 리프에 있는 키들에 대한 경로만 제공한다.
내부 노드는 리프에 있는 키들에 대한 경로만 제공하므로 키 값을 찾기 위해서는 무조건 리프 노드까지 내려가야 한다.
- 순차 세트 (sequence set)
- 리프 노드이다.
- 모든 키 값들을 포함한다.
- 순차 탐색을 지원한다.
다음은 3차 B+ 트리이다.
📁B+ 트리의 노드의 구조 및 특성
- 루트 및 내부 노드는 여러 개의 키 값과 서브 트리에 대한 포인터를 가진다.
즉, B-트리와는 달리 키 값을 가지고 있는 레코드에 대한 포인터에 대해 저장하지 않는다.
- 리프 노드는 키 값을 가지고 있는 레코드에 대한 포인터를 가진다.
- 리프 노드는 모두 링크로 연결되어 있다.
리프 노드는 연결 리스트로 구성되므로 순차 탐색을 지원한다.
📁B-트리와의 차이점
- 인덱스 세트에 있는 키 값은 리프 노드에 있는 키 값을 찾아가는 경로를 제공하는 용도로만 사용한다.
그렇기 때문에 인덱스 세트에 있는 키 값은 사실상 모두 순차 세트에 다시 나타난다.
- 인덱스 세트의 노드와 순차 세트의 노드의 내부 구조가 서로 다르다.
인덱스 세트에 있는 노드는 키 값만 저장하고, 리프 노드는 키 값과 키 값이 저장된 레코드의 포인터도 함께 저장한다.
또한, 노드에 저장할 수 있는 키 값의 수도 다르다.
- 순차 세트의 모든 노드는 순차적으로 서로 연결된 연결 리스트로 구성되어있다.
따라서 순차 탐색을 효율적으로 진행할 수 있다.
📁B+ 트리의 삽입
B+ 트리의 삽입은 B-트리의 삽입과 유사하다. 리프 노드에 빈 공간이 있는 경우, 그대로 빈 공간에 삽입하면 된다. 그러나 리프 노드에서 오버플로우가 발생하면 분할을 사용해야한다.
리프 노드를 분할하는 과정은 다음과 같다.
- 리프 노드를 두 개의 노드로 분할하고 키 값들을 절반씩 분배하여 저장한다.
- 중간 키 값(분할된 왼쪽 노드에서 가장 큰 키 값)의 복사본을 부모 노드로 올려서 저장한다.
중간 키 값의 복사본을 부모 노드에 저장하므로 중간 키 값은 부모 노드, 분할 노드 모두에 존재하게 된다.
📁B+ 트리의 삭제
B+ 트리에서의 삭제는 리프 노드에서만 진행한다. 인덱스 세트에 삭제 키 값이 있더라도 삭제하지 않고 다른 키 값을 탐색하는 키 값으로 사용한다.
다음은 위의 3차 B+ 트리에서 키 값 43을 삭제한 이후의 트리이다.
그러나, 리프 노드에서 언더플로우가 발생한다면 B-트리와 마찬가지로 재분배, 합병을 사용한다. 이때, 재분배의 경우 인덱스 세트의 키 값을 변경하고, 합병의 경우 인덱스 세트의 키 값을 삭제한다.
다음은 재분배를 사용하여 키 값 125를 삭제한 이후의 트리이다.
125를 삭제하면 언더플로우가 발생하게 되므로 형제 노드의 키 값 90을 복사하여 부모 노드로 이동하고, 부모 노드의 키 값 110이 삭제 키의 노드로 이동한다.
다음은 합병을 사용하여 키 값 55를 삭제한 이후의 트리이다.
형제 노드의 키 값 35, 40과 55를 삭제한 후 남은 키 값 69를 합병하고, 부모 노드의 키 값 43은 삭제한다.
