B+Tree, B-Tree

B+Tree

인덱스가 B+Tree로 되어있는 이유

• 데이터가 리프노드에만 있다
• B-Tree와 다르게 Best, Worst가 없이 탐색의 시간복잡도는 무조건 O(log N)이다
• 리프노드는 연결 리스트의 형태로 되어있어서 인접한 다음 노드에 바로 접근 가능하다. (B-Tree와 다르게 선형 탐색 가능)

B-Tree

비교

구분	B-tree	B+tree
데이터 저장	리프 노드, 브랜치 노드 모두 데이터 저장 가능	오직 리프 노드에만 데이터 저장 가능
트리의 높이	높음	낮음(한 노드 당 key를 많이 담을 수 있음)
풀 스캔 시, 검색 속도	모든 노드 탐색	리프 노드에서 선형 탐색
키 중복	없음	있음(리프 노드에 모든 데이터가 있기 때문)
검색	자주 access 되는 노드를 루트 노드 가까이 배치할 수 있고, 루트 노드에서 가까울 경우, 브랜치 노드에도 데이터가 존재하기 때문에 빠름	리프 노드까지 가야 데이터 존재
링크드 리스트	없음	리프 노드끼리 링크드 리스트로 연결

 

데이터 삽입, 삭제 성능이 느린 이유

트리의 균형을 유지하면서 데이터를 삽입, 삭제해야 하기때문

삽입

• 데이터를 삽입할 적절한 위치를 찾은 후 리프 노드에 삽입
• 리프 노드가 가득 차 있으면 새로운 데이터를 삽입할 공간이 없기 때문에 노드는 분할되어야 하며 분할 후 중간 값이 부모 노드로 상승 되어야 함
• 이 과정에서 부모 노드가 가득 차면 부모 노드도 분할되고 그 결과가 반복되며 트리의 높이가 증가할 수 있음
• 최악의 경우 루트 노드까지 분할이 발생하여 트리의 높이가 하나 증가하는 일이 발생

삭제

• 데이터가 포함된 노드를 찾고 제거한 후 해당 노드가 부족한 최소 키 수를 갖게 되면 병합이 필요할 수 있음
• 노드가 부족해지면 인접한 형제 노드와 병합해야 함
• 병합 작업은 트리의 균형을 맞추기 위해 추가적인 트리 재조정을 요구할 수 있음
• 병합이 이루어지면 부모 노드에 영향이 가고 부모 노드의 키가 변경되거나 삭제되면 부모 노드도 재조정이 필요해질 수 있음. 이 때 발생하는 트리 재조정이 삭제 작업의 시간 복잡도를 증가시킬 수 있음
• 병합이 불가능한 경우 형제 노드와 재배치가 일어날 수 있으며 이 작업도 부모 노드에 영향을 미칠 수 있어 부모 노드가 다시 변경될 수 있음