[자료구조] B-트리

B-트리 (B-Tree)란?

---

DB 인덱스에 관해 공부하다가, 동적 Multi-Level Index에서 B-트리를 사용한다는걸 알게 되었다. B-트리에 대해 정리해보자.

 

B-트리는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종이다.

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

 

방대한 양의 저장된 자료를 검색해야 하는 경우 검색어와 자료를 일일이 비교하는건 비효율적이다.

B-트리는 데이터를 정렬된 상태로 보관하고, 삽입 및 삭제를 대수 시간으로 할 수 있게 해준다.

 

B-트리의 모양은 다음과 같다.

 

[참조] 위키백과 B-트리 

 

B-트리의 성립조건은 다음과 같다.

1. 노드가 가지는 데이터의 수가 N개라면, 자식 노드의 갯수는 N+1개이다.
2. 노드가 가지는 데이터는 정렬된 상태여야 한다.
3. 노드가 가지는 데이터를 기준으로 자식 노드가 가지는 데이터의 범위가 결정된다.
   위의 그림을 예로 들어보자.
       왼쪽 자식 트리가 가지는 범위 : 7 미만
       중간 자식 트리가 가지는 범위 : [7, 16)
       오른쪽 자식 트리가 가지는 범위 : 16 이상 
4. 리프 노드는 모두 같은 레벨에 존재해야 한다.
5. 입력 자료는 중복될 수 없다.