B- tree vs B+- tree

B- tree

• Binary Search Tree와 유사하지만, 한 노드 당 자식 노드가 2개 이상 가능하다.
• 균형 트리이다.(Tree is always balanced)
  • 즉, 어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있다.
  • 균형 트리란 루트로부터 거리가 일정한 트리 구조를 뜻하고 트리 중에서 특히 성능이 안정화 되어 있다.
• 그러나 B- 트리는 처음 생성 당시는 균형 트리이지만 태이블 갱신(INSERT/UPDATE/DELETE) 의 반복을 통해 서서히 균형이 깨지고 성능도 악화 된다.
• 어느 정도 자동으로 균형을 회복하는 기능이 있지만, 갱신 빈도가 높은 테이블에 작성되는 인덱스 같은 경우 인덱스 재구성을 통해 균형을 되찾는 작업이 필요하다.
• Space wasted by deletion never becomes excessive
  • 즉, each node is at least half-full

B- tree의 구조

B+- tree

• B- tree의 확장 개넘으로 B- tree의 경우 internal 또는 branch 노드에 key와 data를 담을 수 있다.
• 하지만 B+- tree의 경우 브랜치 노드에 key만 담아두고 data는 담지 않는다.
  • 오직 리프노드에만 key와 data를 저장하고 리프 노드끼리 Linked List로 연결되어 있다.

B+- tree의 장점

1. 리프노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다. 하나의 노드에 더 많은 key들을 담을 수 있기 때문에 트리의 높이는 더 낮아진다.(cache hit를 높일 수 있음)
2. 풀 스캔 시 B+- tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B- tree에 비해 빠르다. B- tree의 경우에는 모든 노드를 확인해야 한다.

B+- 트리 insertion