B-Tree는 탐색 성능을 높이기 위해 높이를 균형있게 유지하는 Balanced Tree의 일종입니다.
B-Tree는 이진 트리와는 다르게 하나의 노드에 여러개의 데이터를 가질수 있으며, 두개 이상의 자식노드들을 가질 수 있습니다. 만약 노드의 자식 수 중 최대값이 K라면 이 B-Tree의 차수는 K차수라 하며 K차 B-Tree라고 합니다.
위의 그림은 3차 B-Tree이며 각 노드마다 최대 자식 수가 3개 인것을 확인 할 수 있습니다.
B-Tree는 하나의 노드에 여러 키를 배치하면서 이진트리보다 훨씬 많은 데이터를 담을 수 있으며, 노드 내의 데이터들은 항상 정렬된 상태입니다.
이러한 B-Tree는 다음과 같은 특징을 갖습니다.
B-Tree를 이용하는 이유중 하나는 시간복잡도 문제 입니다.
일반적인 트리의 경우 평균적으로 O(logN)의 시간복잡도를 갖지만, 트리가 편향된 최악의 경우O(N)의 시간복잡도를 갖게 됩니다. 하지만 B-Tree는 Balanced Tree로서 항상 같은 leaf 노드들이 같은 레벨에 존재하기 때문에 최악의 경우에도 O(logN)의 시간복잡도가 보장됩니다.
B+Tree는 B-Tree의 몇가지 문제점을 보완한 트리로, 가장 큰 차이점은 B+ Tree에서는 데이터를 저장하는 leaf노드만이 실제로 데이터를 갖고있고, 내부 노드들은 단순히 키값만을 갖고 있게 됩니다. 반면 B-Tree는 내부 노드와 leaf노드 모두 데이터를 가질 수 있습니다. 아래 그림을 보면 모든 leaf node들은 연결리스트로 연결되어 있습니다.
이러한 차이점으로 B+Tree는 다음과 같은 이점이 있습니다.