Balanced Tree, B Tree (Data Structure)

참조한 것들

• 어떤 B-Tree 소개 블로그 글
• 어떤 Index, B+Tree 소개 블로그 글

Balanced Tree 의 필요성 §

• BST 를 생각해 보면 일반적인 경우에는 탐색의 시간복잡도가 log2(n) 이지만
• 최악의 경우인 모든 노드가 치우쳐져있는 경우 (전부 일렬로 연결되어 있는 경우) 에는 탐색의 시간복잡도는 n 이 된다.
• 따라서 트리가 항상 균형을 이루는 상태 (모든 Leaf 노드가 같은 레벨에 존재하는 상태) 로 유지될 수 있게 한다면, 어떤 경우에도 시간복잡도는 logx(y) 일 것이다.
• 이렇게 트리가 항상 균형을 이루는 트리를 Balanced Tree (BTree) 라고 한다.

B-Tree (B minus tree) §

B+ Tree

• … 는 DB 의 Index 에서 많이 사용되기 때문에 여기 에서 설명하겠읍니다.

• B-Tree 는 Balanced Tree 의 일종인데
• B-Tree 의 경우에는 자식이 2개 이상일 수 있고 노드의 Key 는 1개 이상일 수 있다
  • 여기서 Key 가 뭐냐면
  • BST 의 경우에는 Key 가 1개라고 말할 수 있다
    • 1개의 키를 기준으로 그것보다 크면 오른쪽으로 내려가고 작으면 왼쪽으로 내려가자네
  • 이제 B-Tree에서는 이러한 키가 여러개가 될 수 있다는 거임 → 뭐 예를 들어서 키가 n, m으로 2개면 n보다 작으면 왼쪽으로, n 보다 크거나 같고 m 보다 작으면 중간으로, m 보다 크면 오른쪽으로 내려가는 식
  • 성질이 이렇기 때문에 키는 반드시 오름차순으로 정렬되어 있어야 하고 키의 갯수보다 하나 많은 자식 노드를 가질 수 있다
• 한 노드가 가질 수 있는 자식의 최대 개수가 M 라면 그걸 M차 B-Tree 라고 부른다
  • 따라서 위에서 설명한 것을 토대로 생각해보면 한 노드에 들어갈 수 있는 키의 최대 갯수는 M - 1 개 이다.
• 정리해보면 M차 B-Tree 의 조건은 다음과 같다
  1. 루트와 리프를 제외한 Node 중 어떤 한 Node 의 Key 개수가 k라면 (1 ≤ k ≤ M - 1) 자식의 개수의 범위는 M / 2 ~ k + 1 이다.
     • 모든 Node 의 키의 개수가 동일하지 않아도 된다 (k 는 노드마다 다를 수 있다는 것)
  2. Node 의 Key 는 정렬된 상태로 존재해야 한다
  3. 자식 Node 들의 Key 는 현재 Node 의 Key 를 기준으로 나뉜다
     • 이말이 결국에는 이말과 같은소리임
     • 이제 B-Tree에서는 이러한 키가 여러개가 될 수 있다는 거임
     • 뭐 예를 들어서 키가 n, m으로 2개면 n보다 작으면 왼쪽으로, n 보다 크거나 같고 m 보다 작으면 중간으로, m 보다 크면 오른쪽으로 내려가는 식
  4. 모든 Leaf Node 들은 같은 Level 에 존재한다.