[자료구조] B-tree와 B+tree에 대해 알아보자!

B-tree..? 만약 자료구조를 공부하지 않았더라도 DB를 공부한 적이 있는 분들이라면 들어본 적이 있는 자료구조일 것입니다.

 

B-tree란?

B-tree는 DB의 인덱스에서 사용되는 자료구조로 이진트리를 확장해서 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조입니다. 쉽게 말해 하나의 노드에 여러 자료가 배치될 수 있는 트리 구조라고 할 수 있습니다.

 

그리고 Balanced Tree라는 특징이 있는데, 이는 노드 삽입 및 삭제 시에 스스로 균형을 맞춰주는 트리를 의미합니다.
기존 이진트리의 경우에는 좌우 균형이 맞지 않는 편향 트리가 생길 수도 있는 문제점이 있어 최악의 경우에 O(n)이라는 시간 복잡도를 가져서 검색 효율이 떨어지는 경우가 생깁니다.
Balanced Tree는 이러한 이진트리의 약점을 개선한 트리로 테이블이 갱신되어도 내부적으로 항상 균형적으로 트리를 유지시켜 주기 때문에 검색 시 최악의 경우에도 O(logn)의 시간 복잡도를 가진다는 장점이 있습니다.

 

하지만 Balanced Tree가 무조건 좋냐고 물어보면 그렇다고 할 순 없습니다.

트리의 데이터들이 자주 변경되거나 추가된다면 트리의 균형을 맞추기 위해서 추가적인 작업을 통해 노드를 재구성을 하여 트리의 균형을 되찾는 작업이 필요합니다.
그렇기 때문에 혹시라도 많은 데이터가 있는데 트리의 데이터 갱신을 자주 하게 되면 추가적인 비용이 더 커져서 배보다 배꼽이 더 커지는 상황이 오게 됩니다.

이러한 문제를 가지고 있어 Balanced Tree는 트리의 데이터 갱신이 자주 일어나는 곳에 적용하면 오히려 악효과를 가진다고 할 수 있습니다. 하지만 적절한 곳에서 사용을 하면 성능을 향상 시키는데 큰 도움을 주는 자료구조입니다.

 

균형을 맞춰줄 때 내부에서 추가적인 작업이 일어난다고 했는데 어떤 식으로 이루지나요?

어떤 작업인지는 Balanced Tree마다 내부적으로 동작하는 방법이 다르고 주제에서 벗어나기 때문에 여기서는 다루지 않겠습니다.

 

B-tree는 하나의 노드가 2개 이상의 노드를 가진다는 것이 이진트리와 다른데 이게 어떠한 도움이 될까?

대량의 데이터를 처리해야 하는 검색 구조인 경우 하나의 노드에 많은 데이터를 가질 수 있다는 점은 큰 장점입니다.
대량의 데이터는 메모리보다는 하드디스크 혹은 SSD에 저장되어야 하는데 이들 외부 기억 장치들은 블럭 단위로 입출력을 하기 때문입니다.

 

예를 들어 한 블럭이 1024 바이트라면, 2바이트를 읽나 1024바이트를 읽나 똑같은 입출력 비용이 발생하기 때문입니다.
따라서 하나의 노드를 모두 1024바이트로 꽉 채워서 조절할 수 있으면 입출력에 있어서 효율적인 구성을 갖출 수 있습니다. B-Tree는 이러한 장점을 토대로 많은 데이터베이스 시스템의 인덱스 저장 방법으로 사용되고 있습니다.

 

 

B+tree란?

B-tree의 확장 개념으로, B-tree와 달리 모든 노드에 key, data가 있지 않고, leaf 노드에만 data가 있습니다. 또한 leaf 노드끼리는 서로 LinkedList로 연결되어 있다는 점이 B-tree와 다르다고 할 수 있습니다.

 

왜 leaf 노드에만 data가 있고 다른 노드들에는 key만 두었을까?

이런 식으로 구성했을 때 B-tree에 비해 생기는 장점들이 생기기 때문입니다.

B+tree의 장점

1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보하여 더 많은 key를 가질 수 있습니다. 하나의 노드에 더 많은 key를 담을 수 있기 때문에 tree의 높이는 더 낮아집니다.(cache hit를 높일 수 있습니다.)
2. 풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형 탐색만 하면 돼서 B-tree에 비해 빠릅니다. B-tree의 경우에는 모든 노드를 확인해야 합니다.

 

어..? 그러면 무조건 B+tree를 사용하면 좋은 거 아닌가?

그렇지는 않고 B+tree가 B-tree에 비해 안 좋은 경우도 많습니다.
예를 들어 B-tree의 경우 최상 케이스에서는 루트에서 끝낼 수 있지만, B+tree는 무조건 leaf 노드까지 내려가 봐야 한다는 단점이 있습니다.
그래서 서로 누가 더 좋고 안 좋고를 따질 수는 없고 각자 적절한 곳에서 사용하면 좋을 것 같습니다.

 

B-tree와 B+tree의 차이 간단하게 정리

• B-tree는 각 노드에 key와 data 모두 들어갈 수 있고, data는 disk block으로 포인터가 될 수 있는 반면에 B+tree는
  각 노드에 key만 들어가고, 따라서 data는 모두 leaf 노드에만 존재합니다.
• B-tree는 모든 노드에 데이터가 저장되거나 삭제될 수 있고,
  반면에B+tree는 add와 delete가 모두 leaf 노드에서만 이루어집니다.