23. B tree - 개념 및 특징, 데이터 삽입

이진 탐색 트리 (BST)

- 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가짐

- 자녀 노드는 최대 두 개까지

 

이런 이진 탐색 트리의 특징을 사용하면서도 자녀 노드의 최대 개수를 늘리기 위해서 B tree를 사용함.

 

B tree

- B tree는 BST를 일반화한 tree

- 자녀 노드의 최대 개수를 늘리기 위해 부모 노드에 key를 하나 이상 저장함

- 부모 노드의 key들을 오름차순으로 정렬함

- 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정됨

이런 방식을 사용하면 자녀 노드의 최대 개수를 입맛에 맞게 결정해서 쓸 수 있음.

최대 몇 개의 자녀 노드를 가질 것인지가 B tree를 사용할 때 중요한 파라미터!!

 

M : 각 노드의 최대 자녀 노드 수

최대 M개의 자녀를 가질 수 있는 B tree를 M차 B tree라고 부름.

M -1 : 각 노드의 최대 key 수

⌈M/2⌉ : 각 노드의 최소 자녀 노드 수

(reoot node, leaf node 제외)

⌈M/2⌉ - 1 : 각 노드의 최소 key 수

(root node 제외)

어떤 파라미터를 기준 파라미터로 잡을지는 다를 수 있음.

 

internal 노드의 key 수가 x개라면 자녀 노드의 수는 언제나 x+1 개임.

노드가 최소 하나의 key는 가지기 때문에 몇 차 B tree 인지와 상관없이 internal 노드는 최소 두 개의 자녀는 가짐.

M이 정해지면, root 노드를 제외하고 internal 노드는 최소 ⌈M/2⌉개의 자녀 노드를 가질 수 있게 됨.

 

B tree 데이터 삽입

- 추가는 항상 leaf 노드에 함

- 노드가 넘치면 가운데(median) key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진함

노드가 넘친다? : 하나의 노드에서 M-1개보다 더 많은 수의 key를 저장하고 있을 때

 

 

데이터 삽입 예시

leaf 노드에 40 추가, leaf 노드가 넘침

60을 새로운 노드에 분할, 오름차순 정렬 위해 70을 빈 노드로 이동, 50은 승진

노드가 넘침, 70을 새 노드에 분할, 50 승진, 오름차순 정렬해서 제일 오른쪽 빈 노드로 50 승진

 

노드가 넘침, 50을 새 노드에 분할, 15 승진, 데이터 삽입 끝

(1, 15, 2, 5, 30, 90, 20, 7, 9, 8, 10, 50, 70, 60, 40 순서로 데이터 삽입)

 

B tree 특징

- 모든 leaf 노드들은 같은 레벨에 있음

- 즉, B tree 는 balanced tree 임

- 검색을 할 때 avg case / worst case 의 시간 복잡도는 O(log N) 임