CS/데이터베이스

[DB] 인덱스에서 B-Tree를 쓰는 이유

데이터베이스의 탐색 성능을 좌우하는 인덱스. 인덱스를 사용하는 이유? 대부분의 속도 저하는 바로 Select문 특히 조건 검색 Where절에서 발생하는데 가장 먼저 생각해 볼 수 있는 대안으로 Index가 존재 그렇다면 왜 B-Tree자료구조를 사용할까? 먼저 자료구조에서 트리란 무엇인가에 대하여 알아보자. Tree는 평균적으로 시간 복잡도 O(logN)을 가진다. 하지만 최악의 경우 한 쪽으로 쏠려버린 트리다 최악의 탐색 시간 O(N)을 가지게 되어버린다. 이걸 방지하기 위해 밸런스 트리(Balanced Tree)를 이용하기도 한다. 밸런스 트리(Balanced Tree)란? 트리의 노드가 한 방향으로 쏠리지 않도록, 노드 삽입 및 삭제 시 특정 규칙에 맞게 재정렬되어 왼쪽과 오른쪽 자식 양쪽 수의 밸..