Hello!! Kyle

[Data Structure] B-tree 정의 및 장/단점 본문

Programming/Data Structure

[Data Structure] B-tree 정의 및 장/단점

기타치는 개발자 MB Kyle KWON 2015.12.02 14:08

검색을 위한 자료구조 중에 잠재력이 가장 큰 것은 역시 트리이다. 그 중 이번 포스팅에서는 B-tree에 대해 알아볼 것이다. B-tree는 주로 데이터베이스에서 인덱스를 저장할 때, 많이 사용된다. 이번 포스팅을 찾은 사람 중에 인덱스 관련 글을 보던 중, B-tree에 대해 궁금해져 찾아온 사람도 있을 것이다. 그럼 B-tree에 대해 알아보자.


B-tree의 정의

- 모든 노드는 최대 m개의 자식들을 가진다.

- 루트노드와 리프노드가 아닌 모든노드는 최소 m/2개의 자식을 가진다.

- 루트노드는 최소 2개 이상의 자식을 가진다.

- k개의 자식을 가진 리프노드가 아닌 노드는 k-1개의 키를 가진다.

- 모든 리프노드들은 같은 높이에 있어야 한다.

- 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있다.


B-tree의 장점

- 노드의 삽입/삭제 후에도 균형 트리 유지로 균등한 응답 속도를 보장 

- 시간 복잡도 : O(logN)


B-tree의 단점

- 삽입/삭제 시 트리의 균형을 유지하기 위해 복잡한 연산 수행이 필요






알고리즘

검색

- 이진 탐색 트리와 비슷하게 루트노드부터 재귀 호출을 활용하여 탐색을 한다.


삽입

- 해당 원소가 들어가야하는 리프노드를 찾는다.

- 노드에 빈 자리가 있다면 새로운 원소를 삽입한다.

- 노드에 빈자리가 없다면 해당 노드를 2개로 분할한다. 

- 기존 노드의 원소와 새로운 원소 중에 중간 값을 분할된 부모 노드의 값으로 한다.

- 중간 값보다 낮은 값은 왼쪽 노드에 넣고, 큰값은 오른쪽 노드에 넣는다.

- 중간 값을 부모 노드로 넣을 때, 부모 노드에 자리가 없으면 부모 노드도 위의 규칙에 의거하여 분할한다.






삭제 (리프노드)

- 삭제하려는 값을 검색

- 리프노드의 값이면 삭제

- 재배열이 필요한 경우, 재배열 실행


삭제 (중간노드)

- 내부 노드의 값은 하위 노드의 구분 값으로 사용되기 때문에 대체할 수 있는 값이 필요

- 삭제될 값의 자리는 왼쪽 노드의 최대값 혹은 오른쪽 노드의 최소값으로 대체

- 대체된 원소가 원래 있던 노드의 원소가 필요한 만큼 존재하지 않을 경우, 리프노드부터 재배열 실행





참고 : http://arisu1000.tistory.com/27715

0 Comments
댓글쓰기 폼