[자료구조/알고리즘] B트리에 대한 고찰(작성 중)

기본적인 이진 탐색트리는 삭제 및 삽입으로 균형이 한쪽으로 쏠리게 되면 성능이 급격하게 떨어질 수 있다.

위의 그림을 보며 root에서 target 찾는 과정을 생각해보면 불균형한 이진트리에서의 탐색이 얼마나 비효율적일 지 상상할 수 있다.

이러한 이유 때문에 균형을 유지하기위한 다양한 자료구조들(AVL트리, RB트리)이 있다. 하지만 이들 역시 이진트리의 형태이기 때문에 레벨의 깊이가 한정되어있다. 하지만 디스크나 SSD같이 느리고 I/O비용이 높은 저장장치에서는 다음레벨로 넘어가는 횟수가 많을 수록 비효율적이다.

B트리는 이진트리의 구조가 아니다. 차수가 2개 이상일 수 있다. 다시말해 여러개의 2개 이상의 노드를 가질 수 있는 것이고 이에따라 하나의 노드에서 처리할 것이 많아진 대신 레벨의 깊이가 낮아지게 된다.

B트리의 모든 리프는 레벨이 같다. 이유는 직관적으로 알 수 있다. 삽입연산이 일어날 때 노드의 이동이 높은 레벨로 이루어지기 때문이다.

B 트리에 데이터 삽입

B 트리에 데이터 삭제