인덱스 (데이터베이스)

3. 종류

인덱스는 테이블 내 하나 이상의 열을 대상으로 생성되며, 무작위 참조 처리나 특정 순서로 레코드를 찾는 효율을 높일 수 있다. 데이터베이스에 따라 식 인덱스, 부분 인덱스 등 다양한 인덱스 생성 기능을 제공한다.

인덱스는 균형 이진 탐색 트리, B+ 트리, 해시 등 다양한 데이터 구조를 사용하여 구현된다. 검색 요구 사항에 따라 필요한 인덱스 구조가 다르므로, 여러 종류의 인덱스를 제공하는 데이터베이스 제품도 있다.

일반적인 인덱스는 한 행이 하나의 키만 갖는 것을 전제로 하지만, 배열 요소 검색이나 전체 텍스트 검색처럼 한 행에서 여러 키가 추출되는 경우도 있다. 이러한 경우에는 '''전치 인덱스'''(영: inverted index)가 사용된다.

B+트리는 인덱싱하는 값이 반복되지 않거나 적게 반복될 때 가장 효율적이다. 반면, '''비트맵 인덱스'''(영: bitmap index)는 기수가 낮아 값이 자주 반복되는 경우에 적합하다. 예를 들어, "성별" 열처럼 "남성", "여성" 값만 가지는 경우 B-트리보다 비트맵 인덱스가 효율적이며 성능 향상에 도움이 된다.

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

Microsoft SQL Server에서 클러스터형 인덱스의 트리 구조는 실제 데이터에 대응하며, 비 클러스터형 인덱스처럼 다른 위치에 있는 데이터에 대한 포인터가 아니다.^[12] 각 릴레이션은 클러스터형 인덱스를 1개, 비 클러스터형 인덱스를 여러 개 가질 수 있다.^[13]

여러 데이터베이스와 테이블이 결합될 때, 이를 '''클러스터'''라고 부르며, 이는 클러스터형 인덱스와는 다른 개념이다. 클러스터 키 값을 공유하는 테이블의 레코드는 동일하거나 인접한 데이터 블록에 함께 저장된다. 이는 클러스터 키를 사용한 테이블 결합 속도를 향상시키는데, 일치하는 레코드가 함께 저장되어 이를 찾는 데 필요한 I/O가 줄어들기 때문이다.^[14]

3. 2. 비클러스터형 인덱스 (Non-Clustered Index)

• 행의 물리적 순서는 인덱스 순서와 동일하지 않다.
• 인덱싱된 열은 일반적으로 JOIN, WHERE, ORDER BY 절에서 사용되는 비-기본 키 열이다.

• '''비트맵 인덱스'''(bitmap index)^[1]

• '''조밀 인덱스'''(dense index)^[1]

• '''희소 인덱스'''(sparse index)^[1]

• '''역방향 인덱스''' (reverse index)^[1]

3. 3. 기타 인덱스

