[자료구조] B-tree & B+tree 비교

B-tree와 B+tree는 데이터베이스와 파일 시스템에서 데이터를 효율적으로 저장하고 검색하기 위해 사용되는 트리 구조이다. 두 트리는 여러 면에서 비슷하지만 몇 가지 중요한 차이점이 있다.

 

1. 구조적 측면:
   • B-tree는 모든 노드가 키와 데이터를 모두 가질 수 있다. 리프 노드와 내부 노드 모두 데이터 항목을 포함할 수 있다.
   • B+tree는 내부 노드는 키와 데이터 포인터를 가지지만 실제 데이터는 리프 노드에만 저장된다. 리프 노드가 연결 리스트로 구성되어 있어 리프 노드 간의 순차 접근이 용이하다.
2. 검색 성능 측면:
   • B-tree는 키를 찾기 위해 내부 노드와 리프 노드를 모두 탐색해야 할 수 있다.
   • B+tree는 데이터가 리프 노드에만 있으므로 검색 작업이 리프 노드에서 끝난다. 또한 리프 노드가 연결 리스트로 연결되어 있어 범위 검색에 유리하다.
3. 삽입 및 삭제 성능 측면:
   • B-tree는 삽입 및 삭제 시 트리의 높이를 균형 있게 유지하는 데 더 많은 노력이 필요할 수 있다.
   • B+tree는 데이터가 리프 노드에 집중되어 있어 삽입 및 삭제 시 재구성해야 할 노드의 수가 적어 더 효율적일 수 있다.
4. 공간 효율성 측면:
   • B-tree는 내부 노드와 리프 노드 모두에 데이터를 저장하므로 사용 가능한 전체 공간을 좀 더 효율적으로 사용할 수 있다.
   • B+tree는 내부 노드가 데이터 포인터만 포함하므로 데이터 저장 공간이 리프 노드에 집중되어 상대적으로 공간 효율성이 떨어질 수 있다.
5. 범위 쿼리 측면:
   • B-tree는 리프 노드가 연결되어 있지 않기 때문에 범위 쿼리 시 각 노드를 별도로 탐색해야 한다.
   • B+tree는 리프 노드가 연결 리스트로 연결되어 있어 범위 쿼리를 수행하는 데 더 효율적이다.

요약하면, B-tree는 삽입과 삭제 시 더 유연할 수 있지만 B+tree는 데이터 검색과 범위 쿼리에 더 적합하다. 두 구조는 특정 사용 사례에 따라 장단점이 달라진다.