B- Tree
전산학에서 B-트리는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종이다.
- 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 대수 시간으로 할 수 있다.
- 이진 트리는 항목이 삽입될 때 하향식으로 구성되는 데 반해, B-트리는 일반적으로 상향식으로 구성
B+ Tree (Quaternary Tree)
컴퓨터 과학용어로, 키에 의해서 각각 식별되는 레코드의 효율적인 삽입, 검색과 삭제를 통해 정렬된 데이터를 표현하기 위한 트리자료구조의 일종
- B트리와 대조적으로 B+트리는, 모든 레코드들이 트리의 가장 하위 레벨에 정렬되어있다. 오직 키들만이 내부 블록에 저장된다.
- 동적이며, 각각의 인덱스 세그먼트(블록 또는 노드라고 불리는) 내에 최대와 최소범위의 키의 개수를 가지는 다계층 인덱스(multilevel index)로 구성
- 블록-지향적인 storage context(예: filesystem)에서 검색을 효율적으로 할 수 있다
