B-Tree

B-Tree는 binary tree(이진 트리)에서 파생된 트리 구조

데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조

 

인덱스에서 주로 사용한다.

 

이진 트리와의 차이점이 있다면, 하나의 노드는 2개 이상의 데이터를 가질 수 있다는 점,

그리고 자식 노드도 여러 개를 가질 수 있다는 점

이진트리는 자식노드 2개밖에 안되지만 B-Tree는 2개 이상이다~ 최대m개 가질 수있다~

하나의 노드에 키값을 여러개 가질 수 있고,
키 사이사이에 자식노드가 연결돼있다.



+
 B+tree는 B-tree의 확장개념으로, b-tree와 달리 모든 노드에 key, data가 있지 않으며, leaf 노드에만 key, data가 있다. 

그리고 leaf 노드끼리는 연결리스트로 연결되어 있음 

 

기존 트리가 검색하다가 다시 루트노드로 돌아간 뒤에 검색을 또 시작한다면, B+tree는 리프노드가 링크드리스트로 연결돼있어서 루트노드로 돌아가지 않고 빠르게 검색 가능!