데이터베이스 과제 B+tree 구현

기한은 10월 28일 까지 E3 2층 김민상
월, 수, 금 오후 1시~6시, 화,목 오후 3~6시까지

Binary tree

log(n)의 runtime가지 위해 고안한 자료구조 하지만 데이터가 skewed 되었을 때 최악의 경우 n의 탐색 runtime을 가지다.

B-tree

이를 해결하기 위한 방법으로 나온것이 B-tree 이진 탐색 트리의 구조를 확장하여 자식 노드 수를 부모 노드 보다 많게 구현한 것임

balanced tree의 대표적인 예
: 같은 깊이의 subtree의 높이 차이가 1이하

B+-tree

B트리와 매우 유사하지만 리프노드가 연결 리스트의 형태로 이루어져있다.
모든 key, data가 leaf node에 뭉처있다.

insert : b-tree와 매우 유사
delete : b-tree와 동일