인덱스 (데이터베이스)

데이터베이스 인덱스(database index)는 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 데이터 검색 작업 속도를 향상시키는 자료 구조이다. 인덱스는 데이터베이스 테이블에 액세스할 때마다 모든 행을 검색할 필요 없이 데이터를 빠르게 찾기 위해 사용된다. 인덱스는 하나 이상의 데이터베이스 테이블 열을 사용하여 생성할 수 있으며, 빠른 무작위 조회와 정렬된 레코드의 효율적인 액세스를 위한 기초를 제공한다.

인덱스는 매우 효율적인 검색이 가능하도록 설계된, 테이블에서 선택된 데이터 열의 복사본이다. 인덱스에는 일반적으로 완전한 행을 효율적으로 가져올 수 있도록 복사된 원래 데이터 행에 대한 "키" 또는 직접적인 링크가 포함된다. 일부 데이터베이스는 개발자가 함수나 식에 의해 변환된 열 값에 인덱스를 생성할 수 있도록 하여 인덱싱 기능을 확장한다. 예를 들어, upper(last_name)에 인덱스를 생성하면 인덱스에는 last_name 필드의 대문자 버전만 저장된다. 때때로 지원되는 또 다른 옵션은 특정 조건식을 만족하는 레코드에 대해서만 인덱스 항목을 생성하는 부분 인덱스이다. 유연성의 또 다른 측면은 다양한 기본 제공 함수로 구성된 식뿐만 아니라 사용자 정의 함수에 대한 인덱싱을 허용하는 것이다.

용도

빠른 조회 지원

대부분의 데이터베이스 소프트웨어는 대규모 데이터베이스에서 순차 검색이 비효율적이기 때문에, 성능 향상을 위해 아표준 시간(sub-linear time) 조회를 가능하게 하는 인덱싱 기술을 포함한다.

데이터베이스에 N개의 데이터 항목이 있고 그 중 하나를 필드 값 중 하나를 기반으로 검색해야 한다고 가정해 보자. 단순한 구현은 테스트에 따라 각 항목을 가져와서 검사한다. 일치하는 항목이 하나만 있는 경우 해당 항목을 찾으면 중단할 수 있지만, 일치하는 항목이 여러 개 있는 경우 모든 항목을 테스트해야 한다. 이는 평균적인 경우 작업 수가 O(N) 또는 선형 시간임을 의미한다. 데이터베이스에는 많은 객체가 포함될 수 있고 조회가 일반적인 작업이므로 성능을 개선하는 것이 바람직한 경우가 많다.

인덱스는 조회의 성능을 향상시키는 모든 자료 구조를 말한다. 이를 위해 다양한 자료 구조가 사용된다. 조회 성능, 인덱스 크기, 인덱스 업데이트 성능 사이에는 복잡한 설계상의 절충점이 존재한다. 많은 인덱스 설계는 로그 시간(O(log(N))) 조회 성능을 보이며, 일부 응용 프로그램에서는 상수 시간(O(1)) 성능을 달성할 수도 있다.

데이터베이스 제약 조건 관리

인덱스는 UNIQUE, EXCLUSION, 기본 키(PRIMARY KEY) 및 외래 키와 같은 데이터베이스 제약 조건을 관리하는 데 사용된다. 인덱스를 UNIQUE로 선언하면 기본 테이블에 암시적 제약 조건이 생성된다. 데이터베이스 시스템은 일반적으로 PRIMARY KEY로 선언된 열 세트에 대해 암시적으로 인덱스를 생성하며, 일부 시스템은 이 제약 조건을 관리하기 위해 이미 존재하는 인덱스를 사용할 수도 있다. 많은 데이터베이스 시스템은 외래 키 제약 조건의 참조하는 열 세트와 참조되는 열 세트 모두에 인덱스가 있어야 하므로, 제약 조건에 참여하는 테이블에 대한 삽입, 업데이트 및 삭제 성능이 향상된다.

일부 데이터베이스 시스템은 새로 삽입되거나 업데이트된 레코드에 대해 특정 서술어(predicate)가 다른 레코드에 대해 유지되지 않도록 보장하는 EXCLUSION 제약 조건을 지원한다. 이는 UNIQUE 제약 조건(동등 서술어 포함)이나 겹치는 시간 범위 또는 교차하는 기하 객체가 테이블에 저장되지 않도록 보장하는 것과 같은 더 복잡한 제약 조건을 구현하는 데 사용될 수 있다. 이러한 제약 조건을 관리하려면 서술어를 만족하는 레코드를 빠르게 검색할 수 있는 인덱스가 필요하다.

