인덱스

데이터베이스에서 인덱스는 테이블 데이터를 효율적으로 검색하기 위해 사용되는 자료 구조로, 데이터를 빠르게 찾기 위한 추가적인 정보를 생성하고 유지합니다. 이를 통해 데이터 검색 속도가 비약적으로 향상되지만, 쓰기 작업의 성능에는 영향을 줄 수 있습니다. 인덱스는 데이터를 저장하고 검색하는 구조에 따라 여러 유형으로 나뉘며, 각 유형은 특정 사용 사례와 쿼리 패턴에 적합합니다.

인덱스의 구조

1. B-트리 구조

• B-트리는 대부분의 관계형 데이터베이스에서 기본적으로 사용되는 인덱스 구조입니다.
• 특징:
  • 데이터를 정렬된 상태로 유지하며, 검색, 삽입, 삭제 작업에서 O(log n)의 시간 복잡도를 가짐.
  • 노드 안에서 키가 정렬되어 있어 이진 검색처럼 키를 탐색.
  • 노드의 자식 노드로 내려갈 때 포인터를 따라가며 원하는 데이터를 찾음.
• 장점:
  • 범위 검색(BETWEEN, <, >)에 매우 적합.
  • 동등 조건 검색에서도 빠른 성능을 제공.
• 단점:
  • 삽입/삭제 작업이 빈번할 경우 트리의 균형을 맞추는 작업으로 인해 성능 저하 가능.

2. B+트리 구조

• B+트리는 B-트리의 변형으로, 현대 데이터베이스에서 범위 검색이 많은 경우 주로 사용됩니다.
• 특징:
  • 데이터는 리프 노드에만 저장되고, 나머지 노드에는 키와 포인터만 포함.
  • 리프 노드들이 연결 리스트로 연결되어 있어 범위 검색이 더 효율적.
  • 리프 노드 사이를 순회하면서 데이터를 순차적으로 가져오기 쉬움.
• 사용 사례:
  • 정렬된 데이터에 대해 순차적으로 검색하거나 범위 조건을 적용하는 경우.

 

인덱스의 유형

1. 클러스터드 인덱스 (Clustered Index)

• 클러스터드 인덱스는 테이블 데이터 자체가 인덱스와 같은 순서로 정렬되어 저장됩니다.
• 특징:
  
  • 보통은 Primary Key를 만드는 순간 클러스터드 인덱스가 생긴다고 생각하면 됩니다.
  • UNIQUE NOT NULL 옵션으로 컬럼을 만들어도 클러스터드 인덱스가 생길 수 있습니다.
  • 클러스터드 인덱스가 지정이 되는 순간 테이블 내의 모든 데이터는 해당 인덱스 기준으로 정렬이 이뤄집니다.
  • 다만, 클러스터드 인덱스는 테이블에 무조건 1개만 존재할 수 있습니다.
    • 이 때, 우선 순위는 Primary Key > UNIQUE NOT NULL 입니다.
    • 즉, UNIQUE NOT NULL 컬럼이 존재해서 클러스터드 인덱스가 있는 상황에서 Primary Key를 추가하게 되면 클러스터드 인덱스는 Primary Key가 되고 UNIQUE NOT NULL 컬럼은 일반 인덱스로 변합니다.
  • 정렬이 되어 있다는 전제조건이 있기 때문에 검색 시 성능이 매우 빠릅니다.
• 장점:
  • 기본 키(primary key)와 같은 고유 데이터를 빠르게 검색 가능.
  • 범위 검색 및 정렬 작업에 효과적.
• 단점:
  • 삽입, 업데이트 작업이 빈번할 경우 성능 저하 가능.

2. 넌클러스터드 인덱스 (Non-Clustered Index)

• 논-클러스터드 인덱스는 아래와 같이 2개의 페이지로 구성이 됩니다.
  • 데이터 페이지 → 실제 데이터를 담고 있으며 정렬이 되지 않습니다.
  • 인덱스 페이지 → 인덱스 키 및 데이터 행에 대한 포인터를 담고 있으며 정렬된 상태를 유지합니다.

• 특징:
  • 하나의 테이블에 여러 개의 넌클러스터드 인덱스 생성 가능.
  • 특정 열에 대한 검색 속도를 높이는 데 유용.
• 장단점:
  클러스터드 인덱스와 반대로 데이터를 정렬시켜 넣지 않아서 수정,삽입,삭제가 빠르지만 리프노드를 거쳐서 검색해야 하니 검색은 느리다.

3. 해시 인덱스 (Hash Index)

 

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조이다.

