[자료구조] B-tree(사용하는 곳, 탐색, 삽입, 삭제, 시간 복잡도)

사용하는 곳,

데이터 베이스나 파일시스템에서 데이터를 저장, 관리 할 때 사용한다

 

특징

1. n차 b트리라면 자식 트리들은 최소한 n/2개의 노드를 가져야한다

2. 왼쪽에는 자신보다 작은 서브 트리, 오른쪽에는 자신보다 큰 서브트리를 가진다

 

탐색

하향식으로 탐색할 수 있도록 한다

 

삽입

하향식으로 자기 자리를 찾고 b트리의 조건을 만족하지 못할 경우, 분해하여 b트리의 조건을 만족 시킬 수 있도록 한다

 

삭제

리프 노드일 경우는 그냥 삭제

아닐 경우는 삭제 후 부모노드, 형제 노드를 이용하여 b트리 유지한다.

 

시간 복잡도

높이가 h라고 햇을때 logh