인덱스 아키텍처 및 인덱싱 방법

비클러스터형 (Non-clustered)

데이터는 임의의 순서로 존재하지만, 논리적 순서는 인덱스에 의해 지정된다. 데이터 행은 인덱싱된 열 또는 식의 값과 관계없이 테이블 전체에 분산될 수 있다. 비클러스터형 인덱스 트리는 정렬된 순서로 인덱스 키를 포함하며, 인덱스의 리프 레벨에는 레코드에 대한 포인터가 포함된다(페이지 기반 엔진의 경우 페이지 및 데이터 페이지 내의 행 번호, 파일 기반 엔진의 경우 파일 내의 행 오프셋).

비클러스터형 인덱스에서:

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

하나의 데이터베이스 테이블에 두 개 이상의 비클러스터형 인덱스가 존재할 수 있다.

클러스터형 (Clustered)

클러스터링은 데이터 블록을 인덱스와 일치하는 특정 순서로 변경하여 행 데이터가 정렬된 상태로 저장되게 한다. 따라서 지정된 데이터베이스 테이블에는 하나의 클러스터형 인덱스만 생성할 수 있다. 클러스터형 인덱스는 전반적인 검색 속도를 크게 높일 수 있지만, 대개 데이터가 클러스터형 인덱스와 동일하거나 반대 순서로 순차적으로 액세스되거나 항목 범위가 선택되는 경우에만 해당된다.

물리적 레코드가 디스크 상에 이 정렬 순서로 존재하므로, 시퀀스의 다음 행 항목은 마지막 항목 바로 앞이나 뒤에 있게 되어 데이터 블록 읽기가 덜 필요하다. 따라서 클러스터형 인덱스의 주요 특징은 물리적 데이터 행이 자신을 가리키는 인덱스 블록에 따라 정렬된다는 것이다. 일부 데이터베이스는 데이터와 인덱스 블록을 별도의 파일로 분리하고, 다른 데이터베이스는 동일한 물리적 파일 내에 두 개의 완전히 다른 데이터 블록을 배치한다.

클러스터 (Cluster)

여러 데이터베이스와 여러 테이블이 조인될 때 이를 클러스터라고 한다(앞서 설명한 클러스터형 인덱스와 혼동해서는 안 된다). 클러스터 키 값을 공유하는 테이블의 레코드는 동일하거나 인접한 데이터 블록에 함께 저장된다. 일치하는 레코드가 함께 저장되고 이를 찾는 데 필요한 I/O가 적기 때문에 클러스터 키에 대한 이러한 테이블의 조인 성능이 향상될 수 있다. 클러스터 구성은 클러스터의 일부인 테이블의 데이터 레이아웃을 정의한다. 클러스터는 B 트리 인덱스 또는 해시 테이블을 키로 사용할 수 있다. 테이블 레코드가 저장되는 데이터 블록은 클러스터 키 값에 의해 정의된다.

열 순서

인덱스 정의에서 열을 정의하는 순서는 중요하다. 첫 번째 인덱싱된 열만 사용하여 행 식별자 집합을 검색하는 것은 가능하다. 그러나 (대부분의 데이터베이스에서) 두 번째 이상의 인덱싱된 열만 사용하여 행 식별자 집합을 검색하는 것은 불가능하거나 효율적이지 않다.

예를 들어, 도시별로 먼저 정리되고 그 다음 성(last name), 이름(first name) 순으로 정리된 전화번호부에서 특정 도시의 모든 전화번호 목록은 쉽게 추출할 수 있다. 그러나 특정 성을 가진 모든 전화번호를 찾는 것은 매우 지루할 것이다. 각 도시 섹션 내에서 해당 성을 가진 항목을 찾아야 하기 때문이다. 일부 데이터베이스는 이를 수행할 수 있지만, 다른 데이터베이스는 인덱스를 사용하지 않는다.

열(city, last_name, first_name)에 생성된 복합 인덱스가 있는 전화번호부 예시에서, 세 필드 모두에 대해 정확한 값을 제공하여 검색하면 검색 시간이 최소화된다. 하지만 city와 first_name에 대한 값만 제공하면 검색 시 city 필드만 사용하여 일치하는 모든 레코드를 가져온다. 그런 다음 순차 조회를 통해 first_name과의 일치를 확인한다. 따라서 성능을 개선하려면 검색 열의 순서대로 인덱스가 생성되도록 해야 한다.

