CS Study 6주차 : B - tree /B + tree

B - tree

B - tree는 인덱스를 이루고 있는 자료구조의 일종이다.

트리 구조의 우위성

트리 구조는 데이터를 유지하기 위해 자주 사용하는 구조인데 참색시 단시간 내에 실행할 수 있기 때문이다.

 

특징

B - tree의 핵심은 테이터가 정렬된 상태로 유지되어 있다는 점이다.

• 그림에 있는 사각형으로 표시된 한개의 데이터를 노트(Node)라고 한다.
• 가장 상단의 노드를 루트 노드(Root Node), 중간 노드들을 브랜치 노드(Branch Node),
  가장 아래의 노드들을 리프 노드(Leaf Node)라고 한다.

 

위 그림처럼 B - tree는 Binary seach tree와 유사하지만, 한 노드당 자식 노드가 2개 이상 가능하다.

 

 

B - tree는 균일성을 가지고 있어 어떤 값에 대해서도 같은 시간대에 결과를 얻을 수 있다.

 

B - tree는 균형 트리이다.

• 균형 트리라는 것은 루트로부터 리프까지의 거리가 일정한 트리 구조를 뜻한다.
• 트리 중에서 특히 성능이 안정화 되어있다.

 

단점

B - tree는 처음 생성 당시는 균형 트리이지만 테이블 갱신(INSERT / UPDATE / DELETE)의 반복을 통해
서서히 균형이 깨지고, 성능도 약화된다.

 

 

B + tree

• B + tree는 B - tree의 확장 개념으로 B - tree와 다르게 브랜치 노드에 key만 담아두고, 데이터는 담지 않는다. 
• 오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 Linked list로 연결되어 있다,

장점

• 리프 노트를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다.
• 풀 스캔 시, B + tree는 리프 노드에 데이터가 모두 있어서  한번의 선형탐색만 하면 되기 때문에 B - tree보다 빠르다.

 

B - tree vs B + tree