DB 개념 - B-Tree (B, B*, B+)

B-Tree는 여러 DBMS에서 인덱스 구현에 많이 사용되는 자료구조이다.
B-Tree, B*Tree, B+Tree가 어떤 것인지, 어떤 차이들이 있는지를 위주로 살펴보자.

B-Tree는 이름에서 알 수 있듯이, Tree 자료구조의 일종이다.

B-Tree라는 이름 때문에 Binary Tree 와 혼동하는 경우가 있는데,
최대 2개의 자식 노드를 가지는 Binary Tree(이진 트리)와 달리,
B-Tree는 가질 수 있는 자식 노드 수가 M이다.
즉, B-Tree 는 2명 이상의 자식을 가질 수 있다.

Binary Tree 에서 키 값을 기준으로 왼쪽은 자신보다 작은 값을, 오른쪽은 자신보다 큰 값을 배치 할 수 있었다.
다시 말하자면, 1개의 키로 2개의 분리된 집합을 만들 수 있었다.

B-Tree 에서는 M개의 분리된 집합을 만들어야 하기 때문에, 키 값이 M-1 개 필요하다.

다른 특징으로는, 항상 리프 노드가 같은 높이를 가진다는 점이다.

리프 노드가 같은 높이를 가질 수 있도록 하기 위해서는
새로운 원소의 삽입, 삭제, 또는 기존 원소의 값 변경 시에 추가적인 오버헤드가 요구된다.

그럼에도 불구하고 리프 노드가 같은 높이를 가질 수 있도록 유지하는 이유는,
삽입,삭제,수정 의 빈도 수 보다 읽기(Read)의 수요가 훨씬 더 높기 때문이다.

트리 자료구조는 비선형적 자료구조이다.
정해진 규칙을 유지하기 때문에, 규칙을 활용하여 원소를 전체 탐색하지 않을 수 있게 된다.
이러한 트리의 시간 복잡도를 결정 할 때 중요한 요소는 바로 '트리의 높이'이다.

위 그림과 같이 선형적으로 구성된 이진 트리는, 트리의 이점을 가지지 못한다.

그에 반해, 위의 트리는 최대한 균형이 맞도록 트리를 구성하였기 때문에
높이가 낮아 읽기 작업 시 전체 노드를 탐색하지 않을 수 있다.

B-Tree 가 리프 노드의 높이를 동일하게 만들어 유지하는 이유는
트리의 균형을 최대한 균등한 상태로 유지하기 위함이다.