⌨️

B+Tree

•

B+트리입니다.

•

데이터 노드의 자료는 정렬되어 있습니다.
모든 leaf node는 같은 레벨에 있습니다.
leaf node가 아닌 node의 키값의 수는 그 노드의 서브트리수보다 하나가 적습니다.
모든 leaf node는 연결리스트로 연결되어 있습니다.

•

보통 max degree 는 홀수로 하는게 좋습니다. 올리는 데이터를 중앙값으로 할 수 있기때문에

•

아래의 예시는 일부러 max degree 를 4개를 했을 때

•

각각의 값에 대해 왼쪽부터 input≤값 으로 페이지를 정한다.

•

즉 여기서 4가 들어오면

◦

root: 4≤5 이므로 왼쪽

◦

branch: 4≤4 이므로 왼쪽

◦

leaf: 2≤4≤4 이므로 중앙에 찾기

•

여기서 5가 들어오면

◦

root: 5≤5 이므로 왼쪽

◦

branch: 4≤5≤5 이므로 중앙

◦

leaf: 4≤4≤5 ≤5 이므로 세번째, max 라서 중앙값+1(짝수라서)이 올라감

•

여기서 6이 들어오면

◦

root:5≤6≤6 이므로 중앙

◦

branch: 6≤6 이므로 왼쪽

◦

leaf: 5≤6≤6 이므로 중앙

•

여기서 7이 들어오면

◦

root: 6≤7이므로 오른쪽

◦

branch: 7≤7 이므로 왼쪽

◦

leaf: 6≤6≤7≤7 이므로 세번째, max 라서 중앙값+1이 올라감