[자료구조] 기존 bst와 avl 트리를 개선한, B-tree에 관하여

B-트리의 필요성( BST와 AVL 트리의 문제점)

BST (Binary Search Tree)는 편향될 경우 높이가 최대 N이 될 수 있다. 이는 탐색, 삽입, 삭제 시 최악의 경우 O(N)의 시간 복잡도를 초래한다. AVL 트리는 항상 균형을 유지하지만, 높이는 여전히 O(log N)이다. 이는 메모리 접근 속도가 느린 대용량 데이터베이스 시스템에서는 비효율적이다. BST와 AVL 트리는 메모리 내에서 사용될 때는 효율적일 수 있지만, 데이터베이스 시스템처럼 대용량 데이터를 다루는 경우에는 디스크 접근이 빈번해질 수 있고, 이는 매우 비용이 크기 때문에 디스크 접근 횟수를 최소화하는 것이 중요하다. B-트리는 이러한 문제를 해결하기 위해 고안되었다. 

 

- B-tree의 특징

균형 유지: B-트리는 항상 균형을 유지한다. 모든 리프 노드는 동일한 깊이를 가진다.

다수의 자식 노드: 각 노드는 최대 M개의 자식을 가질 수 있다. 이는 B-트리의 높이를 낮게 유지하는 데 기여한다.

디스크 블록 최적화: B-트리의 노드 크기는 디스크 블록 크기와 맞춰져 있어, 한 번의 디스크 읽기/쓰기로 많은 키를 읽을 수 있다.

동적 연산 효율성: 삽입과 삭제 연산 시 노드 분할과 병합을 통해 트리의 균형을 유지한다. 이러한 연산의 시간 복잡도는 O(log N)이다.

대규모 데이터베이스 활용: B-트리는 대용량 데이터베이스 시스템에서 주로 사용된다. 데이터가 메모리에 모두 상주하지 못하는 경우에도 효율적인 데이터 접근을 보장한다.