B-trees

B를 balanced의 약자라고도 말하고 branch라고도 말한다.

B는 한 노드에 들어갈 수 있는 데이터의 개수의 최대값.

• B트리는 왜 필요합니까
• B트리의 탐색 복잡도는 logn입니다.
• 이진트리와 탐색복잡도가 같습니다.
• 다만 메모리 계층을 적게 사용한다.

B 트리가 지켜야 할 점

• 한 노드 당 데이터 수는 B - 1보다 적을 수 없고 2B - 2보다 많을 수 없습니다.
• 한 노드에 연결되는 자식 노드의 개수는 B개보다 적을 수 없고 2B - 1보다 클 수 없습니다.

• 한 노드에 연결되는 B <= #of child < 2B
  B -1 <= #of keys < 2B - 1

• 2-3 Tree
• B = 2
• leaf에서만 자식 개수 위반
• B트리에서 나뉘어지는 자식의 가지수는 부모 값들의 개수 +1이 될 수밖에 없다. 구간을 나누는 눈금라고 생각하자

• insert(16)
• insert(2)

search

insert

q

• 자식의 개수는 총 5개가 되나요?
• 하나의 노드에는 여러개의 값들이 들어갈 수 있습니다. 5개의 자식이 아니고 3개의 자식이됩니다.
• B트리의 B의 값은 어떻게 결정되나요
• 메모리의 상황에 따라서 달라집니다.