database index

공부자료: https://en.wikipedia.org/wiki/Database_index

Database index - Wikipedia

database index?

추가적인 쓰기 및 인덱스 데이터 구조를 저장하기 위한 공간에 있어서

테이블의 데이터 획득 연산 속도를 개선하는 기법.

 

인덱스는 데이터베이스 테이블 내의 데이터를 불러올 때 매번 모든 행을 가져오지 않고서 빠르게 데이터를 가져올 수 있다.

 

인덱스는  매우 빠르고 랜덤 확률적인 lookup연산을 하는 것과 정렬된 데이터의 효율적인 접근 모두를 제공하므로써, 테이블내에서 하나 혹은 이상의 열을 사용해서 생성할 수 있다.

 

인덱스는 매우 효율적으로 검색될 수 있는 테이블로부터 선택된 데이터 열들의 복사본이며, 낮은 수준의 디스크 블록 주소 혹은 완전히 row data 참조로부터 복사된 것이다.

 

몇몇 DBMS는 개발자가 함수 혹은 표현식을 이용해서 인덱싱의 권한을 확장한다. 예를 들면 'last name'이라는 필드를 인덱스로 저장할 수 있다.

 

또 다른 옵션은 partial indices(부분 인덱스들)이라는 기법이다. 이 기법의 인덱스 개체들은 몇가지 조건 표현식을 만족하는 데이터들에 한정되어 생성된다.

 

더불어 이러한 유연적인 측면은 정의된 함수의 집합을 사용해 정의된 표현식 뿐만 아니라 사용자 정의된 함수에 기반해 인덱싱을 승인하는 것이다.(정의된 표현식.. C++에서 사용하는 오퍼레이터 재정의 개념과 유사해보인다.)

 

lookup table

공부자료: https://en.wikipedia.org/wiki/Lookup_table

Lookup table - Wikipedia

lookup table은 배열 인덱싱 연산을 이용한 런타임 계산을 대체하는 한 배열이다.

 

수행시간을 아끼는 것은 중요하고, 메모리에서 value를 획득하는게 다른 "확장적인" 연산 혹은 I/O연산을 하는 것보다 빠르기 때문이다.

 

테이블들은 미리 연산될 것이고, 정해놓은 프로그램 저장소에 저장된다. 이 저장소는 프로그램 초기화 단계의 부분으로서(memoization) 혹은 하드웨어의 응용 프로그램-명시 플랫폼에 저장된 부분으로서 미리계산된다.(pre-fetch)

 

lookup 테이블들은 배열혹은 프로그래밍 언어 상에서 상응하는 값들의 리스트를 매칭함으로써 유효 값을 광범위하게 입증하는데 사용된다. 포인터 함수(혹은 offset 라벨) 또한 입력값 매칭 연산을 하기위해 포함 될 수 있다.

 

FPGA는 이것을 하드웨어적으로 구현하는데 사용할 수 있다.

 

예시

 

연관된 배열 혹은 연결리스트 상에서의 간단한 lookup(정렬되지 않은 리스트)

 

이것은 선형 탐색 혹은 brute-force 탐색으로 알려져있다. 각각의 원소들은 한번의 탐색에서 맞는지 체크 되고, 만약 찾고자 하는 값과 연관된 값이 있다면, 이 값은 탐색의 결과로서 사용된다. 찾고자 하는 값이 일찍 나오는 경우를 제외하고, 이 방법은 조금 느리다. 1차원 배열 혹은 연결 리스트에 대해서 lookup은 보통 input data와 일치하는 value가 존재하는지를 결정한다.

 

-> 사견: lookup은 단순하게 생각하면 탐색 연산의 일종이다.

 

인덱싱의 사용

 

1) 빠른 look up을 위한 지원

 

대다수의 데이터베이스는 선형 탐색이 많은 데이터에 비효율적이기 때문에 sub-linear time인 lookup을 성능 개선을 위해 사용한다.

 

최악의 경우 O(n)의 시간이 걸린다.

 

인덱스는 lookup 연산을 개선하는 자료구조이다. 많은 종류의 자료구조가 빠른 lookup을 지원하기 위해 사용된다.

 

lookup의 성능과 상충되는 복잡한 구조도 있는데, index-size와 index-update 연산이다. 많은 인덱스 디자인들은

O(log(n))의 lookup 성능을 갖고, O(1) 성능을 이루는데 가능하도록 한 몇가지 응용도 있다.

 

2) 데이터베이스 제약 정책 수립.

 

UNIQUE, EXCLUSION, PRIMARY KEY, FOREIGN KEY와 같은 데이터베이스 제약조건 정책을 수립하는데 사용된다. 인덱스는 원본 테이블(underlying table)에 암시적 제한을 거는 UNIQUE로서 선언된다. 데이터베이스 시스템은 보통 PRIMARY KEY로 선언된 열들의 집합(테이블)에 대해 인덱스를 암시적으로 생성한다. 

 

