JH-Labs

Balanced Tree (불균형) 이진탐색트리의 문제점은 최악의 경우 O(N)이 발생한다는 것이다. Balanced Tree는 항상 균형을 맞추어진 상태로 유지함으로써 O(logN)의 성능을 보인다. 하지만 데이터의 삭제, 삽입, 갱신이 발생할 때 Balance를 유지하기 위한 연산이 추가로 필요하게 된다는 단점이 있다. Balanced Tree의 종류로 AVL Tree와 레드블랙트리, 2-3 Tree, 2-3-4 Tree, B Tree 등이 있다. B-Tree는 다차원트리 B-Tree는 Balanced Tree이면서 다차원 트리이다. 하나의 노드가 가질 수 있는 자식 노드의 개수(링크 개수)를 M이라고 했을 때 하나의 노드에 '최대' M-1개의 자료를 담을 수 있으며 이 경우 M차 다차원 트리라고 한..

Balanced Tree - 한쪽으로 노드가 몰리는 Binary Search Tree의 단점을 보완하고자 등장 - DBMS에서 가장 범용적으로 사용되는 자료구조 - Binary Search Tree와 유사하지만 depth를 자동으로 잡아주기 때문에 탐색 시간복잡도가 O(logN)을 보장함 - 하지만 depth에 영향을 줄 수 있는 insert, delete 경우에 대해서는 성능이 좋지 않을 수 있음 - 결론적으로, 데이터를 얼마나 자주 삽입, 삭제할 것인가에 따라서 B-Tree Index를 활용할지 말지를 결정 - 즉, 갱신 빈도가 높은 테이블에 인덱스를 지정할 경우, 인덱스 재구성 발생 빈도가 높아진다는 점을 고려해야 함 B-Tree - 하나의 노드에 여러개의 값이 배치되는 구조의 트리 - 차수 M의 ..