B tree, B+ tree

B Tree

• 데이베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종
• 트리구조? 그래프의 일종, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 
• 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길 하나뿐인 그래프를 트리라고 한다.
• 이진 트리를 확장, 하나의 노드가 가질수 있는 자식 노드의 최대 숫자 2보다 큰 트리 구조
• 방대한 양의 저장된 자료를 검색해야 하는 경우 검색어와 자료를 일일이 비교하는 방식은 비효적이기 때문에 B 트리는 잘를 정렬된 상태로 보관하고 삽입 및 삭제를 대수 시간으로 할수 있다.

B+ tree

• Quaternary Tree라고 알려져 있음
• 키에 의해 각각 식별되는 레코드의 효율적인 삽입, 검색과 삭제를 통해 정렬된 데이터를 표현하기 위한 트리자료구조의 일종
• 각각의 인덱스 세그먼트 (블록 or Node) 내에 최대와 최소범위 키의 개수를 가지는 다 계층 인덱스 (multilevel index)로 구성된다
• B트리와 대조적으로 B+트리는 모든 레코드들이 가장 하위레벨에 정렬되어 있다. 오직 키들만 내부 블록에 저장된다.
• 중간 레벨의 노드는 데이터를 찾기위한 인덱스 (index set)