[MSSQL] B-Tree

Tree란?

Tree에 대한 개념은 이미 알고 있을 것이라 생각하고,

 

시간 복잡도에 대해 생각해보자.

 

출처) https://helloinyong.tistory.com/296

 

일반적으로 위의 그림처럼 평균적으로 생긴 Tree에서

 

탐색에 대한 시간 복잡도는 O(log N)이다,

 

 

출처) https://helloinyong.tistory.com/296

 

하지만, 위의 그림처럼 Tree의 형태가

 

한쪽으로 추욱 늘어진 최악의 경우엔 O(N)이다.

 

이러한 최악의 경우를 대비해서

 

Balanced Tree라는 것을 사용한다.

 

 

Balanced Tree?

말 그대로 "균형잡힌 Tree"로,

 

위에서 본 Tree 구조의 최악의 경우처럼 트리가 한쪽으로 쏠리지 않게

 

노드 삽입 및 삭제 시에 특정 규칙에 따라

 

트리가 재정렬되어 좌 / 우 SubTree의 밸런스를 유지하는 Tree이다.

 

항상 좌 / 우 SubTree 간에 밸런스를 유지하고 있기 때문에

 

탐색에 대한 시간 복잡도는 언제나 O(log N)이지만,

 

노드 삽입 및 삭제 시 발생하는 재정렬 작업 때문에

 

탐색을 제외한 작업에서는 일반 Tree보다 성능이 좋지 않다.

 

이러한 Balanced Tree의 예시에는

 

AVL-Tree, RedBlack-Tree, B-Tree 등이 있다.

 

 

왜 하필 (Balanced) Tree를?

Balanced Tree는 최악의 경우에도 탐색 시간이 O(log N)이므로

 

탐색 기능 자체만 봤을 때에는 효율적인 자료구조임을 알 수 있다.

 

B-Tree

1. 트리 내 모든 데이터가 항상 정렬된 상태로 유지되기 때문에,

 

등호(=) 연산뿐만 아니라 부등호(>, <) 연산 처리도 가능하다.

 

2. 포인터 접근 방식이 적어 매우 많은 데이터가 있어도 속도 이슈가 적다.

 

3. 데이터 탐색뿐 아니라, 삽입 및 수정 및 삭제에도 항상 O(log N)의 시간 복잡도를 가진다.