• '''비트맵 인덱스'''(bitmap index): 데이터의 대부분을 비트 배열(비트맵)로 저장하고, 이러한 비트맵에 대한 비트 연산을 수행하여 대부분의 쿼리에 답하는 특수한 종류의 인덱싱이다. B+ 트리와 같이 가장 일반적으로 사용되는 인덱스는 인덱싱하는 값이 반복되지 않거나 소수의 횟수만 반복될 때 가장 효율적이다. 반면에 비트맵 인덱스는 변수 값이 매우 자주 반복되는 경우를 위해 설계되었다. 예를 들어, 고객 데이터베이스의 성별 필드는 일반적으로 최대 세 개의 고유한 값(남성, 여성 또는 알 수 없음)을 포함한다. 이러한 변수의 경우 비트맵 인덱스는 일반적으로 사용되는 트리보다 상당한 성능 이점을 가질 수 있다.^[3]
• '''조밀 인덱스'''(dense index): 데이터 파일의 모든 레코드에 대한 키와 포인터 쌍으로 구성된 파일이다. 이 파일의 각 키는 정렬된 데이터 파일의 특정 레코드에 대한 포인터와 연결된다. 키가 중복되는 클러스터형 인덱스에서 조밀 인덱스는 해당 키를 가진 첫 번째 레코드를 가리킨다.^[3]
• '''희소 인덱스'''(sparse index): 데이터 파일의 모든 블록에 대한 키와 포인터 쌍으로 구성된 파일이다. 이 파일의 모든 키는 정렬된 데이터 파일의 블록을 가리키는 특정 포인터와 연결된다. 키가 중복되는 클러스터형 인덱스에서 희소 인덱스는 각 블록의 가장 낮은 검색 키를 가리킨다.^[3]
• '''역 인덱스''' (reverse index): 인덱스에 입력하기 전에 키 값을 반전시킨다. 예를 들어, 값 24538은 인덱스에서 83542가 된다. 키 값을 반전시키는 것은 새로운 키 값이 단조 증가하는 시퀀스 번호와 같은 데이터를 인덱싱하는 데 특히 유용하다.
• '''식 인덱스''' (함수 인덱스, expression index): 함수나 식을 기반으로 한 인덱스이다. 예를 들어, `upper(last_name)` 함수를 기반으로 생성한 인덱스를 사용하여 last_name 열을 대소문자 구분 없이 데이터를 검색할 수 있다. (대문자로 변환된 값이 인덱스에 저장되어 있기 때문에, 검색 키는 대문자로 제공한다.)
• '''부분 인덱스''' (조건부 인덱스, partial index): 주어진 조건으로 행을 필터링하여 조건을 만족하는 행만 인덱스의 대상으로 한다.
• '''전치 인덱스'''(inverted index): 텍스트 데이터의 각 단어를 해당 단어가 포함된 문서나 레코드에 매핑하는 인덱스이다. 주로 전체 텍스트 검색에 사용된다.
• '''다차원 인덱스''' (Multidimensional Index): 여러 차원의 데이터를 효율적으로 검색하기 위한 인덱스이다. 주로 공간 데이터(GIS)에 사용된다.

4. 인덱스 구조

인덱스는 데이터 검색 속도를 높이기 위해 다양한 자료 구조를 사용한다. 대규모 데이터베이스에서는 선형 탐색이 비효율적이므로, 대부분의 데이터베이스 소프트웨어는 비선형 시간검색을 통해 성능을 향상시킨다.

데이터베이스에 N개의 데이터 항목이 있고, 특정 필드 값으로 데이터 항목 하나를 찾는 경우를 생각해 보자. 단순한 구현에서는 각 항목을 취득하여 조사해야 한다. 일치하는 항목이 하나뿐이면 처음 발견되었을 때 멈출 수 있지만, 여러 항목이 있을 가능성이 있으면 모든 항목을 검사해야 한다. 이는 평균적으로 O(N) 또는 선형 시간이 걸림을 의미한다. 데이터베이스에는 많은 객체가 포함되어 있고 검색은 일반적인 연산이므로, 검색 알고리즘의 효율을 높이는 것은 매우 중요하다.

인덱스는 이러한 검색 효율을 높이기 위한 데이터 구조이다. 이를 위해 사용되는 다양한 자료 구조가 존재한다. 각 자료 구조는 검색 효율, 인덱스 크기, 인덱스 갱신 효율 등 무엇을 우선시하는지에 따라 복잡한 설계상의 트레이드 오프가 있다. 많은 인덱스 디자인은 계산 시간이 로그 (O(log(N)))인 검색 효율을 보이며, 일부 애플리케이션에서는 계산 시간이 플랫 (O(1))인 검색 효율을 달성할 수 있다.

자주 사용되는 인덱스 구조로는 균형 이진 탐색 트리, B+ 트리, 해시 등이 있다. 검색 요구 사항에 따라 필요한 인덱스 구조가 다르므로, 서로 다른 구조를 가진 여러 개의 인덱스를 제공하는 데이터베이스 제품도 있다.

4. 1. B-트리 (B-Tree)

4. 2. 해시 인덱스 (Hash Index)

5. 인덱스 사용 (Usage)

인덱스는 데이터베이스 테이블에서 하나 이상의 열을 대상으로 생성되며, 무작위 참조 처리나 특정 순서로 레코드를 찾는 속도를 높여준다. 인덱스는 보통 원본 데이터의 행에 대한 "키"나 직접 링크를 포함하여 행 전체를 효율적으로 가져올 수 있게 한다.

데이터베이스에 따라서는 개발자가 함수나 식으로 계산된 열 값에 인덱스를 생성하는 식 인덱스를 사용하기도 한다. 예를 들어, `upper(last_name)`에 인덱스를 만들면 `last_name` 필드의 대문자 버전만 인덱스에 저장된다. 일부 시스템에서는 사용자 정의 함수나 내장 함수로 계산된 열 값에 인덱스를 생성할 수 있다. 또한, 특정 조건식을 만족하는 일부 레코드에 대해서만 인덱스를 생성하는 부분 인덱스도 있다.

