B+ Tree의 구조와 동작
B+ Tree의 정의와 기본 속성
B+ Tree는 다음과 같은 특성을 만족하는 rooted tree이다.
- 모든 root에서 leaf node까지의 경로 길이는 동일하다. (균형 트리, balanced tree)
- root와 leaf node가 아닌 모든 노드는 ⎡n/2⎤ 이상 n 이하의 자식 노드를 가진다. (⎡X⎤-> upper bound)
- leaf node는 ⎡(n-1)/2⎤ 이상, (n-1) 이하의 값을 가진다.
- 특수한 경우:
- root가 leaf node가 아니라면 최소 2개의 자식 노드를 가진다.
- root가 leaf node라면(트리에 다른 노드가 없다면) 0개에서 (n-1)개 값까지 가질 수 있다.
B+ Tree Node의 구조
각 node는 다음과 같이 구성된다.
- Ki: search-key 값들 (정렬되어 있음, K1 < K2 < ... < Kn-1)
- Pi: pointer들
- non-leaf node에서는 자식 node를 가리키는 포인터
- leaf node에서는 실제 record 또는 record bucket을 가리키는 포인터
Leaf Node의 특성
- Pi(0 < i < n)는 search-key 값 Ki를 가지는 record를 가리킨다.
- Li, Lj가 leaf node이고 i < j라면, Li의 search-key 값들은 Lj의 search-key 값보다 항상 작거나 같다.
- Pn은 search-key 순서상 다음 leaf node를 가리킨다(leaf node끼리 연결 리스트 구조).
Non-Leaf Node의 특성
- non-leaf node들은 leaf node에 대한 multi-level sparse index 역할을 한다.
- m개의 pointer를 가진 non-leaf node에서:
- P1이 가리키는 subtree의 모든 key는 K1보다 작다.
- 2 ≤ i ≤ n-1에 대해, Pi가 가리키는 subtree의 모든 key는 Ki-1 이상 Ki 미만이다.
- Pn이 가리키는 subtree의 모든 key는 Kn-1 이상이다.
B+ Tree 예시 (n=6)
- leaf node는 3~5개의 값을 가져야 한다(⎡(n-1)/2⎤ ~ n-1, n=6).
- root를 제외한 non-leaf node는 3~6개의 자식 node를 가져야 한다(⎡n/2⎤ ~ n, n=6).
- root는 최소 2개의 자식 node를 가져야 한다.
B+ Tree의 일반적 특성
- node들은 pointer로 연결되어 있으므로 논리적으로 가까운 block이 물리적으로 가까울 필요는 없다.
- non-leaf node들은 sparse index의 계층 구조를 이룬다.
- B+ Tree는 비교적 적은 수의 level을 가진다.
- root 아래 level: 최소 2*⎡n/2⎤ 값
- 그 다음 level: 최소 2⎡n/2⎤⎡n/2⎤ 값
- file에 K개의 search-key 값이 있다면, tree의 높이는 최대 ⎡log⎡n/2⎤(K)⎤이다.
- 검색 비용은 tree의 높이와 동일하다.
B+ Tree에서의 검색
기본 검색 알고리즘
function find(v)
C=root
while (C is not a leaf node)
Let i be least number s.t. V <= Ki.
if there is no such number i then Set C = last non-null pointer in C
else if (v = C.Ki ) Set C = Pi +1
else set C = C.Pi
if for some i, Ki = V then return C.Pi
else return null /* no record with search-key value v exists. */
B+ Tree에서의 범위 쿼리
- 범위 쿼리는 주어진 범위 내의 search-key 값을 가진 모든 record를 찾는다.
- 실제 구현에서는 iterator interface를 제공하여 next() 함수로 하나씩 record를 반환한다.
B+ Tree의 노드 크기와 성능
- node는 일반적으로 디스크 block과 같은 크기(4KB)로 할당된다.
- n은 보통 100 정도(인덱스 엔트리당 40바이트).
- 1백만 개 search-key 값, n=100일 때, root에서 leaf node까지 최대 4개 node만 접근하면 된다.
- 이는 balanced binary tree(1백만 key에 약 20개 node 접근)와 비교해 매우 효율적이다.
- 각 node 접근마다 디스크 I/O가 필요하므로, B+ Tree의 낮은 높이는 큰 장점이다.
Non-Unique Key 처리
- search key ai가 유일하지 않다면, (ai, Ap) 형태의 composite key로 인덱스를 만든다.
- Ap는 primary key, record ID 등 유일성을 보장하는 속성
- ai = v 검색은 composite key의 범위 검색((v, -∞) ~ (v, +∞))으로 처리
- clustering index라면 sequential하게 접근, non-clustering index라면 각 record마다 추가 I/O 발생
B+ Tree의 삽입 연산
record가 파일에 이미 추가된 상태에서, ptr을 해당 record의 포인터, k를 search key라 하자.
k가 들어갈 leaf node를 찾는다.
- leaf node에 공간이 있으면 (k, ptr) 쌍을 삽입
- 공간이 없으면 leaf node를 분할(split)한다.
- n개의 (search-key, pointer) 쌍을 정렬
- 처음 ⎡n/2⎤개는 원래 node에, 나머지는 새 node에
- 새 node를 p라 하고, p의 최소 key 값을 k라 하자. (k, p)를 부모 node에 삽입
- 부모 node가 가득 차면 부모도 분할, 이 과정을 위로 propagate
- 최악의 경우 root까지 분할되어 tree 높이가 1 증가
B+ Tree Insertion – Internal Node Split
Non-leaf node split 과정
이미 가득 찬 internal node N에 (k, p) 쌍을 삽입해야 할 때, non-leaf node split은 다음과 같이 진행된다.
- N을 메모리의 임시 버퍼 공간 M에 복사한다.
- (k, p) 쌍을 M에 삽입한다.
- M에서 P₁, K₁, ..., K⎡n/2⎤₋₁, P⎡n/2⎤까지를 다시 디스크 상의 node N에 쓴다.
- M에서 P⎡n/2⎤₊₁, K⎡n/2⎤₊₁, ..., Kₙ, Pₙ₊₁까지를 새롭게 할당된 node N'에 쓴다.
- K⎡n/2⎤와 N'에 대한 포인터를 부모 node에 삽입한다.
예시
- 기존 internal node가 가득 찬 상태에서 split이 발생하면, 키와 포인터들이 반으로 나뉘어 새로운 internal node가 생성되고, 부모 node에 중간 키가 삽입된다.
- 그림에서 Califeri가 중간 키로 올라가고, 기존 자식들이 두 그룹으로 나뉜다.
B+ Tree Insertion – Leaf Node Split
Leaf node split 과정
새로운 값(예: 'Adams')을 삽입할 때 대상 leaf node가 가득 차 있다면 split이 발생한다.
- 삽입할 위치를 찾아 leaf node에 삽입 시도
- leaf node가 가득 차 있으므로 split 필요
- 기존 leaf node의 값을 반으로 나누어 두 개의 leaf node로 분리
- 예시: [Brandt, Califeri, Crick] + Adams → [Adams, Brandt], [Califeri, Crick]
- 두 leaf node를 연결하고, 부모 node에 split된 leaf node의 첫 번째 키(Califeri)를 삽입
- 부모 node도 가득 차면 추가 split이 전파될 수 있음
예시
- 'Adams' 삽입 시, [Brandt, Califeri, Crick] leaf node가 split되어 [Adams, Brandt], [Califeri, Crick]이 된다.
- split된 leaf node의 첫 번째 키(Califeri)가 부모 internal node로 복사된다.
- 트리 구조가 유지되도록 internal node와 leaf node가 모두 업데이트된다.
B+ Tree Insertion 예시: 'Lamport' 삽입 과정
1단계: 삽입 위치 탐색 및 leaf node split 필요
- 'Lamport'를 삽입하기 위해 leaf node [Gold | Katz | Kim ]에 접근한다.
- 해당 leaf node가 이미 가득 차 있으므로 split이 필요하다.
- split 결과, [Gold | Katz]와 [Kim | Lamport ] 두 개의 leaf node로 분리된다.
- leaf node split 시, 부모 node에 새로운 key('Kim')와 pointer가 추가되어야 한다.
2단계: 부모 internal node split
- 부모 internal node [Califeri | Einstein | Gold | Kim]도 가득 차 있으므로 split이 필요하다.
- split 결과, [Califeri | Einstein]과 [Gold | Kim] 두 개의 internal node로 분리된다.
- 중간 key('Gold')가 상위 root node로 올라간다.
3단계: 트리 구조 재조정
- root node가 [Mozart]에서 [Gold | Mozart]로 확장된다.
- 전체 트리 구조가 균형을 유지하도록 internal node와 leaf node가 재배치된다.
- 최종적으로 leaf node들은 [Adams | Brandt], [Califeri | Crick], [Einstein | El Said], [Gold | Katz], [Kim | Lamport | Mozart], [Singh], [Srinivasan | Wu]로 구성되고, internal node와 root node가 새롭게 연결된다.
요약
- leaf node split이 발생하면, 그 영향이 부모 internal node, 나아가 root node까지 전파될 수 있다.
- split 과정에서 중간 key가 상위 node로 올라가고, 트리의 균형이 항상 유지된다.
- B+ Tree는 삽입 시에도 항상 모든 root-to-leaf 경로의 길이가 동일하게 유지된다.
B+ Tree에서의 삭제 연산
삭제 기본 과정
B+ Tree에서 record가 이미 file에서 삭제된 상황을 가정하자. 삭제된 record의 key를 K, pointer를 Ptr이라고 할 때, 삭제 연산은 다음과 같이 진행된다:
- leaf node에서 (K, Ptr) 쌍을 제거한다.
- 만약 node가 너무 적은 entry를 가지게 되어 sibling에 맞출 수 있다면, sibling과 병합(merge)한다:
- 두 node의 모든 key 값을 하나의 node(왼쪽 node)에 삽입하고, 다른 node를 삭제한다.
- 삭제된 node를 가리키는 pointer Pi와 그 parent node에서의 쌍 (Ki-1, Pi)를 재귀적으로 위의 절차를 사용하여 삭제한다.
특수 케이스 처리
만약 삭제로 인해 node가 너무 적은 entry를 가지게 되었지만, 그 entry들이 sibling에 맞지 않는 경우에는 pointer를 재분배(redistribute)한다:
- sibling에서 entry들을 재분배하여 두 node 모두 최소 개수 이상의 entry를 갖도록 한다.
- parent node에서 해당 key를 업데이트한다.
삭제의 전파
- node 삭제는 n/2 이상의 pointer를 가진 node가 발견될 때까지 상위로 전파될 수 있다.
- 만약 root node가 삭제 이후 오직 하나의 pointer만 가지게 된다면, 그 root는 삭제되고 유일한 자식이 새로운 root가 된다.
B+ Tree 삭제 예시
"Srinivasan" 삭제 예시
"Srinivasan"을 삭제할 때는 다음과 같은 과정이 진행된다:
1. leaf node에서 "Srinivasan" entry를 제거하면 underfull-node(ptr = 1 < 2)가 된다.
두 leaf node를 merge하면 부모 internal node도 underfull node가 된다.
두 부모 underfull node는 두가지 옵션이 있다
- merge
- re-distribution: 데이터를 재분배하는 경우
2. median key를 포함한 상태에서 underfull-node와 sibling 간의 merge가 필요하다.
두 부모 노드를 merge하기에는 옆 sibling node가 가득 차있으므로 merge가 불가능하다.
re-distribution을 해야되기 때문에 부모의 부모 노드인 root node의 두 포인터 사이에 있는 모든 키들을 리스트업한다(root node의 키도 포함).
3. 결과적으로, "Califieri, Einstein, Gold, Mozart"와 같이 median key를 포함하여 internal node의 구조가 변경된다.
두 포인터 사이에 있는 모든 키들을 리스트업한 후, 중앙값으로 Gold를 채택해서 Gold를 루트 노드로 옮긴다.
4. 최종 결과
"Singh" , "Wu" 삭제 예시
두 노드를 삭제할 때는 다음과 같은 과정이 진행된다:
1. leaf node에서 "Singh" , "Wu" 2개의 entry를 제거하면 underfull-node(ptr = 1 < 2)가 된다.
삭제 후 underfull node가 발생하지만, sibling과 병합이 불가능한 경우이다.
"Gold, Katz, Kim, Mozart" 형태로 key를 재분배한다.
2. lnternal node에서 포인터와 key를 업데이트한다
중앙값을 kim으로 잡고 kim을 internal node로 올리고, 다시 재분배한다.
internal node에서 포인터와 key를 업데이트한다. 이를 통해 tree의 균형을 유지한다.
"Gold" 삭제
"Gold"를 삭제하는 경우 다음과 같은 변화가 발생한다:
1. leaf node에서 "Gold" entry가 제거된다.
제거 이후 해당 node가 underfull(ptr = 1 < 2)이 된다.
underfull node가 sibling과 merge된다.
2. 상위 internal node에서도 merge가 발생하여 구조가 변경된다.
마지막 leaf노드가 없어지므로, 상위 internal node에서도 underfull node가 되어 merge가 발생하여 구조가 변경된다.
결과적으로 tree의 구조가 단순화된다.
3. root node도 underfull node(< 2)가 되어 삭제된다.
이러한 과정을 통해 B+ Tree는 삭제 연산 이후에도 항상 balanced tree의 특성을 유지하며, 모든 leaf node를 같은 깊이에 유지한다.
삭제 연산이 cascading되어 tree의 높이가 감소하는 경우다.
B+ Tree와 B-Tree의 비교
B-Tree와 B+ Tree는 같은 데이터에 대해 다른 구조를 가진다. 두 구조의 차이점은 다음과 같다:
B-Tree 구조 특징
- 모든 node(내부 node와 leaf node)에 key와 data record에 대한 직접 포인터를 모두 저장한다.
- 트리 내 어떤 level에서도 key를 발견하면 바로 해당 record에 접근할 수 있다.
- 예시 트리에서 [Einstein, Katz, Singh] 같은 internal node에서도 직접 record에 연결된다.
B+ Tree 구조 특징
- data record에 대한 포인터는 오직 leaf node에만 저장된다.
- internal node는 순수하게 인덱스 역할만 수행한다.
- leaf node들은 linked list로 연결되어 범위 검색에 효율적이다.
- Root node [Mozart], internal nodes [Einstein, Gold], [Srinivasan]과 leaf nodes로 구성된다.
검색 과정 비교
- B-Tree: key를 찾는 즉시 해당 record에 직접 접근할 수 있어 단일 레코드 검색이 빠르다.
- B+ Tree: key를 찾기 위해 항상 leaf node까지 내려가야 하지만, 범위 검색과 순차 접근에 유리하다.
갱신 연산의 복잡도
삽입/삭제 비용 분석
- 단일 항목의 삽입 및 삭제 비용(I/O 연산 횟수)은 트리의 높이에 비례한다.
- K개의 항목과 최대 fanout이 n일 때, 최악의 경우 삽입/삭제 복잡도는 O(log⎡n/2⎤(K))이다.
- 실제로는 I/O 연산 횟수가 더 적다:
- internal node들은 버퍼에 있는 경향이 있다.
- split/merge는 드물게 발생하며, 대부분의 삽입/삭제 연산은 leaf node만 영향을 준다.
- 평균 node 점유율은 삽입 순서에 따라 달라진다: 무작위 삽입 시 2/3, 정렬된 순서로 삽입 시 1/2이다.
B+ Tree 파일 구성 (B-Tree와의 비교)
기본 개념
- B+ Tree 파일 구성에서는 leaf node가 포인터 대신 실제 record를 저장한다.
- 삽입/삭제/갱신이 있어도 데이터 record를 클러스터링 상태로 유지하는 데 도움이 된다.
- leaf node는 여전히 최소 반(half full) 이상 채워져야 한다.
- 삽입과 삭제는 B+ Tree 인덱스의 항목 삽입/삭제와 동일한 방식으로 처리된다.
공간 활용 최적화
- 포인터보다 record가 더 많은 공간을 차지하므로 공간 활용도가 중요하다.
- 공간 활용도를 향상시키기 위해 split과 merge 중 더 많은 sibling node를 재분배에 포함시킨다.
- 왼쪽 및 오른쪽 sibling 모두 재분배에 참여
- 이로 인해 각 node는 최소 2n/3 항목을 갖게 된다.
인덱싱 관련 기타 이슈
Record 재배치와 secondary 인덱스
- record가 이동하면 record 포인터를 저장하는 모든 secondary 인덱스를 업데이트해야 한다.
- B+ Tree 파일 구성에서 node split은 매우 비용이 많이 든다.
- 해결책: secondary 인덱스에 record 포인터 대신 B+ Tree 파일 구성의 search key를 사용한다.
- B+ Tree 파일 구성 search key가 unique하지 않은 경우 record-id 추가
- record를 찾기 위해 파일 구성을 추가로 탐색해야 함
- 쿼리 비용은 높아지지만 node split은 저렴하다.
문자열 인덱싱
가변 길이 문자열을 key로 사용할 때 고려사항:
- 가변 fanout 발생
- 포인터 수가 아닌 공간 활용도를 split 기준으로 사용
접두사 압축(prefix compression) 기법:
- internal node의 key 값은 전체 key의 접두사일 수 있다.
- 서브트리를 구분할 수 있는 충분한 문자만 유지
- 예: "Silas"와 "Silberschatz"는 "Silb"로 구분 가능
- leaf node의 key는 공통 접두사를 공유하여 압축할 수 있다.
Bulk Loading 및 Bottom-Up Build 구축
효율적인 대량 데이터 로딩
- B+ Tree에 항목을 하나씩 삽입하면 항목당 약 1 I/O가 필요하다.
- leaf level이 메모리에 맞지 않는다고 가정
- 대량의 항목을 한 번에 로드할 때 매우 비효율적일 수 있다.
대안 1: 정렬 후 삽입
- 먼저 항목을 정렬한다(효율적인 외부 메모리 정렬 알고리즘 사용).
- 정렬된 순서로 삽입한다.
- 삽입은 기존 페이지로 이동하거나 split을 발생시킨다.
- I/O 성능이 크게 향상된다.
- 그러나 대부분의 leaf node가 절반만 채워진다.
대안 2: 상향식 B+ Tree 구축
- 앞서와 같이 항목을 정렬한다.
- leaf level부터 시작하여 계층별로 트리를 생성한다.
- 대부분의 데이터베이스 시스템에서 구현되어 있다.
반응형
댓글