이진 탐색 트리(Binary Search Tree, BST)의 한계
이진탐색트리는 탐색, 삽입, 삭제 연산에 평균적으로 O(logN)의 시간 복잡도를 가진다.
그러나, 균형이 깨지는 경우 O(N)으로 성능이 저하가 될 수 있다.
이러한 문제를 해결하기 위해 균형 트리(Balanced Tree) 개념이 등장하였고, 그 중 다진 트리(M-way tree) 구조를 가지는 B-tree가 개발되었다.
B-tree란?
B-tree의 구조
- 노드(Node): 데이터(Key)와 포인터를 포함하는 기본 단위
- 루트 노드(Root Node): 트리의 최상위 노드
- 브랜치 노드(Branch Node): 내부 노드로, 데이터와 자식 노드를 포함
- 리프 노드(Leaf Node): 자식 노드가 없는 노드로, 실제 데이터를 저장
B-tree의 특징
- 한 노드는 M개의 자식과 (M-1)개의 키를 가질 수 있음
- 노드 내 키 값은 오름차순 정렬되어 있음
- 키 값 기준으로 좌측 서브트리는 작은 값, 우측 서브트리는 큰 값을 가짐
- 균형 유지: 모든 리프 노드가 동일한 깊이에 위치
- 검색, 삽입, 삭제 연산의 시간 복잡도: O(log N)
B-tree의 연산
https://www.cs.usfca.edu/~galles/visualization/BTree.html
여기 사이트에 들어가 직접 눈으로 확인해보면 쉽게 이해할 수 있다 🤓
1. 검색
- 루트 노드에서 키를 확인
- 찾는 값보다 작으면 왼쪽 서브트리, 크면 오른쪽 서브트리로 이동
- 리프 노드에 도달할 때까지 반복
2. 삽입
- 적절한 리프 노드 찾기
- 키를 삽입한 후, 정렬 유지
- 노드가 꽉 찬 경우, 분할 → 부모 노드로 중간 키 이동
3. 삭제
- 리프 노드에서 키를 제거
- 노드의 키 개수가 최소 키 개수보다 작아지면, 병합 또는 차용(형제 노드에서 값 빌려오기) 수행
- 균형을 유지하면서 부모 노드 조정
B+tree란?
B+tree는 B-tree의 확장 개념으로, 검색과 범위 탐색 성능을 더욱 향상시킨 구조
B-tree와 달리 브랜치 노드에는 키 값만 저장하고, 리프 노드에서만 데이터(value)를 저장한다.
또한, 리프 노드들이 Linked List로 연결되어 있다.
데이터베이스 엔진인 InnoDB에서도 사용되는 구조이다. (실제는 아래 설명보다 더 복잡하게 구현되어 있다)
B+tree의 구조
- 브랜치 노드: 키 값만 저장하며, 자식 노드를 가리키는 포인터 포함
- 리프 노드: 모든 데이터를 저장하며, Linked List로 연결
- 리프 노드에서만 검색 가능, 브랜치 노드에서는 탐색 경로만 결정
B+tree의 특징
- 트리 높이 감소: 한 노드당 더 많은 키를 저장 가능 → 검색 속도 향상
- 빠른 범위 검색: 리프 노드가 Linked List로 연결되어 있어 순차 탐색이 효율적
- 균형 유지: 노드가 가득 차면 분할, 부족하면 병합
B+tree의 연산
B+tree 의 연산은 B-tree 연산과 비슷하다.
1. 검색
- 루트 노드에서 적절한 서브트리 선택
- 브랜치 노드를 따라 리프 노드까지 탐색
- 리프 노드에서 선형 탐색으로 키를 찾음
2. 삽입
- 적절한 리프 노드 찾기
- 키를 삽입 후, 정렬 유지
- 리프 노드가 꽉 찬 경우, 분할 → 부모 노드에 새로운 키 추가
3. 삭제
- 리프 노드에서 키를 제거
- 키 개수가 최소 키 개수보다 작아지면, 병합 또는 차용(형제 노드에서 값 빌려오기) 수행
- 필요 시 부모 노드 조정
| B-tree | B+tree | |
| 데이터 저장 | 리프 노드, 브랜치 노드 모두 저장 가능 | 오직 리프 노드에만 저장 |
| 트리의 높이 | 상대적으로 높음 | 낮음(한 노드당 더 많은 키 저장 가능) |
| 검색 속도 | 브랜치 노드에서도 검색 가능 | 리프 노드까지 가야 검색 가능 |
| 범위 검색 | 느림 | 빠름(리프 노드 Linked List 활용) |
| 키 중복 | 없음 | 있음(리프 노드에 모든 데이터 저장) |
참고: https://gyoogle.dev/blog/computer-science/data-structure/B%20Tree%20&%20B+%20Tree.html