MySQL에서 인덱스(Index)는 데이터 검색을 더 빠르게 하기 위해 사용하는 것으로, 데이터베이스의 색인이라고 생각하면 됩니다.
B-Tree(Balanced Tree)는 데이터가 저장된 노드를 여러 층으로 구성하고, 각 층에 대한 인덱스 값을 기준으로 탐색하는 방식입니다. 이러한 구조는 데이터의 양이 많은 경우에도 빠른 검색이 가능하며, 인덱스 값을 기준으로 범위 검색이 가능하여 WHERE 절에서의 검색 조건에 맞는 레코드를 빠르게 찾을 수 있습니다. 또한, B-Tree는 데이터가 삽입, 삭제될 때마다 인덱스를 재정렬하지 않아도 되기 때문에 성능이 유지됩니다.
MySQL에서는 B-Tree 이외에도 해시 인덱스(Hash Index) 등 다양한 인덱스 알고리즘을 지원합니다. 하지만, 대부분의 상황에서 B-Tree 인덱스가 최적의 선택입니다.
예를 들어, 특정 테이블의 컬럼을 인덱스로 설정하면, 해당 컬럼을 기준으로 검색할 때 레코드를 빠르게 찾을 수 있습니다. 이렇게 인덱스를 설정하면 검색 속도가 향상되므로, 대용량의 데이터를 빠르게 검색할 수 있습니다.
시간 복잡도
B-Tree의 시간 복잡도는 일반적으로 O(log n)입니다. B-Tree는 데이터가 저장된 노드를 여러 층으로 구성하고, 각 층에 대한 인덱스 값을 기준으로 탐색하기 때문에 노드의 수가 적어도 log n 개 이상 필요합니다. 이렇게 구성된 B-Tree에서 검색, 삽입, 삭제 등의 연산은 모두 O(log n)의 시간 복잡도를 가집니다.
공간 복잡도
공간 복잡도는 B-Tree의 구조에 따라 달라집니다. B-Tree의 노드는 일반적으로 하나의 블록 크기에 맞추어서 저장되며, 이 블록의 크기는 데이터베이스마다 다르게 설정될 수 있습니다. 따라서, B-Tree의 공간 복잡도는 데이터의 크기, 블록의 크기, 노드의 크기 등에 따라 달라집니다. 하지만, 일반적으로 B-Tree는 데이터의 양이 증가하더라도 공간을 효율적으로 사용하여 메모리 낭비를 최소화합니다.
