균등한 응답속도를 위한 탐색 트리, B-Tree

B-Tree의 개요

B-Tree의 개념

- 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조

- 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 자료구조의 일종

 

- 대부분의 이진 트리는 항목이 삽입될 때 하향식으로 구성되지만 B-트리는 상향식으로 구성됨.
- B는 Balanced의 의미이며, leaf node가 한쪽 방향으로 쏠리는 현상이 적음
- B-Tree 에서 B를 Bi로 인식하는 사람들이 많으나, Balanced이다. 일반적인 트리와 다르게 자식노드가 3개 이상이 될 수 있기 때문이다.

B-Tree의 특징

1. 각 노드는 1/2이상 채워져야 하며 모든 리프 노드(leaf node)는 같은 레벨 (균형 트리)
2. 탐색, 추가, 삭제는 루트 노드(root node)로 부터 시작
3. 노드 내 값은 오름차순을 유지
4. 공백이거나 높이가 1이상인 m-원 탐색 트리(m-way search tree)

 

B-Tree의 장단점

장점

1. 삽입, 삭제 후에도 균형 트리 유지
2. 효율적인 알고리즘 제공
3. 저장 장치의 효율성
4. 균등한 탐색 속도 보장 가능

 

단점

1. 노드의 삽입과 삭제 시 트리의 균형을 유지하기 위해 복잡한 연산(재분배, 합병) 필요
2. 순차탐색 시에 중위(indorder) 순회로 비효율적임

- B+ 트리 구조에서 리프 노드간의 linked list로 순차 탐색 효율이 향상

 

B-Tree의 구조

B-Tree의 구조

- 기존 이진트리는 자식노드가 2개까지만 허용되는 것과 달리 B-Tree는 2개 이상이 가능한 구조이다.

B-Tree의 Insert 절차

B-tree 노드 삽입 절차, 새로운 값인 59가 추가된 경로를 설명하는 구조

1. 기존 노드에 59가 신규로 추가됨
2. 59가 추가되면서 middle value가 65로 변경되며, 새로운 노드들이 형성됨

 

B-Tree의 활용

- DBMS나 파일시스템의 인덱스 자료구조로 활용 (B+tree, B*tree로 발전)

- 검색엔진, 패턴 매칭 등 성능이 일정하면서 빠른 탐색이 요구되는 분야에 활용

 

키워드

균형트리, 중위순회, root node, leaf node

 

참고자료

https://ko.wikipedia.org/wiki/B_%ED%8A%B8%EB%A6%AC