[자료 구조] B Tree와 데이터베이스에서의 활용법

November 20, 2023

B Tree

b tree

m=4일 때, B 트리의 예

일반적으로 'B 트리'라고 언급할 때, 이는 B Tree를 지칭하는 용어입니다. B Tree는 트리 자료구조의 한 유형으로, 이진 트리를 확장하여 각 노드가 2보다 큰 자식 노드를 가질 수 있는 구조를 갖추고 있습니다.

이진 트리와는 달리 각 노드가 많은 정보를 가지거나 두 개 이상의 자식을 가질 수 있는 트리 자료구조이고 최대 M개의 자식을 가질 수 있는 트리를 B-Tree라고 합니다.

한 예시로, B-트리의 한 유형인 2-3-4 트리에서 각 노드는 2, 3, 4개의 자식을 가질 수 있으며 키는 내부 노드에 저장됩니다.

삽입 시에 노드가 꽉 차더라도 즉시 분리하지 않고, 키값과 포인터를 재분배하여 형제 노드로 이동시키는 구조
- 필요한 경우에만 키값과 포인터를 재배치
- 형제노드가 꽉 차있는 경우 노드를 분리
트리의 depth가 줄어듦
변화가 없는 트리고 깊이가 내려가면 성능상 단점이 매우 큰 경우, B* 트리를 사용하면 장점이 될 수 있음

two-to-three-split

B가 추가된 뒤, B가 들어갈 노드와 sibling 노드가 모두 full이라서 새로운 노드로 분할됨 (two-to-three-split)

b+ tree

실제 데이터는 leaf 노드에만 저장됨

B+ 트리에서는 내부 노드에는 키만 저장되고, 실제 데이터는 leaf 노드에 저장하고, leaf 노드들이 연결리스트로 연결되어 있습니다. 이로 인해 순차 검색이나 범위 검색에 효율적입니다.

B+ tree example

동작	수행
split	새로운 separator가 index set에 추가됨
concatenation	기존 separator가 index set에서 삭제되어야 함
redistribution	index set에서 separator도 같이 변화되어야 함

B+tree case1 B+tree case2

B+ delete on index set

Type	Insertion	Deletion	Lookup
Unsorted Array	O(1)	O(n)	O(n)
Sorted Array	O(n)	O(n)	O(log(n))
B tree	O(log(n))	O(log(n))	O(log(n))

구분	B-Tree	B*-Tree	B+-Tree
접근성	순차 접근이 어려움	루트 노드를 제외한 모든 노드는 1/2이상 채워져야 함	탐색을 하면서 원하는 키값의 레코드 위치 파악
탐색	중위 순회	레코드 위치는 leaf 노드에서만 파악 가능	순차접근이 용이 구간 탐색 가능
중복성	탐색 키의 중복성을 제거함	탐색 키의 중복성을 제거함	Index set과 Sequence set에 중복성이 존재
복잡성	Leaf가 아닌 노드 사이즈가 더 크고 인덱스에 대한 저장공간 관리가 복잡	삽입시 split 현상의 최소화	모든 노드의 크기가 같고 삭제될 노드가 항상 Leaf 노드에 존재 삭제가 상대적으로 단순
특징	하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 m원 탐색 트리 자료구조	공집합이거나 높이가 1 이상인 m원 탐색 트리	모든 키 값들이 leaf 노드에 정렬되어있는 트리 구조

Clustered Index
- 데이터 레코드의 저장 순서와 인덱스 내의 순서가 동일
- 하나의 테이블에는 하나의 clustered index만 존재, column별로 여러 인덱스 사용 가능

방법	Pros	Cons
Hashing	One record Lookup	구간 탐색 어려움
B Tree	Range Searching	O(log(n)) 검색 시간
Red-Black Tree	Same O(log(n)) time complexity as B-trees	Slower than B-trees in practice due to always accessing data via reference pointers.