검색을 위한 자료구조 중에 잠재력이 가장 큰 것은 역시 트리이다. 그 중 이번 포스팅에서는 B-tree에 대해 알아볼 것이다. B-tree는 주로 데이터베이스에서 인덱스를 저장할 때, 많이 사용된다. 이번 포스팅을 찾은 사람 중에 인덱스 관련 글을 보던 중, B-tree에 대해 궁금해져 찾아온 사람도 있을 것이다. 그럼 B-tree에 대해 알아보자.
B-tree의 정의
- 모든 노드는 최대 m개의 자식들을 가진다.
- 루트노드와 리프노드가 아닌 모든노드는 최소 m/2개의 자식을 가진다.
- 루트노드는 최소 2개 이상의 자식을 가진다.
- k개의 자식을 가진 리프노드가 아닌 노드는 k-1개의 키를 가진다.
- 모든 리프노드들은 같은 높이에 있어야 한다.
- 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있다.
B-tree의 장점
- 노드의 삽입/삭제 후에도 균형 트리 유지로 균등한 응답 속도를 보장
- 시간 복잡도 : O(logN)
B-tree의 단점
- 삽입/삭제 시 트리의 균형을 유지하기 위해 복잡한 연산 수행이 필요
알고리즘
검색
- 이진 탐색 트리와 비슷하게 루트노드부터 재귀 호출을 활용하여 탐색을 한다.
삽입
- 해당 원소가 들어가야하는 리프노드를 찾는다.
- 노드에 빈 자리가 있다면 새로운 원소를 삽입한다.
- 노드에 빈자리가 없다면 해당 노드를 2개로 분할한다.
- 기존 노드의 원소와 새로운 원소 중에 중간 값을 분할된 부모 노드의 값으로 한다.
- 중간 값보다 낮은 값은 왼쪽 노드에 넣고, 큰값은 오른쪽 노드에 넣는다.
- 중간 값을 부모 노드로 넣을 때, 부모 노드에 자리가 없으면 부모 노드도 위의 규칙에 의거하여 분할한다.
삭제 (리프노드)
- 삭제하려는 값을 검색
- 리프노드의 값이면 삭제
- 재배열이 필요한 경우, 재배열 실행
삭제 (중간노드)
- 내부 노드의 값은 하위 노드의 구분 값으로 사용되기 때문에 대체할 수 있는 값이 필요
- 삭제될 값의 자리는 왼쪽 노드의 최대값 혹은 오른쪽 노드의 최소값으로 대체
- 대체된 원소가 원래 있던 노드의 원소가 필요한 만큼 존재하지 않을 경우, 리프노드부터 재배열 실행
'Programming > Data Structure' 카테고리의 다른 글
| [Data Structure] 자료구조 (Data Structure) (0) | 2012.12.29 |
|---|