[DB] indexing part-1 (index의 구조)

https://codenme.tistory.com/22d

데이터베이스 참고자료

위의 자료를 기반으로 작성한 내용입니다.

 

(update at 23-08-08)

 

Dbms가 레코드 들을  잘 찾기 위한 구조로써 heap은 별로다. (전체를 다 뒤져야할 수 도 있다)

데이터를 미리 정돈하면 bin search 등으로 linear search보다 빨리 search 가능.

Search key: file 안의 record 찾는데 사용.

index file

Index file: index entry라는 record 들을 포함

Index entry: (search key,pointer) 구조. ( 원본 파일보다 적은 용량을 통해 해당 파일의 실제 위치 가르킨다)

 

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조

 

Query -> index(key, pointer or value) -> DB (실제 record) 의 과정으로 DB에 접근하게 된다.

 

Ordered indice : search key 가 정렬되어있다.

Hash indices: search key가 hash function 을 통한 buckets 에 골고루 분배되어있다. ( 정렬 x)

 

Point query: 정확하게 쿼리에 해당하는 데이터 1개만 찾는 것

Range query: 주어진 범위 내 모든 데이터를 가져온다. 

 

 

인덱스를 사용한다면, 새로운 데이터가 추가될 때마다 해당 데이터를 인덱스가 가리키게 해야 한다.

Space overhead: 원래공간에서 추가적으로 저장되는 것 .

 

ordered index

2가지 형태를 가진다. 

- Clustering index(primary index): 정렬 되어있는 file에서, search key와 찾고자 하는 데이터가 한 덩어리가 되어있는 상태 ( search key가 실제 file 안의 순서를 보여준다.)

각 value와 record들이 search key에 따라 쭉 order되어 저장된다. (이런 구조상 relation 당 1번밖에 사용할 수 없음)

 

- Secondary index: (non clustering): search key 에 포인터가 붙어있는 것.

• Search key의 order와 실제 file의 순서 다르다.
• 내가 찾고자 하는 secondary index( 한다리 걸쳐 가는)로 찾고자하는 걸 표현

 

dense Index

dense index

• 파일 안의 모든 search key값(서로다른 값) 에 대한 index 레코드가 존재한다..
• 어떠한 위치를 가르키는 인덱스는 여러 튜플로 구성될 수 도 있다.
• 저장공간을 많이 사용하지만 데이터 찾는 시간이 빠르다.

 

 

sparse Index

• 몇몇개의 search key를 위한 index 레코드만 포함한다 (모든 search key에 대한 index 존재 x).
• 정렬 되 있을 때 적합하다. ( 찾는 값 보다 적은 곳에서부터 쭉 읽으며 탐색.)
• 범위로 표현한다.  Dense 보다 적은수의 인덱스로 표현가능!
• 저장공간을 절약하지만 데이터 찾는 시간 느리다. ( access time 과 space overead간의 tradeoff )

 

Sparse index의 장점

-  Insert, delete 시에 공간, 유지 오버헤드가 dense보다 적다. ( 모든 위치에 대해 보유 x) 하지만 search time은 느리다.

좋은 타협안: clustering index+ sparse index.

Sparse index에서 각 key가 각 block안의 최소값을 가르키게 만든다 -> ( 각 블록의 최소값부터 블록의 끝까지 탐색하는 것으로 block I/O 감소가능).

 

이렇게하면 dense index와 같은 block I.O 횟수를 가지면서 낮은 space overhead를 유지가능

(최소값~ 블록 끝까지 찾아야 하는 search time이 늘어나지만 Query processin에서 block scanning time은 무시할 정도이다. 진짜 문제는 block I/O time(데이터의 위치를 찾고 이동하는 시간).)

 

 

Multi-Level index

문제점: 모든 데이터는 결국 '메모리' 에 올라가야 찾을 수 있다. 그리고 어떠한 DB를 사용할 때, 해당 DB 전체를 메모리에 올리는 것이 가장 효과적인 방법이다.

