트리의 활용

트리를 이용한 DB 설계의 장 / 단점 및 트리의 한계 해결

DB를 설계할 때 주로 사용되는 자료구조는 B-Tree이다.

• [ ] 다른 자료구조를 DB로 사용 할 수 없는 이유

 

1. 해시 테이블의 경우

해시 테이블은 단 하나의 데이터를 탐색하는데 O(1) (최악의 경우 O(N)이지만 평균적으로 O(1))의 시간복잡도를 가지만, DB에서는 등호(=) 뿐만 아니라 부등호(<, >)도 사용

→ O(1)의 시간복잡도를 보장 할 수 없고, 비효율적

   

2. 레드-블랙트리의 경우

레드-블랙트리는 하나의 노드에 하나의 요소를 저장하지만, B - 트리의 경우 하나의 노드에 배열처럼 여러개의 데이터 요소를 저장

→ 같은 공간의 노드를 참조 포인터로 접근 할 필요가 없음 → 동일 메모리에서 작동

→ 두 트리 모두 O(logN)의 시간복잡도를 가지지만, 실제 환경에서는 메모리 주소 참조의 CPU 연산 시간이 생략되어 데이터가 많아질수록 더 많은 성능 차이 발생

 

3. 배열의 경우

💡 배열의 경우 참조 포인터라는 개념 자체가 없고, 모든 데이터가 메모리에 순차로 저장되어 있어 접근이 매우 빠르다. 그렇다면 왜 배열을 사용하지 않을까?

• 배열의 경우 B - 트리보다 탐색속도를 제외한 모든 연산에서 비효율적

위 사진과 같이 배열의 중간에 새로운 데이터를 삽입할 경우 O(N)의 시간복잡도가, 맨 뒤에 저장한다면 O(logN)의 시간복잡도가 발생 → 이는 저장, 삭제에서도 동일

수정의 경우 O(NlogN)의 시간이 발생

 

극복 방법

1. 연산의 속도를 높이기 위해 분산시스템을 구축한다.
2. B-Tree를 이용해 노드의 분열을 줄여서 보조연산의 횟수를 감소시킨다.
3. 데이터를 미리 정리한 후 정리된 상태로 사용한다(Hash)