B-tree

binary search tree 에서 파생된것으로

BST에서 자식노드의 갯수에 제한을 없앤것이 b-tree이다

자식노드의 갯수가 3개 이상이려면
부모노드의 key도 하나 이상이어야한다

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

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

                  [20 40]
               /     |      \
        [10 15]   [30 35]   [50 60 70]
       /    |     /    |     |      \
    [5 7] [12] [25] [32] [45]  [55 65 75]

자식노드의 갯수에 따라 n차 b-tree로 불리는데
위의 예시는 자식노드가 3개이므로 3차 B-tree이다

key에 의해서 자식노드들의 범위가 정해진다

왼쪽: 20 > x,
가운데: 20 < x < 40
오른쪽: 20 < x

B-tree의 중요한 파라미터들로는

• M : 최대로 가질 수 있는 자식노드의 수, M에 따라 M차 B-tree로 불린다, 위의 예시에서는 3
• M-1 : 각 노드의 최대 key의 수 : 노드에 들어있는 숫자의 갯수를 말함, 3차 b-tree는 최대 2개까지 들어있을 수 있다
• ⎡M/2⎤: M/2의 올림, M이 3일때 2 : 각 노드의 최소 자녀 노드 수
  (leef, root노드는 제외)
• ⎡M/2⎤-1: 각 노드의 최소 key 수, 예시에서는 1
  (root node제외)
• b-tree에서 internal node의 key가 x라면 자식노드의 수는 x+1

시간복잡도

O(logN)의 시간 복잡도를 가짐
N은 테이터의 갯수

만약 데이터가 100개일 때, 3차 B-tree라면 $$\log_3 100$$ 으로 4~5의 값이 나오고
그럼 높이가 4개에서 5개정도가 나오고 시간 복잡도도 그정도 나온다