응용 및 제한 사항

인덱스는 많은 응용 분야에서 유용하지만 몇 가지 제한 사항이 있다. 다음 SQL 문을 고려해 보자: SELECT first_name FROM people WHERE last_name = 'Smith';. 인덱스 없이 이 문을 처리하려면 데이터베이스 소프트웨어는 테이블의 모든 행에서 last_name 열을 확인해야 한다(이를 전체 테이블 스캔이라고 한다). 인덱스가 있으면 데이터베이스는 Smith 항목을 찾을 때까지 인덱스 자료 구조(일반적으로 B 트리)를 따라가기만 하면 된다. 이는 전체 테이블 스캔보다 계산 비용이 훨씬 적다.

다음 SQL 문을 고려해 보자: SELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';. 이 쿼리는 이메일 주소가 "@wikipedia.org"로 끝나는 모든 고객의 이메일 주소를 산출하지만, email_address 열에 인덱스가 있더라도 데이터베이스는 전체 인덱스 스캔을 수행해야 한다. 이는 인덱스가 단어가 왼쪽에서 오른쪽으로 진행된다는 가정하에 구축되기 때문이다. 검색어 시작 부분에 와일드카드 문자가 있으면 데이터베이스 소프트웨어는 기본 인덱스 자료 구조를 사용할 수 없다(즉, WHERE 절이 sargable하지 않음). 이 문제는 reverse(email_address)에 생성된 또 다른 인덱스와 SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');와 같은 SQL 쿼리를 추가하여 해결할 수 있다. 이렇게 하면 와일드카드가 쿼리의 맨 오른쪽(gro.aidepikiw@%)에 오게 되어 reverse(email_address)에 대한 인덱스가 이를 충족할 수 있다.

와일드카드 문자가 %wikipedia.org%와 같이 검색어의 양쪽에서 모두 사용되는 경우, 해당 필드에 사용 가능한 인덱스는 사용되지 않는다. 대신 순차 검색만 수행되며, 이 경우 $O(N)$ 시간이 소요된다.

인덱스 유형

비트맵 인덱스

 이 부분의 본문은 비트맵 인덱스입니다.

비트맵 인덱스는 데이터의 대부분을 비트 배열(비트맵)로 저장하고 이러한 비트맵에 대해 비트 논리 연산을 수행하여 대부분의 쿼리에 응답하는 특수한 종류의 인덱싱이다. B+ 트리와 같이 가장 일반적으로 사용되는 인덱스는 인덱싱하는 값이 반복되지 않거나 적은 횟수로 반복되는 경우 가장 효율적이다. 반면, 비트맵 인덱스는 변수의 값이 매우 빈번하게 반복되는 경우를 위해 설계되었다. 예를 들어, 고객 데이터베이스의 성별 필드는 보통 남성, 여성 또는 알 수 없음(기록되지 않음)의 최대 세 가지 고유 값을 포함한다. 이러한 변수의 경우 비트맵 인덱스는 일반적으로 사용되는 트리에 비해 상당한 성능 이점을 가질 수 있다.

밀집 인덱스 (Dense index)

데이터베이스에서 밀집 인덱스는 데이터 파일의 모든 레코드에 대한 키와 포인터 쌍이 있는 파일이다. 이 파일의 모든 키는 정렬된 데이터 파일의 특정 레코드 포인터와 연결된다. 중복 키가 있는 클러스터형 인덱스에서 밀집 인덱스는 해당 키를 가진 첫 번째 레코드를 가리킨다.

희소 인덱스 (Sparse index)

데이터베이스에서 희소 인덱스는 데이터 파일의 모든 블록에 대한 키와 포인터 쌍이 있는 파일이다. 이 파일의 모든 키는 정렬된 데이터 파일의 블록에 대한 특정 포인터와 연결된다. 중복 키가 있는 클러스터형 인덱스에서 희소 인덱스는 각 블록의 가장 낮은 검색 키를 가리킨다.

역키 인덱스 (Reverse index)

 이 부분의 본문은 역색인입니다.

역키 인덱스(reverse-key index)는 키 값을 인덱스에 입력하기 전에 반전시킨다. 예를 들어, 값 24538은 인덱스에서 83542가 된다. 키 값을 반전시키는 것은 새로운 키 값이 단조롭게 증가하는 시퀀스 번호와 같은 데이터를 인덱싱할 때 특히 유용하다.

