[2019.04.03]자료구조- B-tree

B-tree는 일반적인 이진트리와 다르게 하나의 노드에 다수의 키를 가지고 있다. 자식을 두개만 가질 수 있는 이진트리를 확장하여 더 많은 수의 자식을 가질 수 있게 만든 방식이다.

b-tree의 조건

• 모든 단말노드는 동일한 높이를 가진다.
• 각 내부노드의 자식노드는 M/2 이상 M 이하이다.
• 루트의 자식 수는 2 이상이다.

B-tree 탐색

위 노드에서 40인 값을 찾을 시, 최상위 노드부터 탐색을 한다. 50보다 작으므로 왼쪽 노드로 이동한다. 왼쪽 노드로 가니 10, 25가 있다. 둘 중 큰 숫자인 25보다 크므로 오른쪽 자식 노드로 내려간다. 30,35,40,45값 중 40을 찾게 된다.

B-tree 삽입

25라는 값을 추가하기 위해 트리를 탐색한다. 삽입을 할 위치를 찾아보니, 해당 노드에는 더이상 삽입을 할 수 없는 위치이다. 그러므로 트리 분배를 시행한다. 노드 중 중간 키인 23을 기준으로 잘라서 상위로 올린다. 그리고 상위노드에서도 중간키를 기준으로 잘라서 상위로 올린다.

B-tree 삭제 및 이동  연산

5라는 키를 삭제하려 한다. 그러나 5는 중간 노드에 위치해 있는 키다. 그래서 노드 이동을 해줘야 한다. 해당 삭제할 노드의 중간 하위 노드인 6,7중 6과 자리를 변경한다. 그리고 오른쪽 노드의 맨 왼쪽 키를 위로 올리고 상위노드에서는 제일 오른쪽 노드를 중간 하위로 보낸다.