B-Tree, B+Tree

B-Tree와 B+Tree는 데이터베이스에서 사용되는 자료구조로, 대량의 데이터를 저장하고 탐색하는 데에 효율적이다.

B-Tree

Balance Tree라는 뜻의 B-Tree는 Node들이 균형을 잡히도록 설계되었다. 검색,삽입,삭제 모두 O(log N)
각 노드는 하나 이상의 자식 노드를 가지며, 각 노드는 키와 포인터를 가진다. 키는 검색에 포인터는 다른 노드 또는 데이터를 가리킨다.

이런 특징으로 파일 시스템과 데이터 베이스 인덱스에서 널리 사용된다.

B-Tree 는 높이가 낮아서 탐색 속도가 빠르며 랜덤 엑세스에 대해 더욱 빠른 성능을 제공한다. (데이터 삽입,삭제갱신작업)

B+Tree

B+Tree는 B-Tree의 변형으로, 리프 노드에만 데이터를 저장하기 때문에 더 많은 데이터를 저장할 수 있고, 리프 노드 간에 연결이 되어있어 범위 검색에 용이하다.

이런 특징으로 데이터베이스와 인덱스(특히 클러스터 인덱스)에 많이 사용된다.

B+Tree는 대량의 데이터, 범위 검색에 더욱 빠른 성능을 제공한다.

추가

MySQL 의 InnoDB 엔진의 기본 자료구조는 B-Tree이며 B+Tree도 지원한다.
범위 검색 제외한 대부분의 쿼리에선 B-Tree가 유리하다.