B+ 트리

B 트리와 유사해 보이지만, B 트리와는 조금 다르다. B 트리의 특성상 순회가 힘든데,
B+트리는 리프 노드를 제외한 노드는 index로 키 값을 찾는데 사용이 된다. 그리고 리프 노드에 데이터를 저장한다.
리프 노드는 연결 노드로 각 leaf노드는 모두 연결되어있다.

장점

• 리프 노드에만 데이터를 저장하고있으므로 리프노드를 제외하고 노드 당 키를 많이 담을 수 있음.
• 링크드 리스트로 연결되어 있어서 리프 노드에서 선형

참고

• B+tree 시각화(https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html)