역색인 (Inverted index)

 이 부분의 본문은 역색인입니다.

역색인은 콘텐츠 단어를 해당 단어가 포함된 문서에 매핑하여 전체 텍스트 검색을 가능하게 한다.

기본 인덱스 (Primary index)

기본 인덱스는 테이블의 키 필드와 테이블의 키가 아닌 필드에 대한 포인터를 포함한다. 기본 인덱스는 데이터베이스에 테이블이 생성될 때 자동으로 생성된다.

보조 인덱스 (Secondary index)

정렬 필드도 키 필드도 아닌 필드를 인덱싱하는 데 사용된다(파일이 키 필드나 기본 키 필드로 구성되어 있다는 보장이 없음). 데이터 파일의 모든 튜플에 대한 하나의 인덱스 항목(밀집 인덱스)은 인덱싱된 속성의 값과 블록 또는 레코드에 대한 포인터를 포함한다.

선형 해싱 (Linear hashing)

데이터베이스 시스템에서 사용되는 또 다른 유형의 인덱스는 선형 해싱이다.

인덱스 구현

인덱스는 다양한 자료 구조를 사용하여 구현될 수 있다. 인기 있는 인덱스로는 균형 트리, B+ 트리 및 해시가 있다.

마이크로소프트 SQL 서버에서 클러스터형 인덱스의 리프 노드는 비클러스터형 인덱스의 경우처럼 다른 곳에 있는 데이터에 대한 포인터가 아니라 실제 데이터에 해당한다. 각 관계는 단일 클러스터형 인덱스와 여러 비클러스터형 인덱스를 가질 수 있다.

인덱스 동시성 제어

 이 부분의 본문은 인덱스 잠금입니다.

인덱스는 일반적으로 여러 트랜잭션과 프로세스에 의해 동시에 액세스되므로 동시성 제어가 필요하다. 원칙적으로 인덱스는 일반적인 데이터베이스 동시성 제어 방법을 활용할 수 있지만, 상당한 성능 향상을 위해 일반적인 방법과 병행하여 적용되는 특수 인덱스 동시성 제어 방법이 존재한다.

커버링 인덱스 (Covering index)

대부분의 경우 인덱스는 필요한 데이터를 읽을 데이터 레코드를 빠르게 찾는 데 사용된다. 즉, 인덱스는 테이블의 데이터 레코드를 찾는 데만 사용되고 데이터를 반환하는 데는 사용되지 않는다.

커버링 인덱스는 인덱스 자체에 필요한 데이터 필드가 포함되어 있어 필요한 데이터에 직접 응답할 수 있는 특별한 경우이다.

다음 테이블을 고려해 보자(다른 필드는 생략):

ID	이름	기타 필드
12	플러그	...
13	램프	...
14	퓨즈	...

ID 13의 이름을 찾으려면 (ID)에 대한 인덱스가 유용하지만, 이름을 얻으려면 여전히 레코드를 읽어야 한다. 그러나 (ID, 이름)에 대한 인덱스에는 필요한 데이터 필드가 포함되어 있으므로 레코드를 조회할 필요가 없다.

커버링 인덱스는 각각 특정 테이블을 위한 것이다. 여러 테이블을 JOIN하거나 가로질러 액세스하는 쿼리는 잠재적으로 이러한 테이블 중 둘 이상의 커버링 인덱스를 고려할 수 있다.

커버링 인덱스는 데이터 검색 속도를 크게 높일 수 있지만, 추가 키로 인해 인덱스 자체가 커져 데이터 삽입 및 업데이트 속도가 느려질 수 있다. 이러한 인덱스 크기를 줄이기 위해 일부 시스템에서는 인덱스에 키가 아닌 필드를 포함할 수 있도록 허용한다. 키가 아닌 필드는 인덱스 순서의 일부는 아니지만 리프 레벨에만 포함되므로 전체 인덱스 크기를 줄이면서 커버링 인덱스를 구성할 수 있다.

이는 SQL에서 CREATE INDEX my_index ON my_table (id) INCLUDE (name);로 수행할 수 있다.

표준화

ISO SQL 표준은 물리적 측면을 다루지 않기 때문에 인덱스를 생성하는 방법을 정의하는 표준은 없다. RDBMS 벤더는 모두 자사 소프트웨어의 기능에 따른 몇 가지 특정 옵션이 포함된 CREATE INDEX 구문을 제공한다.

같이 보기

• 인덱스 잠그기
• 검색엔진 인덱스