데이터 인덱스를 어떤 자료구조로 정렬하냐에 따라 탐색 시간이 달라진다. 일반적으로 많이 사용되는 구조가 B+Tree이다.
B+Tree는 아래와 같은 특징을 갖는다.
- 작은 값은 왼쪽 자식, 크거나 같은 값은 오른쪽 자식에 속한다.
- Leaf 노드만 데이터 포인터이며, 내부의 노드는 인덱스를 찾기 위한 역할을 한다. 만약 트리 내부에 7이 있더라도 Leaf 노드에 7이 없다면 데이터를 찾을 수 없다.
- Leaf 노드는 연결 리스트로 연결된 선형 구조를 가진다. 0 → 5 → 6 → 8 → ...
- 하나의 노드에 저장할 수 있는 최대 인덱스 개수를 fanout이라고 한다. 위 그림은 fanout이 4이다.
- fanout이 f이고, 데이터가 N개일 때, $\left \lceil log_fN \right \rceil$ 단계만 거치면 탐색이 가능하다.
- 하나의 노드는 반드시 (fanout / 2)개 이상의 값을 가져야한다.
- Leaf 노드의 level이 동일하도록 균형(Balance)을 맞춰주는 것이 탐색에 유리하다. 편향된 트리는 효율성을 떨어뜨리며, level이 작을수록 탐색이 빨라진다.
삽입
인덱스 범위에 따라 값을 삽입한다.
노드에 더 이상 값을 삽입할 수 없을 때,
→ 노드를 반으로 나누어 2개로 만든다.
→ 오른쪽 노드의 최솟값을 부모 노드에 삽입한다.
→ 부모 노드가 가득찼을 때, 같은 동작을 반복한다.
8을 삽입하는 경우:
균형 찾기
B+ Tree는 하나의 노드에 (fanout/2)개의 값을 가져야한다. 값을 삭제했을 때, 노드의 수가 감소하며 균형이 무너질 수 있기 때문에 균형을 찾는 과정이 필요하다.
노드의 값이 fanout의 절반 이하라면,
→ 오른쪽 형제 노드가 fanout의 절반을 초과할 때,
→ 오른쪽 형제 노드의 값을 가져오고, 형제 노드의 최소값을 부모 노드에 업데이트해준다.
→ 오른쪽 형제 노드도 fanout의 절반 이하라면,
→ 오른쪽 형제 노드와 병합하고, 부모 노드와 링크를 삭제한다.
삭제
삭제는 Leaf 노드에서 값을 삭제하고, 균형을 맞춰주면 끝난다.
17을 삭제하는 경우:
참고
B* Tree는 fanout의 2/3을 채우는 B Tree이며, 이때 삽입·삭제에서 split이나 merge가 덜 발생한다.