인덱스는 테이블 내 키 열만 포함하지만, 테이블에는 키 열 이외의 데이터도 있으므로, 보통 인덱스가 차지하는 저장 용량은 대상 테이블보다 적다. 따라서 전체를 메모리에 보관하기 어려울 정도로 큰 테이블이라도, 해당 인덱스는 메모리에 보관할 수 있을 가능성이 있다.

5. 1. 빠른 조회를 위한 지원 (Support for fast lookup)

5. 2. 데이터베이스 제약 조건 관리 (Policing the database constraints)

6. 컬럼 순서 (Column order)

색인 정의가 열을 정의하는 순서는 중요하다. 색인된 첫 번째 열만 사용하여 일련의 행 식별자를 검색할 수 있다. 그러나 두 번째 이상의 색인 열만 사용하여 일련의 행 식별자를 검색하는 것은 불가능하거나 대부분의 데이터베이스에서 효율적이지 않다.^[1]

예를 들어, 도시, 성, 이름 순으로 구성된 전화번호부에서 특정 도시 내의 모든 전화번호 목록을 쉽게 추출할 수 있다. 그러나 특정 성을 가진 모든 전화번호를 찾는 것은 매우 번거로울 것이다. 각 도시 섹션 내에서 해당 성을 가진 항목을 찾아야 하기 때문이다. 일부 데이터베이스는 이를 수행할 수 있지만 다른 데이터베이스는 색인을 사용하지 않는다.^[1]

복합 색인이 (도시, 성, 이름) 열에 생성된 전화번호부 예에서, 세 필드 모두에 정확한 값을 제공하여 검색하면 검색 시간이 최소화된다. 하지만 도시와 이름 값만 제공하면 검색은 도시 필드만 사용하여 일치하는 모든 레코드를 검색한다. 그런 다음 순차 조회를 통해 이름과 일치하는지 확인한다. 따라서 성능을 향상시키려면 검색 열 순서대로 색인이 생성되었는지 확인해야 한다.^[3]

7. 응용 및 제한 사항 (Applications and limitations)

인덱스는 많은 응용 분야에 유용하지만 몇 가지 제한 사항이 있다. 예를 들어, 다음 SQL 문을 고려해 보자.

```sql

SELECT first_name FROM people WHERE last_name = 'Smith';

```

인덱스 없이 이 문을 처리하기 위해 데이터베이스 소프트웨어는 테이블의 모든 행에서 `last_name` 열을 확인해야 한다. (이것을 전체 테이블 스캔이라고 한다). 인덱스가 있으면 데이터베이스는 단순히 인덱스 데이터 구조(일반적으로 B-트리)를 따라 Smith 항목을 찾을 때까지 따라간다. 이는 전체 테이블 스캔보다 계산 비용이 훨씬 적게 든다.

다음 SQL 문을 고려해 보자.

```sql

SELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';

```

이 쿼리는 이메일 주소가 "@wikipedia.org"로 끝나는 모든 고객에 대한 이메일 주소를 생성하지만, `email_address` 열이 인덱싱되어 있더라도 데이터베이스는 전체 인덱스 스캔을 수행해야 한다. 이는 인덱스가 단어가 왼쪽에서 오른쪽으로 진행된다는 가정하에 구축되었기 때문이다. 검색어 시작 부분에 와일드카드가 있으면 데이터베이스 소프트웨어는 기본 인덱스 데이터 구조를 사용할 수 없다. (다시 말해, WHERE 절은 ''sargable하지 않다'') 이 문제는 `reverse(email_address)`에 생성된 다른 인덱스를 추가하고 다음과 같은 SQL 쿼리를 사용하여 해결할 수 있다.

```sql

SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');

```

이렇게 하면 와일드카드가 쿼리의 가장 오른쪽 부분(이제 `gro.aidepikiw@%`)에 배치되어 `reverse(email_address)`의 인덱스를 만족시킬 수 있다.

와일드카드 문자가 검색어의 양쪽에 "%wikipedia.org%"로 사용될 경우 이 필드에서 사용할 수 있는 인덱스가 사용되지 않는다. 대신 순차적 검색만 수행된다.^[1]

8. 인덱스 동시성 제어 (Index concurrency control)

