서론 - 인덱스에서 쓰이는 B tree가 뭔데? Tree 구조는 기본적으로 탐색시 시간복잡도 O(log N)을 가진다.  하지만 최악의 경우, 트리 노드가 한쪽 방향으로 쏠려서 O(N)을 가지게 된다.이런 경우를 방지하기 위해서 Balanced Tree를 이용한다.  balanced tree : 노드 삽입 및 삭제시 특정 규칙에 맞게 재정렬되어 양쪽 자식 수의 밸런스를 유지하는 트리최악의 경우에도 각 연산이 무조건 O(log N)를 보장하며 redblack-tree나 b-tree가 여기에 해당한다.   본론 - 각 자료구조간 비교를 통해 확인해보자데이터베이스의 인덱스에서는 위의 B tree와 B+tree 자료구조를 채택해서 사용하고 있다. 그렇다면 다른 자료구조도 많은데 왜 하필 저 녀석들을 사용할까? ..