[DB] B-Tree vs B+Tree

B-Tree

• (데이터 저장) 모든 내부, 리프 노드에 저장

• (중복 키) 없음

• (검색) 리프 노드뿐만 아니라 브랜치 노드에도 데이터가 저장되어 느린 경우가 있음

• (삭제) 내부 노드의 데이터 삭제가 느리고 복잡함

• (리프 노드) 리프 노드끼리 연결 x

• 균형 트리 balanced tree

B+Tree

• (데이터 저장) 리프 노드에만 저장

• (중복 키) 있음

• (검색) 데이터가 리프 노드에만 있어 비교적 빠름

• (삭제) 리프 노드에서만 삭제하면 되므로 빠름

• (리프 노드) 링크드 리스트로 연결되어 검색 기능이 효율적

• 하나의 노드에 더 많은 key를 담을 수 있어 트리의 높이가 낮아짐

출처: https://www.javatpoint.com/b-plus-tree