B-tree의 시간복잡도(검색,삽입,삭제)

 

1. 검색 (Search)

• 최악의 경우: O(logN)
• 설명: B-트리는 M차 트리로 각 노드는 최대 M개의 자식을 가질 수 있다. 트리의 높이는 logN에 비례하므로, 검색 연산의 시간 복잡도는 O(logN)이다. 이는 각 레벨에서 이진 탐색을 사용해 최악의 경우 O(M)의 시간이 추가로 필요할 수 있지만, 일반적으로 M은 작기 때문에 시간 복잡도는 여전히 O(log N)에 가깝다.

2. 삽입 (Insertion)

• 최악의 경우: O(logN)
• 설명: 삽입 연산 시 먼저 적절한 리프 노드를 찾아야 하며, 이는 검색과 동일하게 O(logN)의 시간 복잡도를 가진다. 이후 노드 분할이 필요할 경우, 분할 연산은 상수 시간 내에 수행되므로 전체 삽입 연산의 시간 복잡도는 O(logN)이다.

3. 삭제 (Deletion)

• 최악의 경우: O(logN)
• 설명: 삭제 연산도 먼저 적절한 노드를 찾아야 하므로 O(logN)의 시간 복잡도를 가진다. 이후 키를 삭제하고 필요시 노드를 병합하거나 재조정하는 과정이 필요한데, 이 역시 상수 시간 내에 이루어지므로 전체 삭제 연산의 시간 복잡도는 O(logN)이다.