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 ....
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];
댓글 없음:
댓글 쓰기