Q) 만약 1~10이라는 데이터가 DB내에 존재하는데, 1~5번만 메모리에 올라간다면?
1~5번을 메모리에 올리고 사용하다가 6~10번이 필요하면, 1~5번을 메모리에서 빼내고 6~10번을 다시 올려야한다. (Disk IO 지속적으로 발생) 따라서, Multi-Level index를 사용하여, 메모리에 전체를 올릴 수 있을 때까지 Sparse인덱스로 level을 쌓아 나가는 것으로, 정해진 메모리에 fit하게 DB에 대한 index를 통채로 올릴 수 있다.

• 만약 index가 memory 에 fit하지 않는다면 access의 cost가 높아진다( disk access해야되서)
• Multilevel index: 맨 위 헤더를 보고 어디서부터 어디 까지만 봐도 되는지 알 수 있다.
• Mul-idx는 최하위에 실제 데이터를 가르키는 Dense index를 포함하고 있다-> 상위로 갈 수 록 범위를 표현하는 인덱스가 될 것이다.
• Sparse index(outer index) 가 하위의 index 가르키고, 가장 아래에는 실제 데이터 보유한 dense index(inner index)로 실제 block의 모든 위치를 가르키게 한다.
• 이런식으로 index가 memory에 fit 할때까지 계속 level을 1개씩 더 만들어 나간다.
• Insert, delete시 모든 level에 변경 사항이 반영되어야한다.
• file 수정시에 모든 level의 index가 업데이트 되어야한다.

 

Index Update: Insertion

 원래 데이터 변경 전 데이터 기준으로 만든 인덱스는 새로운 정보 포함하지 않는다. 데이터 변경하면 인덱스는 업데이트 되어야한다.

Dense: 만약 search key value가 index안에 없다면 그냥 insert ok

아니면 추가된 데이터가 인덱스에 표현될 수 있도록( 데이터 insert에도 인덱스 변경할 필요 없도록), 어느 위치에 insert할지 찾아야.

1)    만약 index 엔트리에 모든 record로 가는 포인터가 있다면, 새로운 리코드로 향하는 pointer 형성

2)    모든 record로의 포인터 x 시 첫번째 record에 대한 pointer만 추가.

3)    Sequential file 구조로 indice가 유지될 경우: 새로운 엔트리 생성. Overflow block이 필요할 수 있다.( 순서를 유지해야되기에)

 

Sparse: 범위 안에 있으면 변경할 필요 x 만약 index가 각 파일의 block에 대한 엔트리를 모두 보유 중이라면, 변경할 필요 없다.

범위 밖:  새로운 block 생성. 새로운 block의 첫번째 search key(최소값)을 index에 추가한다.

 

 

Index Update: Deletion

지우고자하는 record가 index의 valid한 레코드일시, 어딘가에 반드시 표현되 있어야.

Dense indices: 만약 인덱스가 1개의 데이터를 포함하고 있다면, 그냥 지우면 된다.

만약 인덱스가 여러 개를 표현시, 그냥 지우면 안된다. 

(A인덱스가 1,2,3 표현하고, 2 를 지웠는데 A를 지워버리면 1, 3 유실…)

만약 1을 지우면>> A가 2를 가르키게. 만약 3을 지우면> 그대로 둬도 된다. ( 첫 위치 가르키고 쭉~ 읽어 들이는 것이기에)

 

 

 

• secondary index지울 index entry가 index 내에 없으면 그대로.
• 만약 지운 record가 유일한 search key라면, search key 순서상 다음 키로 대체 ( 다음 키 없으면 엔트리 자체 삭제)
• Search key 값을 가르키는 index entry가  지워진 record 가르키면, 같은 search key 가진 다음 record 가르키게 업데이트

Index record는 bucket을 가리키고 있다

Bucket:  모든 실제 record를 가리키는 포인터들과 특정한 search key를 가지고 있다.

Secondary indices는 dense 여야 한다. (index update의 case가 dense index 중 clustering index와 동일,  순서가 뒤죽박죽이라 index에 없는거 찾기 너무 어렵다)

위 그림에  쓴 설명처럼, sequential index로써 쓰면 비용이 너무 비싸다.