(1부) B tree의 개념과 특징, 데이터 삽입이 어떻게 동작하는지를 설명합니다! (DB 인덱스과 관련있는 자료 구조)

B tree 개념과 특징

(복습) 이진 탐색 트리(BST)

• BST의 자녀 노드는 최대 두 개까지이다.

• 자녀 노드를 세 개까지 가지고 싶다면?
  • 부모 노드에 key를 하나 이상 저장한다
  • 부모 노드의 key들을 오름차순으로 정렬한다
  • 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정된다

이를 구현한 것이 B tree이다. B tree는 BST를 일반화한 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 제외

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

B tree 데이터 삽입 방식

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

3차 B tree 예제

모든 leaf 노드들은 같은 레벨에 있다.

-> balanced tree
-> 검색 avg/worst case O(logN)