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

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

• 자녀 노드는 최대 2개까지 가질 수 있다.
• BST 방식을 응용해 자식을 늘리고자 BST 방식 등장

B tree

• 자녀 노드의 최대 개수를 늘리기 위해 부모 노드에 key를 하나 이상 저장한다.
• 부모 노드의 key들을 오름차순으로 정렬한다.
  • 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정된다.
• 자녀 노드의 최대 개수를 입맛에 맞게 결정해서 쓸 수 있다.
• B tree는 BST를 일반화한 tree

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

• M : 각 노드의 최대 자녀 노드 수
• M-1 : 각 노드의 최대 key 수
• M/2(올림) : 각 노드의 최소 자녀 노드 수 -> root, leaf 노드 제외
  • leaf node : 자녀 노드가 없는 노드
  • root node : 시작 노드, 출발점이기에 만족하지 않아도 됨
• M/2(올림)-1 : 각 노드의 최소 key 수 -> root노드 제외

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

• leaf node 제외
• 노드가 최소 하나의 key는 가지기 때문에, 몇차 B tree 인지는 상관 없이 internal 노드는 최소 두 개의 자녀는 가진다.

몇차 B트리인지 나타내는 M이 정해자면, root노드를 제외하고 최소 M/2(올림)개의 자녀 노드를 가질 수 있음
ex) M : 5차 -> 각 노드들은 최소 3개의 자녀 노드를 가져야 함

B tree 데이터 삽입

• 추가는 항상 leaf 노드
• 노드가 넘치면(M-1의 키보다 더 많은 키를 저장) 가운데 key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진한다.
  • 노드가 넘친다 : M차(최대 자녀 노드 수), M-1(최대 키의 값) -> M-1개 보다 더 많은 수의 키를 저장할 때

balanced tree의 특징을 가짐 : 모든 리프노드들은 같은 레벨에 있다.

• BST : 최악의 경우 한쪽으로 쏠릴 수도 있는 반면
• B트리는 항상 모든 리프노드들은 같은 레벨에 있음
  => 조회 시 항상 일정한 성능 O(log N)