대량의 데이터에서 탐색을 진행할 때 B+-Tree가 BST보다 효과적인 이유는 무엇인가?

[anuu0916]

BST는 최악의 경우 한 쪽으로 치우쳐 선형으로 형성되는 skew 형상이 발생할 수 있다. 따라서 왼쪽 subtree와 오른쪽 subtree의 높이를 같게 유지하는 AVL 트리를 사용해 문제점을 사용한다. B+-Tree는 AVL의 한 종류이다.