B tree의 개념과 특징, 데이터 삽입

[B Tree] - DB 인덱스과 관련있는 자료 구조

• BST(이진 탐색 트리)의 경우 가질 수 있는 최대 자녀 노드의 수는 2개다.
• 여기서 응용해서, 자녀 노드의 최대 개수를 늘리고 싶다면? -> B tree
  - 즉, B 트리는 BST를 일반화한 트리라고 할 수 있다.
• 자녀 노드가 3개일 경우 값의 범위를 정해줘야 하기 때문에 key값은 2개를 갖는다.

B Tree 에서의 삽입 조건

• 추가는 항상 leaf node에 한다.
• 노드가 넘치면(노드가 가질 수 있는 최대 key 수를 초과하면) 좌우 key를 분할하고 가운데 key를 부모노드로 올려보낸다.
• key는 항상 오름차순 정렬을 유지한다.

삽입과정에서 알아본 B Tree 특징

• leaf node가 모두 항상 같은 레벨에 존재한다.
  - 즉, balanced tree다. (참고로, BST는 balanced tree가 아님)
  • 이것이 의미하는 바?
    -> 조회 worst case가 O(log N)이 된다는 점!