B-Tree

정의

특징

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

• 노드 내 key들을 오름차순으로 정렬한다.

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

• internal 노드의 key 수가 x개면, 자녀 노드의 수는 항상 x + 1개
• → 몇 차 B tree인지와 관계없이 internal 노드는 최소 두개의 자녀를 가진다.

• 모든 leaf 노드들은 같은 레벨에 있다.

• balanced tree

시간복잡도

파라미터

사용

삽입

1. 삽입은 항상 leaf 노드에 한다.

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

삭제

1. 삭제는 항상 leaf 노드에 한다.
1. internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제
1. predecessor(선임자)나 successor(후임자)와 위치를 바꾼다.

2. 삭제 후 최소 key 수보다 적어졌다면 재조정한다.
1. key 수가 여유있는 형제의 지원을 받는다.
2. a가 불가능하면 부모의 지원을 받고 형제와 합친다.
3. b 이후 부모에 문제가 있다면 다시 재조정 한다.

예시

DB Index

B-tree 계열을 사용하는 이유

1. Second Storage 접근 횟수 감소

2. 데이터를 찾을 때, 탐색 범위를 빠르게 좁힐 수 있다.(자녀 노드수를 설정할 수 있으므로)

3. 운영체제에서 데이터를 가져올 때 block 단위로 가져오는데, B-tree 계열은 서로 같이 있으므로 한번에 같이 가져올 가능성 증가(block 단위에 대한 저장 공간 활용도가 더 좋다.)

4. M(각 노드의 최대 자녀 노드 수)를 정하면, 다른 모든 파라미터들이 결정됨

Hash Index 안쓰는 이유

출처