인덱스는 일반적으로 여러 트랜잭션 및 프로세스에서 동시에 접근하므로, 동시성 제어가 필요하다. 원칙적으로 인덱스는 일반적인 데이터베이스 동시성 제어 방식을 활용할 수 있지만, 인덱스에 특화된 동시성 제어 방식이 존재하며, 이는 일반적인 방식과 함께 적용되어 상당한 성능 향상을 얻을 수 있다.^[1]

9. 커버링 인덱스 (Covering index)

커버링 인덱스는 쿼리에 필요한 모든 컬럼을 포함하는 특수한 인덱스이다. 일반적인 인덱스는 데이터 레코드를 빠르게 찾는 데 사용되지만, 데이터를 반환하려면 데이터 레코드를 읽어야 한다. 그러나 커버링 인덱스는 인덱스 자체에 필요한 모든 데이터 필드가 포함되어 있어, 데이터 레코드를 조회할 필요 없이 인덱스에서 바로 쿼리 결과를 얻을 수 있다.

예를 들어, 다음과 같은 테이블이 있다고 가정해 보자.

ID가 13인 이름을 찾기 위해 ID에 대한 인덱스를 사용할 수 있지만, 이름을 얻으려면 여전히 레코드를 읽어야 한다. 그러나 (ID, 이름)에 대한 커버링 인덱스를 사용하면 레코드를 조회할 필요 없이 인덱스에서 바로 이름을 얻을 수 있다.

커버링 인덱스는 데이터 검색 속도를 크게 높일 수 있지만, 추가 키로 인해 인덱스 자체가 커질 수 있으며, 이는 데이터 삽입 및 업데이트 속도를 늦출 수 있다. 이러한 인덱스 크기를 줄이기 위해 일부 시스템에서는 인덱스에 비키(non-key) 필드를 포함할 수 있다. 비키 필드는 인덱스 정렬의 일부가 아니지만, 리프 레벨(leaf level)에만 포함되어 전체 인덱스 크기가 더 작은 커버링 인덱스를 허용한다.^[7]

커버링 인덱스는 특정 테이블에 대해서만 적용된다. 여러 테이블에 걸쳐 조인(JOIN)하는 쿼리는 잠재적으로 이러한 테이블 중 하나 이상에 대한 커버링 인덱스를 고려할 수 있다.^[7]

참조

_[1] 문서 PostgreSQL 9.1.2 Documentation: CREATE TABLE http://www.postgresq[...]
_[2] 문서 Overview of Clusters http://download.orac[...] Oracle® Database Concepts 10g Release 1 (10.1)
_[3] 서적 Database Systems: The Complete Book
_[4] 서적 Chapter 8: Building Fast-Performing Database Models http://searchsecurit[...] Wrox Publishing
_[5] 웹사이트 Clustered Index Structures http://msdn2.microso[...] 2012-10-04
_[6] 웹사이트 Chapter 4: Creating Indices http://www.microsoft[...] Microsoft Press 2006-01
_[7] 문서 Covering Indexes for Query Optimization http://literatejava.[...]
_[8] 웹사이트 11.9. Index-Only Scans and Covering Indexes https://www.postgres[...] 2023-04-08
_[9] 웹사이트 Create indexes with included columns - SQL Server https://learn.micros[...] 2023-04-08
_[10] 문서 PostgreSQL 9.1.2 Documentation: CREATE TABLE http://www.postgresq[...]
_[11] 서적 Chapter 8: Building Fast-Performing Database Models http://searchsecurit[...] Wrox Publishing
_[12] 웹사이트 Clustered Index Structures https://docs.microso[...] マイクロソフト 2021-03-17
_[13] 웹사이트 Chapter 4: Creating Indices http://www.microsoft[...] Microsoft Press 2006-01
_[14] 문서 Overview of Clusters http://download.orac[...] Oracle® Database Concepts 10g Release 1 (10.1)
_[15] 서적 Database Systems: The Complete Book
_[16] 문서 Covering Indexes for Query Optimization http://literatejava.[...]
_[17] 간행물 1 VS COBOL II Application Programming Language Reference, Release 4, Eighth Edition (March 1993) IBM Corporation 1993-03
_[18] 서적 Enterprise PL/I for z/OS, Version 4.3, Language Reference http://www-01.ibm.co[...] 2015-11-25
_[19] 웹사이트 Informix C-ISAM http://www-03.ibm.co[...] 2015-11-25