B - Tree

왜 DB는 B - Tree를 선택했을까?

Worse case of Tree algorithm:

: Worse case of Tree algorithm처럼 트리노드의 요소가 한쪽 방향으로만 쏠려 있다면 최악의 탐색시간(O(N))을 가지게 된다. 이러한 경우를 방지 하기 위해 밸런스 트리를 이용한다.

밸런스트리란?

노드의 방향이 한방향이 아닌 왼쪽과 오른쪽 자식 양쪽 수의 밸런스를 유지하는 트리로 노드 삽입 및 삭제 시 특종 규칙에 맞게 재정렬되어 있는 자료구조이다.
항상 양쪽 자식의 밸런스를 유지하므로, 무조건 O(logN)의 시간 복잡도를 가지게 된다.

장점: 탐색에 대한 성능을 높힘

단점: 재정렬되는 작업으로 인해 노드 삽입 및 삭제 시 일반적인 트리보다 성능이 떨어짐

종류: RedBlack-Tree, B-Tree가 있음

밸런스 트리는 최악의 경우에도 O(logN)이므로 탐색시간에 매우 효육적인 자료구조이다. 그래서 DB의 인덱스는 밸런스트리 그중 B-Tree를 선택함

B-Tree의 구조

B - tree의 장점

1. 균일성:

어떠한 값에 대해서도 같은 시간에 결과를 얻을 수 있다.

2. 데이터로드 효율성:

데이터가 많은 경우 메모리에 트리구조를 유지하기 보다는 외부장치에 데이터를 저장한다.
각 노드의 값을 파일로 저장하고 파일정보만 저장하고 있다면 메모리에서도 충분히 트리를 유지할 수 있다.
외부장치에서 데이터를 읽어 올때 데이터의 크기 상관없이 그 크기만큼 읽어온다. 즉 노드의 데이터를 특정 블럭 크기 만큼 지정하여 저장 할 수 있다면 효율적으로 데이터를 읽어올 수 있다.