B-Tree 인덱스
B-Tree는 밸런스 트리(Balanced Tree)를 말하는데 가장 대표적으로 쓰이는 인덱스 자료 구조이다.
트리의 노드가 한 방향으로 쏠리지 않도록, 노드 삽입 및 삭제 시 특정 규칙에 맞게 재정렬되어 왼쪽과 오른쪽 자식 양쪽 수의 밸런스를 유지하는 트리이다.
B-Tree를 사용하는 이유
항상 양쪽 자식의 밸런스를 유지하므로, 무조건 O(logN)의 시간 복잡도를 가지게 된다. 다만 재정렬되는 작업으로 인해 노드 삽입 및 삭제 시 일반적인 트리보다 성능이 떨어지게 된다. 그러므로 밸런스 트리는 삽입/삭제의 성능을 희생하고 탐색에 대한 성능을 높였다고 볼 수 있다.
Binary Tree 사용할 경우
2진 트리 구조상 트리 모양이 한쪽으로 치우쳐지게 될 수 있는데 트리 탐색의 장점인 O(logN) 시간복잡도가 마치 배열을 순차탐색 하듯 하는 O(N)에 가까워지게 된다.
해시 테이블 사용할 경우
해시 테이블은 해시 함수를 통해 나온 해시 값을 이용하여 저장된 메모리 공간에 한 번에 접근을 하기 때문에 O(1)이라는 시간 복잡도를 가진다. 그러나 탐색시간이 제일 빠른 해시 테이블을 사용하지 않는 이유는 단 하나의 데이터를 탐색하는 시간만 O(1) 이기 때문에 탐색을 할때 여러개의 데이터를 조회하는 경우(> or <)에는 사용 할 수 없다.
배열을 사용할 경우
배열은 조회의 면에서 매우 빠르지만 일반적인 배열에서 삽입과 삭제는 큰 비용이 든다. 중간에 어떤 값을 삽입 혹은 삭제 할 경우 전체 데이터를 뒤로 혹은 앞으로 한 칸씩 이동하는 과정에서 평균 시간 복잡도가 O(N)이 걸리게 된다.
LinkedList를 사용할 경우
배열을 사용할 수 없다면 LinkedList를 사용하자고 할 수 있지만 탐색을 무조건 제일 앞 부분인 'HEAD'부터 시작해야 하는 LinkedList로서는, DB-Index로 사용하기엔 매우 비효율적인 자료구조가 된다.
출처
