B-Tree란?
균형 이진 탐색 트리의 일종으로, 빠르게 데이터를 탐색하거나 삽입, 삭제할 수 있도록 설계된 트리 구조입니다.
B-Tree는 데이터베이스와 같은 대량의 데이터를 다루는 시스템에서 효율적인 성능을 제공합니다.
트리의 각 노드는 여러 키와 자식을 가질 수 있으며, 이를 통해 이진 트리보다 더 적은 깊이를 가지면서 많은 데이터를 효율적으로 처리할 수 있습니다.
MySQL에서 B-Tree 인덱스의 역할
MySQL에서 InnoDB와 MyISAM 스토리지 엔진은 기본적으로 B-Tree 인덱스를 사용합니다. 이 인덱스를 통해 MySQL은 테이블 내의 데이터를 효율적으로 검색할 수 있습니다. B-Tree 인덱스는 다음과 같은 상황에서 유리합니다.
- 검색: 특정 열에 대해 값이 무엇인지 빠르게 찾아낼 수 있습니다.
- 범위 검색: B-Tree 구조는 범위 기반 검색(예: 특정 값보다 크거나 작은 데이터)을 효율적으로 수행합니다.
- 정렬된 데이터: 인덱스가 정렬된 상태로 데이터를 저장하기 때문에, 정렬된 데이터를 효율적으로 탐색할 수 있습니다.
B-Tree의 특징
- 균형 트리: 모든 리프 노드는 동일한 깊이를 가지므로, 데이터가 어디에 있든지 탐색 속도가 균일합니다.
- 자기 균형: 삽입이나 삭제가 발생할 때도 트리는 스스로 균형을 유지합니다.
- 빠른 탐색: 트리의 높이가 낮기 때문에 탐색, 삽입, 삭제가 빠릅니다. 보통 O(log n) 시간 복잡도를 가집니다.
B-Tree의 구조
Root 노드
- 트리의 최상위에 있는 노드
- 루트 노드는 다른 노드들과 달리 자식 노드가 없을 수도 있으며, 이 경우 트리의 전체가 하나의 노드로만 이루어집니다.
Branch 노드 (또는 Internal Node)
- 루트와 리프 노드 사이에 있는 노드
- 탐색, 삽입, 삭제 시 데이터의 경로를 결정하고, 리프 노드로 가는 중간 다리 역할을 합니다.
Leaf 노드
- 트리의 말단에 있는 노드
- 실제 데이터 또는 데이터의 포인터를 저장하는 곳으로, 모든 탐색 연산은 최종적으로 리프 노드에서 종료됩니다.
B-Tree의 구조적인 특징
- 키 값의 정렬: 각 노드의 키 값은 정렬되어 있고, 노드 내에서 자식 노드의 경로가 그 키 값을 기준으로 결정됩니다.
- K1, K2, ..., Kn 이라는 키가 있다면, 이 키들 사이의 자식 노드들은 다음과 같은 규칙을 따릅니다:
- 왼쪽 자식 노드의 모든 키는 K1보다 작습니다.
- K1 과 K2 사이의 자식 노드의 키는 K1 보다 크고 K2 보다 작습니다.
- 가장 오른쪽 자식 노드의 모든 키는 Kn보다 큽니다.
- K1, K2, ..., Kn 이라는 키가 있다면, 이 키들 사이의 자식 노드들은 다음과 같은 규칙을 따릅니다:
- 노드의 크기: B-Tree는 차수를 기반으로 노드의 크기를 결정하며, 노드가 꽉차거나 너무 비었을 경우 분할(Split) 또는 병합(Merge)을 통해 트리의 균형을 유지합니다.
- 삽입 시, 만약 노드가 너무 많은 키 값을 가지게 된다면 해당 노드는 두 개의 노드로 분할합니다.
- 삭제 시, 노드가 너무 적은 키 값을 가지게 되면 이웃한 노드와 병합합니다.
- 트리의 높이: B-Tree는 노드가 여러 개의 키와 자식 노드를 가질 수 있으므로, 트리의 높이가 상대적으로 낮습니다.
이는 데이터 탐색 시 더 적은 단계로 원하는 값을 찾을 수 있게 만들어, 검색 기능을 향상시킵니다.
B-Tree는 균형 트리
균형 트리
- 모든 리프 노드가 트리의 어느 쪽으로 치우치지 않고 가능한 한 동일한 깊이 또는 유사한 깊이에 위치하도록 유지되는 트리
- 삽입, 삭제, 탐색 시 성능이 일정하게 유지됩니다.
- 트리의 높이가 log(n)에 비례하므로, 탐색 시간 복잡도가 O(log n)으로 유지됩니다.
비균형 트리
- 트리의 노드가 한 쪽으로 치우쳐 있는 구조이며 이로 인해 일부 노드는 깊이가 매우 깊어지며, 이는 성능 저하를 초래할 수 있습니다.
- 삽입, 삭제가 반복되면 트리의 구조가 크게 변하고 비대칭적인 트리가 될 수 있습니다.
- 최악의 경우 트리가 선형 구조(리스트)와 유사해질 경우 탐색 시간 복잡도가 O(n)이 됩니다.
Reference URIs