suyeonme
[자료구조/균형트리] B-트리, B+트리란? 본문
B-트리(B-tree) 란?
B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. -- 위키피디아
방대한 양의 저장된 자료를 검색해야 하는 경우 검색어와 자료를 일일이 비교하는 방식은 비효율적이다. B-트리는 자료를 정렬된 상태로 보관한다. 트리에 노드 삽입 및 삭제시, B트리의 규칙에 맞도록 재정렬하여, 왼쪽과 오른쪽 자식의 밸런스를 항상 유지한다.
따라서 O(logN)의 시간복잡도(탐색, 삽입, 삭제)를 가진다.
최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부른다.
Balanced Tree란?
일반적으로 트리 구조를 탐색하는 경우, O(logN)의 시간복잡도를 가진다. 하지만 트리노드의 요소가 한쪽에 쏠리는 최악의 경우, O(N)의 시간복잡도를 갖게된다. 이러한 경우를 방지하기 위해서 데이터베이스의 인덱스에서는 Balanced Tree를 사용한다.
Balanced Tree란, 트리의 노드가 한방향으로 쏠리지 않도록, 노드를 삽입 및 삭제하는 경우, 규칙에 맞도록 트리를 재정렬하여 왼쪽과 오른쪽 노드의 밸런스를 항상 유지하는 트리이다. 항상 양쪽 노드의 밸런스를 유지하므로 O(logN)의 시간복잡도를 보장한다.
B-tree는 Balaned tree에 속하며, 하드 드라이브, 플래시 메모리등 방대하고 느린 데이터 접근시, 최적화된 자료구조이다.
B-Tree의 특징
- 하나의 노드에는 여러개의 데이터가 저장될 수 있으며, 각 노드내의 데이터는 항상 오름차순으로 정렬된 상태이다.
- 모든 리프 노드의 높이는 같아야한다.
- M차 B-Tree라면 루트 노드와 리프 노드를 제외하고 최소 M/2개 이상의 데이터를 가져야한다. 만약 4차 B-tree라면, 최대 4개의 데이터를 가질 수 있고 2개(4/2) 이상의 데이터를 가져야한다.
- 리프노드의 데이터 수는 M-1이하여야한다.
- 노드의 키는 최대 M-1개부터 최소 ⌈M/2⌉ - 1개의 키가 포함될 수 있다.
- 루트를 제외한 모든 노드에는 최소 t-1 개의 키가 포함되어야 한다. 루트는 최소 1개의 키를 포함할 수 있다.
- 모든 노드(루트 포함)에는 최대 (2*t-1) 개의 키만 포함할 수 있다.
- 노드의 자식 수는 노드에 있는 키 수에 1을 더한 값이다.
- B-Tree에 노드를 삽입하는 것은 리프 노드에서만 발생한다.
- 이진트리는 노드 삽입시, 하향식으로 구성되지만, B-Tree는 일반적으로 상향식으로 구성된다.
B-Tree의 장점
- 하나의 노드에 여러개의 데이터를 저장함으로써, 트리의 높이를 줄였다. 높이가 낮은 트리는 디스크 I/O, 검색 및 데이터 삽입시에도 성능이 더 빠르다.
- B-Tree는 삽입, 삭제, 검색과 같은 기본 작업에서 시간 복잡성이 O(log N)로 보장되므로 대규모 데이터 세트 및 실시간 애플리케이션에 적합하다.
- 데이터 저장시, 효율적으로 스토리지를 사용할 수 있다.
B-Tree 데이터 검색
찾으려는 값보다 더 큰값이 있는 위치의 인덱스를 가진 자식 노드로 이동한다. 만약 이러한 자식노드가 없다면, 데이터 수만큼 이동한다.
B+ Tree란?
B-Tree에서 확장된 개념으로, 리프 노드를 제외하고는 값을 담지 않는 트리이다.
리프 노드에만 데이터를 저장하기때문에, 메모리를 더 많이 확보한다. 따라서 더 많은 key를 담을 수 있으며, 이러한 특징으로 트리의 높이를 낮출 수 있다. 트리의 높이가 낮을수록 cache hit을 높일 수 있으므로 데이터 탐색이 빠르다.
B+트리는 리프 노드를 순차적으로 연결하는 포인터 집합을 가지고 있다. 인덱스된 순차 파일 처리시, 포인터를 이용하여 키, 값을 일일이 비교하지 않고 다음 데이터에 접근해서 빠르게 처리할 수 있다.
풀 스캔(Full scan)시, B+Tree는 리프노드에 데이터가 있기 때문에 선형탐색을 할 수 있어서, B+트리보다 빠르다.
B+Tree의 특징
- 모든 key, data가 리프 노드에 저장된다.
- 모든 리프 노드는 Linked List로 연결된다. 따라서 리프 노트에서 선형검색으로 데이터를 탐색할 수 있어서 빠르다.
- 리프노드의 부모 key는 리프 노드의 첫번째 key보다 작거나 같다.
- 데이터 삭제시, 리프 노드에서만 키, 값을 삭제한다.
B-Tree vs B+Tree
| B-Tree | B+Tree | |
| 데이터 저장 | - 리프 노드, 브랜치 노드 모두 데이터 저장 가능 - 각 노드에 key, data 저장 가능 |
- 리프 노드에만 저장 가능 - 각 노드에 key, 리프노드에 모든 데이터 저장 |
| 검색 속도(Full Scan) | 모든 노드 탐색 | 리프 노드에서 선형 탐색 |
| 키 중복 | 없음 | 있음(리프노드에 모든 데이터를 저장하기 때문) |
| 리프 노드 | - | 모든 리프노드가 Linked List로 연결되어 순자 접근에 용이함 |
| 삽입/제거 | 각 노드에서 수행 | 리프 노드에서만 수행 |
참고 자료
'프로그래밍👩🏻💻 > 자료구조' 카테고리의 다른 글
| [자료구조] 우선순위 큐(Priority Queue) (0) | 2022.11.06 |
|---|---|
| [자료 구조] 그래프(Graph) (0) | 2022.07.28 |
| [자료 구조] 해시테이블(Hash Table) (0) | 2022.07.10 |
| [자료 구조] 트리(Tree) (0) | 2022.07.10 |
| [자료 구조] 연결 리스트(Linked list) (0) | 2022.07.09 |