해시 테이블 기반의 DB 인덱스는 (데이터=컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현하였다. 해시 테이블의 시간복잡도는 O(1)이며 매우 빠른 검색을 지원한다.

하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그러한 이유는 해시가 등호(=) 연산에만 특화되었기 때문이다. 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.

 

4. 비트맵 인덱스 (Bitmap Index)

• 데이터를 비트맵(bit map) 형식으로 저장.
• 특징:
  • 열의 값이 제한적인 경우(예: 성별, 상태 코드) 매우 효율적.
  • 데이터 삽입, 삭제 작업이 많으면 비효율적.

5. 복합 인덱스 (Composite Index)

• 여러 열(column)을 결합하여 하나의 인덱스를 생성.
• 특징:
  • 다중 열 조건을 자주 사용하는 경우 적합.
  • 열 순서에 따라 성능이 달라질 수 있음.

인덱스의 검색 방식

• Index Full Scan
  • 테이블의 모든 레코드를 순차적으로 검색하는 방식입니다.
  • 혹은, 쿼리 옵티마이저가 인덱스를 사용하지 않는 것이 더 효율적이라고 판단할 때 발생합니다.
  • 일반적인 경우에 테이블의 규모가 조금만 커도 성능이 가장 좋지 않은 스캔 방식입니다.
• Index Unique Scan
  • 유니크 인덱스(클러스터드 또는 논-클러스터드)를 사용하여 검색하는 방식입니다.
  • … WHERE id = 3;과 같은 쿼리(id가 PK또는 UNIQUE 제약조건이 있는 경우)에서 쓰이는 스캔 방식입니다.
  • 특정 값에 대해 정확히 하나의 레코드를 찾을 때 사용이 되고 찾으면 바로 그 순간 검색이 종료됩니다.
  • 항상 효율적인 스캔 방식입니다.
• Index Range Scan
  • 인덱스의 특정 범위 내에서 검색을 수행할 때 사용하는 방식입니다.
  • … WHERE age BETWEEN 30 AND 40; 과 같은 쿼리에서 쓰이는 스캔 방식
  • 클러스터드 인덱스에서 레인지 스캔을 하면 위에서 말한 것처럼 정렬되어 있어서 I/O 효율성이 좋습니다.
    • 레인지 스캔을 할 때 연속적인 데이터 페이지를 접근하는 원리라 그렇습니다.
  • 논-클러스터드 인덱스는 인덱스 페이지에서 검색 범위를 찾고 해당 데이터 페이지로 포인터를 따라가요.
    • 데이터도 물리적으로 분산되어 있을 수 있어서 클러스터드 인덱스에 비해 I/O 효율성은 낮습니다.
  • 하지만, 공통적으로 데이터를 스캔하고자 하는 범위가 넓어지면 성능이 저하될 수 있습니다
• Index Skip Scan
  • 복합 인덱스에서 첫 번째 열이 아닌 열을 기준으로 탐색합니다
  • 복합 인덱스의 효율성을 최대화하기 위해 사용합니다.
  • 첫 번째 열의 값들을 건너뛰고 탐색하므로 일반 인덱스 스캔보다 느릴 수 있습니다.

 

인덱스의 장점과 단점

장점

• 검색 속도 향상: 데이터를 빠르게 찾아야 하는 쿼리에 대해 효율적인 검색 제공.
• 정렬 및 필터링 지원: 데이터가 이미 정렬된 상태로 저장되므로 정렬 작업이 더 빠름.
• 범위 검색에 유용: 특히 B-트리 및 B+트리는 범위 검색을 최적화.

단점

• 쓰기 성능 저하: 삽입, 삭제, 업데이트 작업 시 인덱스를 유지하기 위한 오버헤드 발생.
• 추가적인 스토리지 필요: 인덱스를 저장하는 데 별도의 저장 공간이 필요.
• 복잡한 관리: 인덱스를 너무 많이 생성하면 쿼리 성능이 오히려 저하될 수 있음.

정리

• B-트리와 B+트리는 범위 검색과 정렬 작업에 적합하며, 관계형 데이터베이스에서 가장 널리 사용되는 구조입니다.
• 해시 인덱스는 동등 조건 검색에 특화되어 있지만 범위 검색에는 적합하지 않습니다.
• 비트맵 인덱스는 열 값의 범위가 작고 값이 제한적인 경우에 유리합니다.
• 클러스터드 및 넌클러스터드 인덱스는 데이터의 물리적 정렬 방식과 관련되어 있으며, 테이블 구조와 사용 패턴에 따라 선택합니다.