B-Tree와 B+Tree
B-Tree와 B+Tree
B-Tree와 B+Tree는 데이터베이스와 파일 시스템에서 대용량 데이터를 효율적으로 저장하고 검색하기 위해 설계된 자가 균형 탐색 트리(Self-Balancing Search Tree)입니다. 두 자료구조의 핵심 목표는 디스크 접근 횟수(Disk I/O)를 최소화하여 성능을 높이는 것입니다.
🌳 B-Tree의 특징
- 균형 잡힌 다진 탐색 트리 (Balanced M-way Search Tree) : 하나의 노드에 여러 개의 키(key)와 자식 노드 포인터를 가질 수 있는 트리입니다. (이진 트리는 최대 2개의 자식)
- 주요 규칙
> * 모든 리프 노드는 같은 레벨(높이)에 존재합니다. > * 노드의 키들은 항상 정렬된 상태를 유지합니다. > * 내부 노드(Internal Node)에도 키와 데이터가 함께 저장될 수 있습니다.
- 동작 원리 : 노드가 가득 차면 '분열(Split)'이, 노드가 최소 키 개수보다 적어지면 '병합(Merge)'이 일어나며 스스로 트리의 균형을 유지합니다.
- 디스크 I/O 최적화 : 노드 하나에 많은 키를 저장함으로써 트리의 높이를 매우 낮게 유지합니다. 디스크에서 데이터를 읽는 단위인 '블록' 또는 '페이지' 크기와 노드의 크기를 맞추어, 한 번의 디스크 I/O로 많은 데이터를 메모리에 로드할 수 있어 효율적입니다.
✨ B+Tree: B-Tree의 확장
B+Tree는 B-Tree의 개념을 계승하면서, 데이터베이스 인덱스에 더 적합하도록 몇 가지 중요한 개선을 이룬 자료구조입니다.
- B-Tree와의 핵심 차이점
> 1. 데이터 저장 위치 : B-Tree는 모든 노드에 데이터를 저장할 수 있지만, B+Tree는 오직 리프 노드에만 데이터를 저장합니다. 내부 노드에는 자식 노드를 찾아가기 위한 키만 저장합니다. > 2. 리프 노드 연결 : B+Tree의 모든 리프 노드는 연결 리스트(Linked List) 형태로 서로 연결되어 있습니다.
- B+Tree의 장점
> * 향상된 범위 탐색 : 리프 노드들이 연결 리스트로 연결되어 있어, 특정 범위의 데이터를 순차적으로 탐색(Range Scan)할 때 매우 효율적입니다. (예: `WHERE age BETWEEN 20 AND 30`) > * 더 많은 키 저장 : 내부 노드에 데이터 대신 키만 저장하므로, 같은 크기의 노드에 더 많은 키를 담을 수 있습니다. 이는 트리의 높이를 더 낮게 유지하여 검색 효율을 높입니다. > * 균일한 탐색 속도 : 모든 데이터가 리프 노드에만 존재하므로, 어떤 데이터를 찾든 항상 루트에서 리프까지 동일한 높이를 탐색하게 됩니다.
💡 개발자 핵심 Point
- B-Tree와 B+Tree의 핵심 아이디어는 '디스크 I/O 횟수를 줄여 성능을 최적화'하는 것입니다. 메모리 접근 속도와 디스크 접근 속도의 엄청난 차이 때문에 고안된 자료구조입니다.
- 이러한 장점 때문에, 대부분의 현대적인 데이터베이스 시스템(MySQL, PostgreSQL 등)은 인덱스 구조로 B-Tree가 아닌 B+Tree를 사용합니다.
- 해시 인덱스 vs B-Tree 인덱스
> * 해시 인덱스 : 등호(=) 연산을 사용한 동등 비교 검색에 매우 빠르지만(O(1)), 부등호(<, >)를 사용한 범위 탐색은 불가능합니다. > * B-Tree(B+Tree) 인덱스 : 동등 비교(O(log n))와 범위 탐색 모두에 효율적이므로, 대부분의 경우 B-Tree 인덱스가 범용적으로 사용됩니다.
