B+Tree

• 같은 레벨의 모든 키값들이 정렬됨
• 같은 레벨의 sibling node는 연결리스트 형태로 연결되어있음
• 모든 leaf node는 연결리스트로 연결되어 있음
• 키값 중복 X, 탐색 유리
• 블럭 사이즈를 더 많이 이동할 수 있음(key 값에 대한 하드디스크 주소 X)
• 그러나 무조건 leaf node 까지 내려가야함
• 삽입, 삭제 모두 leaf node에서 이루어짐
• 모든 leaf node는 같은 레벨
• leaf node가 아닌 node의 키 값의 수는 그 노드의 서브트리수-1

단말 노드 <> 비단말 노드

• 인덱스 노드 : leaf node가 아닌 자료, value값에 다음 노드를 가리키는 포인터 주소 존재
• 데이터 노드 : lead node 자료, value값에 데이터가 존재

 

References

https://ssocoit.tistory.com/217

[자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree

https://sdesigner.tistory.com/79

B-Tree & B+ Tree 자료구조 알아보기