인덱스 알고리즘 B tree 간단 개념 정리

B Tree(Balanced Tree)

- 균등한 응답속도 유지를 위하여 Leaf Level의 좌우균형을 유지하는 트리

- 데이터베이스와 파일시스템에서 주로 사용되는 트리 자료구조(비선형 자료구조)의 한 종류

- 이진트리를 확장하여 자식 노드의 최대 숫자가 2보다 큰 트리 구조

- 최악의 경우에도 O(longN)의 사간복잡도의 검색 성능

 

 

종류

B 트리

출처: http://www.btechsmartclass.com/data_structures/b-trees.html

높이 균형 m-원 탐색트리

Leaf 노드가 한쪽 방향으로 쏠리는 현상이 적음

노드의 삽입과 삭제시 트리의 균형을 유지하기 위해 복잡한 연산(재분배, 합병)이 필요

1/2 이상 차면 노드 분열

 

B+트리

Leaf node간 linked list가 구성되어 순차 탐색의 효율이 좋음

leaf node에만 데이터가 있기 때문에 모든 데이터에 도달하는 비용이 거의 같다.

 

B*트리

하나의 노드가 Overflow 되면 여유 공간이 있는 이웃 노드에 재분배 과정을 거쳐 삽입이 가능

Root/Leaf dhl shemfmf 2/3 이상 채워 Split 현상 감소