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

https://youtu.be/bqkcoSm_rCs

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

  

1. 자녀 노드의 최대 개수를 늘리기 위해서 부모 노드에 key를 하나 이상 저장한다.

2. 부모 노드의 key들을 오름차순으로 정렬한다.

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

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

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

  

M : 각 노드의 최대 자녀 노드 수 => 최대 M개의 자녀를 가질 수 있는 B tree를 M차 B tree라 부른다.

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

M/2의 올림수 : 각 노드의 최소 자녀 노드 수(root node, leaf node 제외)

M/2의 올림수-1 : 각 노드의 최소 key 수(root node 제외)

===> M만 정해주면 나머지는 알아서 정해진다.

  

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

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

  

B tree 데이터 삽입

* 데이터 추가는 항상 leaf 노드에 한다.

* 노드가 넘치면 가운데 key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진한다.

  

모든 leaf 노드들은 같은 레벨에 있다. => balanced tree => 검색 avg&worst case = O(log N)