레이블이 PostgreSql인 게시물을 표시합니다. 모든 게시물 표시
레이블이 PostgreSql인 게시물을 표시합니다. 모든 게시물 표시

2020년 7월 1일 수요일

SQL 빠르게 하기 - 인덱스

1. 사전지식

인덱스는 어떠한 Key 를 가지고 원하는 위치를 찾는 방법임.

그러므로 (Search Key, Address) 로 인덱스들이 구성될 것임.

이러한 인덱스들의 모음이 Index Entry 라고 함.

Search Key

=> Sequencial File Organization 에서 정렬 기준이 되는 Attribute

=> 그냥 인덱스 만들 때 쓰는 기준 Attribute

평가 기준

Access Types : 어떤 명령을 효율적으로 해줄 수 있는가.

Access Time : 데이터 접근 시간

Update Time : (Insertion Time, Deletion Time) 데이터 수정 시 인덱스도 수정되어야 하기 때문

Space Overhead.: 인덱스 저장할 공간은 적은게 좋음

2. Ordered Indices ( Indexing)

데이터가 search key 에 따라서 정렬되어 있음.

Primary Indices (clustering Indices)

데이터의 정렬된 순서와 인덱스가 사용하는 search key 가 일치하는 경우.

ID 같은 Primary Key 를 이용해 만드는 하는 경우가 많음.

densed index

=> 모든 search key 가 다 들어가 있음.

=> 같은 search key 를 공유하는 경우도 정렬되어 있으므로 순차검색 하면 됨.

=> Access Types 은 다 가능하고, Access Time 은 케바케, Update Time 이 크고, Space Overhead 가 큼.

sparsed index

=> 일부의 search key 가 다 들어가 있음.

=> index 에 없는 record 를 찾기 위해선, 정렬되어 있으므로 가장 가까운 index 를 이용해 순차검색을 하면 됨.

=> 검색하는데 시간이 더 걸림

=> Access Types 은 다 가능하고, Access Time 은 케바케, Update Time 이 작고, Space Overhead 가 작음.

Multilevel Index

=> 데이터가 너무 크면 인덱스도 메모리아 한번에 다 안들어감.

=> 그래서 인덱스의 인덱스도 사용함.

=> B+Tree 가 되어서 Ordered Index 의 이데아가 되어버림.

Secondary Indices (Non Clustering Indices)

데이터 순서와 index entry 의 순서가 다름.

순서가 보장되지 않으므로 densed index 밖에 안됨.

같은 search key 로 여러개의 record 가 있는 경우도 검색할 수 있게 하기 위해, Bucket 을 만들어 해당되는 주소들을 모아둠.

=> Access Time, Update Time, Space Overhead 는 Primary 의 경우와 비슷함.

=> Access Type 에서 범위기반 탐색은 쓰면 안됨. 딱 하나 찾는 경우만 좋음.

=> 인덱스 디스크 접근 -> 데이터 디스크 접근 -> 인덱스 디스크 접근... 의 반복이 되기 때문.

B+Tree

1단계 => Indexed Sequential File : search key 로 정렬된 파일 + Clustering index

2단계=> B+Tree

insert, delete 할 때 오버헤드 조금 주고, index re-organazation 을 update 마다 조금씩 해서 전체 재정렬해서 시스템이 멈추는 일을 막아줌.

node 당 포인터(value) 갯수를 n 개 담을 수 있다고 하자. (이때 블럭 크기에 맞도록 n의 크기를 조정한다.)

RULE

1. root node 는 자식이 없는 경우 0 ~ 0-n 개의 value 를 가짐. 있으면 최소 2개 이상.

2. root node 부터 leaf node 까지 길이는 모두 같음

3. internal node 는 n/2 ~ n 개 까지다.

4. leaf node 는 (n-1)/2 ~ n-1 개 까지의 노드를 갖는다. (맨 끝 노드는 sibiling node 를 가르키므로)

특징

최대로 널널하게 tree 를 만든다고 하면

Height 가 1 인 경우 2 * n/2 ( root 는 최소 자식이 2개, leaf node 는 (n-1)/2 이긴한데 대충 n/2 개 이상)

Height 가 2 인 경우 2 * n/2 * n/2 ....

$LeafLevel\ Node\ =\ 2\ \cdot \ \left\lceil \combi{n/}2\right\rceil ^{Height}$LeafLevel Node = 2 · n/2Height
$Height\ =\ \log _{\left\lceil \combi{n/}2\right\rceil }\combi{K}\ \ \ \ \ \ \left(K\ is\ Leaf\ Level\ Node\right)$Height = logn/2K      (K is Leaf Level Node)

B+Tree 의 Layer 마다 각각 메모리에 따로 저장되어 있기 때문에,

데이터에 접근하기 위한 디스크 탐색 횟수는 총 Height + 1 번이 된다.

(layer 을 binary search 하면 binary 로 나눈 횟수만큼 디스크 탐색이므로, 메모리에 인덱스가 다 안담기는 경우 B+Tree 가 이득이 된다.)

3. Hash ( Unordered Indices)

Search Key 로부터 해쉬함수 적용해서 같은 값끼리 Bucket 에 주소를 넣음.

순서가 없기 때문에 Secondary Indices 일 수 밖에 없음.

( Secondary 는 데이터와의 관계이고 Unordered 는 Indices 자체가 순서가 있냐 이야기임)

Uniform : Hash Function 은 search-key 값들의 개수가 Uniform 하게 Bucket 에 들어가야 함

Random : 이를 위해 key 의 domain 에 의한 영향을 줄이기 위해 그것들에 대해서 Random 해야한다.

Bucket Overflow

균등하게 Bucket 에 담는건 힘들고, Bucket 크기도 무한정 할 수 없기 때문에 넘치는 일이 생김

1. Overflow Chaining

=> Linked List 로 구현

=> Closed Hashing

2. Open Hashing

=> 다른 bucket 에 임시로 두는 방법

=> Insert, Delete 가 빈번히 일어나기 때문에, 빈 공간이 있는데도 다른 버킷에 값이 있는 등 적절하지 않음

Dynamic Hashing

bucket 크기를 유동적으로 하는 방법.

구현방법은 여러가지가 있음.

4. 인덱스 사용

Hash 는 값을 몇개 안찾는 경우에만 사용할 수 있음

B+Tree Primary Key의 경우만 범위 탐색도 쉽게 할 수 있음.

5. PostgresSql 적용

생성

create index [index name] on [table name] using [index sort]([attribute name]);

index sort 에는 btree, hash 등이 쓰인다.

삭제

drop index [index name];


List