그리고 몇가지는 이 제약을 세우기 위해 이미 존재하는 인덱스를 사용할 수 있다.

 

많은 데이터 베이스 시스템들은 인덱스된 FOREIGN KEY 제약에 참조된 열 집합과 참조 모두를 요구한다. 더불어서 제약에 참여하는 테이블의 삽입, 갱신, 삭제 성능을 개선한다.

 

인덱스 종류

dense index

이 인덱스는 데이터 파일상의 모든 레코드에 대해 키와 포인터의 쌍으로 이뤄진 파일이다. 이 파일의 모든 키는 데이터 파일에 있는 레코드로 이어지는 특정한 포인터와 연관되어 있다. 복사된 키를 갖는 군집된 인덱스들에서, dense 인덱스는 키를 사용해서 첫번째 레코드를 가리킨다.

 

reverse index

reverse-key 인덱스는 인덱스로 값을 넣기 전에 키값을 뒤집는다. 쉽게, 24538이라는 값은 83542가 되어 인덱스에 들어간다. 키값을 뒤집는 것은 증가하는 순서로 된 새 키값이 있는 순서번호 처럼 색인이 붙는 데이터에 특히 유용하다.

 

spare index

이 인덱스는 데이터 파일상의 모든 블록에 대해 키와 포인터의 쌍으로 이뤄진 파일이다. 이 파일의 모든 키는 데이터 파일에 있는 블록으로 이어지는 특정한 포인터와 연관이 있다. 복사된 키들을 갖는 군집된 인덱스들에서, sparse 인덱스는 각각의 블록에 가장 낮은 탐색 키를 가리킨다.

 

primary index

이 인덱스는 테이블의 key 필드와 key 필드가 아닌것을 가리키는 포인터들을 포함한다. primary index는 테이블이 데이터베이스 상에서 만들어질때 자동적으로 생성된다. 파일을 만들때, primary index에 대해 반드시 아래의 2가지를 명시해야한다.

1. primary index의 이름.

2. primary index 명세서.

 

secondary index

정렬된 필드와 키 필드가 아닌 필드를 인덱스할때 사용된다. 데이터 파일(dense index)의 모든 튜플에 대해서 하나의 인덱스 엔트리는 인덱스된 속성값과 block/record를 가리키는 포인터를 포함한다.

 

인덱스 아키텍처

non-clustered(비군집화 인덱스 구조)

데이터는 임의의 순서대로 표현되지만, 논리적인 순서는 인덱스에 의해 명시화된다. 데이터 행들은 테이블 전반에 거쳐 색인이 달린 컬럼 혹은 표현에 상관없이 퍼지게 된다. non-clustered 인덱스 트리는 정렬된 순서로 인덱스 키들을 포함하고, 레코드를 가리키는 포인터를 포함하는 인덱스가 말단 노드에 위치한다.

 

non-clustered 인덱스상에서 

 

1. 행의 물리적 순서는 인덱스 순서와 같지 않다.

2. 색인이 붙은 열들은 보통 JOIN, WHERE , ORDER BY 문장에 수행되는 primary key가 아닌 열들이다.

 

데이터베이스 상에서 여러개의 non-clustered index가 존재할 수 있다.

 

Clustered(군집화된 인덱스 구조)

군집화는 데이터 블록을 특정하고 별개의 순서로 색인을 달아놓는다.(match the index) 이때 순서대로 저장되는 행 데이터는 순서대로 저장되도록 한다. 따라서 오직 한개의 군집화된 인덱스들만이 주어진 데이터베이스 테이블에 생성 될 수 있다.  군집화된 인덱스들은 데이터를 획득하는 전체 속도를 크게 증가시킬 수 있다. 하지만 보통 군집화된 인덱스의 순서를 역으로 하거나 같은 것 상에서 순서대로 접근된다.(or when a range of items is selected)

 

물리적 레코드들이 디스크상에 정렬된 순서로 존재하기 때문에, 순서의 다음행 데이터는 즉시 마지막 것의 그 다음을 가리키고, 몇 안되는 데이터를 읽어오는 것만 요구된다. 군집화된 인덱스의 주된 특징은 물리적 데이터가 ㄱ드ㅡㄹ을 가리키는 인덱스 블록들에 부합한다는 것이다. 몇가지 데이터베이스는 데이터와 인덱스 블록을 구분된 파일로 나누는데, 다른것들은 완벽하게 다른 두개의 데이터 블록들을 같은 물리적 파일에 보관한다.

 

 Cluster(군집화 인덱스 구조)