26. B tree 1부 : 개념, 특징, 데이터 삽입

본 내용은 유튜버 쉬운코드의 강의 "데이터베이스"를 참고하여 작성하였습니다.

 

BST 복습

이진 탐색 트리(Binary Search Tree) : 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가짐.

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

이진 탐색 트리 예제

 

• 자녀노드를 세 개 가지게 만들려면? -> 기준점이 되는 값이 2개(k1, k2)가 필요함.

---

B tree

• 자녀 노드의 최대 개수를 늘리기 위해 부모 노드에 key를 하나 이상 저장
• 부모 노드의 key들을 오름차순으로 정렬
• 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정됨.
• 위의 방식을 사용하게 되면 자녀 노드의 최대 개수를 입맛에 맞게 결정해서 쓸 수 있다.

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

---

B tree 주요 파라미터

1. M : 각 노드의 최대 자녀 노드 수
   • M차 B tree : 최대 M개의 자녀를 가질 수 있는 B tree
2. M-1 : 각 노드의 최대 key 수
3. 올림(M/2) : 각 노드의 최소 자녀 노드 수 (root node, leaf node 제외)
4. 올림(M/2)-1 : 각 노드의 최소 key 수 (root node 제외)

• 1번이 정해지면 2~4번은 자동으로 결정됨.
• 어떤 파라미터를 기준 파라미터로 잡을지는 다를 수 있음.

---

B tree 노드의 key 수와 자녀 수의 관계

• internal 노드의 key 수가 x개라면 자녀 노드의 수는 언제나 x+1개다.
  -> 노드가 최소 하나의 key는 가지기 때문에 몇 차 B tree인지와 상관없이 internal 노드는 최소 두 개의 자녀는 가진다.
  -> M이 정해지면 root 노드를 제외하고 internal 노드는 최소 올림(M/2)개의 자녀 노드를 가질 수 있게 된다.

이런 모양은 안됨.

---

B tree 데이터 삽입

• 추가는 항상 leaf 노드에 한다.
• 노드가 넘치면 가운데(median) key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진한다.

---

3차 B tree의 데이터 삽입 예제

1 추가 15 추가 2 추가 트리 분리		8 추가 10 추가 트리 분리 트리 분리
5 추가 30 추가 트리 분리		50 추가 70 추가 트리 분리
90 추가 20 추가 트리 분리 트리 분리		60 추가 40 추가 트리 분리 트리 분리
7 추가 9 추가 트리 분리		트리 분리(최종)

• 추가할 때 오름차순으로 정렬
• 모든 leaf 노드들은 같은 레벨에 있다.
  -> balanced tree
  -> 검색 avg/worst case : O(log N)

 

]

50 추가 70 추가 트리 분리
60 추가 40 추가 트리 분리 트리 분리
트리 분리(최종)