컴퓨터 공학 - B Tree

1. B 트리의 개념

B 트리는 데이터베이스와 파일 시스템에서 널리 사용되는 자기균형 다진트 구조로서, 대량의 데이터를 효율적으로 저장하고 검색하는 데 최적화된 자료구조이다. 이 구조는 노드가 다수의 키와 자식을 가지며, 트리의 높이를 최소화하여 검색, 삽입, 삭제 연산의 시간복잡도를 평균적으로 O(log N)으로 유지한다. 이는 B 트리가 이진 탐색 트리보다 높은 다항적 차수(보통 2~1000의 차수)를 가지기 때문에 가능한데, 차수가 클수록 트리의 높이가 줄어들어 검색 속도가 빠르다. 예를 들어, 차수가 100인 B 트리를 사용할 경우, 10억 개의 데이터를 저장했을 때 평균 검색 깊이는 3단계 내외로 줄어들어 디스크 입출력을 획기적으로 줄일 수 있다. 또한, B 트리는 자율적으로 균형을 유지하는 구조로, 특정 노드가 지나치게 채워지거나 비게 되는 현상을 방지한다. 노드가 최대 차수에 도달하면 분할(split) 연산이 일어나고, 반대로 키 삭제 시 최소 차수보다 낮아지면 병합(merge) 또는 재분배를 통해 균형을 맞춘다. 이로 인해 트리 전체의 균형이 유지되며, 이는 검색이나 수정 작업 시 소요되는 평균 시간이 일정하게 유지되도록 돕는다. 실무에서는 …