최종 수정 : 25.1.2
m원 탐색 트리
1. 정의와 특성
최대 차수가 m인 트리로 인덱스를 만들기에 적합한 트리이다. 이진 탐색 트리의 확정된 형태로 높이를 줄이기 위해 사용한다. 루트와 단노드를 제외한 노드는 최소한 두 개의 서브 트리를 가지고, 최소 m/2 개, 최대 m 개의 서브 트리를 가진다. 각 노드의 키의 개수는 서브 트리의 개수보다 1 작다.
2. B 트리의 정의와 특성
B - 트리(Balanced tree)는 이진 트리에서 탐색 성능의 향상을 위해 단노드의 높이를 같게 한 균형 트리이다. 최대 m개의 서브 트리를 가질 수 있어 이를 m차 균형 트리(m-balanced tree)라 하여 m - 원 탐색 트리라고 한다. B 트리의 특징은 다음과 같다.
- 모든 노드의 킷값은 정렬되어 있어야 한다.
- 각 노드의 킷값은 오름차순으로 나열된다.
- 각 노드의 자노드의 개수는 최소 ┌m/2┓개, 최대 m개이다. ( ⌈ ⌉는 천장함수의 기호이며, 올림을 의미)
- 루트는 항상 두 개 이상의 자노드를 가진다. (루트가 단노드일 때는 예외)
- 각 노드의 킷값은 자노드(서브 트리) 개수보다 1 작다.
- 모든 단노드는 레벨이 같다.
3. B 트리에서의 검색 연산
검색은 루트에서 시작하여 자노드로 내려가면서 수행하는 하향식 검색을 수행한다.
4. B 트리에서의 삽입 연산
키를 삽입하는 경우 B 트리의 성질에 의해 트리의 구조가 분열되는 변경이 발생할 수 있다.
1) 분열이 발생하지 않는 경우
킷값을 포함할 여유가 있는 경우이면, 분열 없이 데이터를 삽입할 수 있다.
2) 분열이 발생하는 경우
삽입에서 분열이 발생하는 이유는 각 노드의 최대 킷값이 제한된 개수를 초과하면 분열이 발생한다. 노드 삽입 과정은 데이터를 삽입할 노드를 찾고, 데이터를 삽입 후 킷값의 초과 여부를 확인하고, 초과할 경우 가운데 값으로 노드 분할을 하여 가운데 값을 상위노드를 올리는 과정을 반복함으로써 트리 전체의 구조를 재구축한다.
5. B 트리에서의 삭제 연산
삭제 연산은 삭제할 키가 있는 노드를 찾아서 데이터를 삭제하면 된다. 그러나 각 노드를 유지하기 위한 최소한의 노드수를 지키지 못하는 경우가 발생한다. 이때는 삽입 연산과 반대로 노드 병합을 통한 트리 재구축을 수행해야 한다.
1) 삭제할 키가 단 노드에 있는 경우
- 삭제할 키가 있는 노드에 key의 개수가 최소 제한 개수보다 큰 경우
☞ 단순히 삭제한다. - 삭제할 키가 있는 노드에 key의 개수가 최소이고, 제노드의 key의 개수가 최소 이상인 경우
☞ 노드 재구축이 필요, 노드에 key가 제한 개수의 초과가 발생하면 중간값이 이동한다. - 삭제할 키가 있는 노드와 제노드의 key의 개수가 최소이고, 부노드의 key의 개수가 최소 이상인 경우
☞ 노드 재구축이 필요, 노드에 key가 제한 개수의 초과가 발생하면 중간값이 이동한다. - 삭제할 키가 잇는 노드와 제노드, 부노드의 key의 개수가 최소인 경우
☞ 노드 재구축이 필요, 노드에 key가 제한 개수의 초과가 발생하면 중간값이 이동한다.
2) 삭제할 노드가 루트나 간노드에 있는 경우
- 삭제할 키가 있는 노드와 자노드의 key의 개수가 최소 이상인 경우
☞ 노드 재구축이 필요, 노드에 key가 제한 개수의 초과가 발생하면 중간값이 이동한다. - 삭제할 키가 있는 노드와 자노드의 key의 개수가 최소인 경우
☞ 노드 재구축이 필요, 노드에 key가 제한 개수의 초과가 발생하면 중간값이 이동한다.
6. B 트리의 변형
1) B* 트리
B* 트리는 B 트리의 변형으로, B 트리에서 각 노드에 키를 1/2 이상 채우는 부분에 의해 발생하는 잦은 노드의 결합과 분해의 재구축 작업이 발생하는데 이를 해결하기 위해 제시된 트리이다. 루트가 아닌 노드는 노드의 키를 2/3 이상 채워지도록 하는 특징을 갖는다. 한 노드에 채워지는 킷값의 개수가 많아져서 노드의 결합과 분해가 기존의 B 트리보다 덜 발생한다.
- B 트리에서 각 노드의 키값을 1/2 이상 채우던 것을 2/3 이상 채우는 것으로 늘였다.
- 분열과 결합의 횟수를 줄여 성능을 향상한다.
- 루트와 단노드가 아닌 노드는 최소 서브 트리의 수 ⌈ (2m - 2) / 3 ⌉ 이다.
- 그 외의 특징은 B 트리와 같다.
2) B+ 트리
B+ 트리는 B 트리와 같은 구조로 되어 있다. 그러나 모든 킷값들은 단노드들에만 정렬되어 있고, 루트와 간노드는 인덱스의 역할을 하는 트리 구조이다. 일반적인 파일 구조 중 ISAM(Indexed Sequential Access Method) 파일의 인덱스 구성이 B + 트리를 이용한다. 단노드를 제외한 모든 노드는 인덱스 역할을 하고, 단노드는 실제 키값을 가지고 있는 구조이다. 인덱스를 통한 접근은 루트부터 키를 찾아 트리의 계층을 탐색하고, 가장 왼쪽의 단노드부터 오른쪽 끝의 단노드까지 순서대로 접근하는 순차접근이 가능하다. 단노드를 제외한 모든 노드는 인덱스 열할만 하므로 단노드로 구성된 순차셋의 킷값과 겹치는 값도 존재할 수 있다. 일반적인 B 트리와 B* 트리는 모든 킷값이 유일해야 하지만, B+ 트리는 인덱스셋과 숫차셋(데이터셋)의 분리로 인덱스와 순차셋에서 중복된 값이 나올 수 있다. 순차셋에서 중복된 값이 나올 수는 없다.
- B 트리의 구조를 그대로 가진다.
- 인덱스 셋과 순차 셋으로 구성하여 인덱스를 통한 직접접근과 단노드를 통한 순차접근이 가능하다.
- 인덱스 셋 : 루트와 간노드로 구성, 인덱스를 위한 것이므로 키가 아닌 값도 인덱스로 사용할 수 있다.
- 순차 셋 : 단노드 전체로, 왼쪽부터 오른쪽으로 오름차순 정렬이 되어있으므로 단노드를 순차 검색할 수 있다.
참고
독학사 교재
댓글