티스토리 뷰
잡설
취업 준비를 하며 여러가지를 공부하고 있는 요즘 머릿속에 들어가는 건 많은데, 머리 한구석에 구멍이라도 난 듯 지식의 누수가 심하다... 그래서 배웠던 내용들을 복습도 할 겸해서 블로그를 개설하게 되었다. 이번 포스트는 블로그를 개설하고 처음 작성하는 포스트이고 그 주제는 데이터베이스의 index로 정했다. 관련된 내용들이 많아 의도치 않게 쪼개서 업로드를 해야 될 거 같아 세부 주제도 나누었으니 참고하길 바란다. 그럼 잡설은 이 정도로 하고 본격적인 내용에 들어가기로 하겠다.
Index란?
- 데이터베이스에서 data file(table)의 특정 데이터(record)에 빠르게 접근하기 위한 자료구조
- Index는 정렬의 여부에 따라 크게
ordered index와hash index로 구분
장점
- 데이터(record)에 접근하는 시간을 줄일 수 있다.
단점
- Index를 위한 추가적인 메모리 공간이 필요하다.
- Index가 적용된 data file(table)에 update작업이 실행될 경우, index에서도 update가 일어나 추가 비용이 필요하다.
Index의 기본 구성요소
Search-key
데이터베이스의 한 data file(table)에서 record(row)를 조회하기 위한 값 또는 값의 집합들. 여기서 말하는 key는 primary key, candidate key등에서 사용하는 단어와 의미가 다르다.
Index file의 기본 구조
Search-key와 pointer로 구성되어 있는 record(index entry)들의 모음. pointer의 경우, 실제 데이터가 저장되어 있는 disk block을 식별하기 위한 identifier와 record가 block에서 어디에 위치해 있는지에 대한 offset으로 이루어져 있다.
Ordered index 평가 지표
모든 상황에서 이상적으로 동작하는 index는 없다. 그렇기 때문에 각 index를 적절하게 사용하기 위해서는 이를 평가하기 위한 기준이 필요하다. 다음 기준은 ordered index의 성능을 판단하기 위해서 제안되었고, 총 3가지 항목으로 나눠져 있다.
1. Access type
a. Point query: 특정 value에 대한 질의를 수행할 수 있는지의 여부
ex) 닉네임이 ABC인 회원 정보 조회
b. Range query: 특정 value들에 대한 질의를 수행할 수 있는지의 여부
ex) 닉네임에 A로 시작하는 회원들의 정보 조회
2. Time
a. Access time: 특정 데이터를 조회하는 데 걸리는 시간
b. Insertion time: 새로운 데이터를 삽입할 정확한 위치를 찾는 시간 + 데이터를 삽입하는 데 걸리는 시간 + 삽입하고서 index의 구조를 수정하는데 걸리는 시간
c. Deletion time: 삭제할 데이터를 찾는데 걸리는 시간 + 특정 데이터를 삭제하는 데 걸리는 시간 + 삭제하고서 index의 구조를 수정하는데 걸리는 시간
3. Space
Index를 사용함으로써 발생하는 추가적인 저장 공간에 대한 기준. 이 기준은 index의 성능이 좋다면 희생될 수 있는 우선순위가 낮은 항목
Ordered index의 구조
Ordered index는 정렬된 순서가 실제 물리적 저장 순서에도 영향을 미치는지에 따라 각각 primary index와 secondary index로 구분된다.
Primary index(Clustering index)
- Index가 정렬된 기준이 실제 물리적 데이터가 정렬된 기준과 일치한다.
- Primary index의 primary는 데이터베이스의 primary key에 대한 의미도 내포되어 있지만, 그렇다고 해서 primary index의 search-key가 반드시 primary key이어야 할 필요는 없다
- Primary index는 다른 용어로 clustering(clustered) index라고 부른다.
- 실제 데이터가 정렬되어 있기에 sequential scan이 효율적이다.
- 데이터가 순서대로 정렬되어 있기 때문에 range query에 유리하다.
- ex) '주민등록번호가 93으로 시작되는 사람들의 정보를 조회하라'는 질의를 처리할 경우 첫번째 93으로 시작하는 사람의 정보를 찾으면 94로 시작하는 사람이 나오기 전까지의 정보를 반환하면 된다.
Secondary index(Non-clustering index)
- Index가 정렬된 기준과 실제 물리적 데이터가 정렬된 기준과 일치하지 않는다.
- Table당 여러개의 secondary index를 가질 수 있다.
- Secondary index의 search-key는 unique할 필요없다.
- Secondary index는 실제 데이터의 정렬 순서와 무관하게 나열되어 있기에 데이터에 접근하기 위해서는 index의 type이 반드시 dense index이어야 한다.
- 중복된 search-key의 값을 허용하기 때문에, bucket이라는 실제 record block을 가리키는 자료구조를 통해 record block에 접근한다.
-> Bucket을 통해 데이터 record block에 접근하기 때문에 그만큼의 시간이 더 소모된다.
-> 만일 search-key가 적게 중복되거나 중복되지 않았을 경우, bucket에 미리 할당한 만큼의 메모리 낭비가 발생할 수 있다. - Index가 존재하지 않는 것보다는 빠르게 데이터에 접근할 수 있지만, primary index보다는 더 많은 시간을 필요로 한다.
- Secondary index는 다른 용어로 non-clustering(non-clustered) index라고 부른다.
- 실제 데이터가 정렬되어 있지 않기에 sequential scan하는 것은 비효율적이다.
- Range query를 수행할 수 있으나, 실제 데이터가 저장된 순서와 index의 순서가 다르기 때문에 record마다 random I/O operation이 요구되어 데이터베이스의 성능에 치명적일 수 있다.
Ordered index type
Dense index
- Search-key로 선정된 table의 attribute의 모든 값이 index file에 나타났을 때의 type
- Dense index는 모든 pointer가 실제 record block을 가리키는 경우([그림4]의 왼쪽)와 첫번째 search key값이 등장하는 부분만을 가리키는 경우([그림4]의 오른쪽)로 나눌 수 있다.
-> 첫번째 record block만을 가리키는 경우([그림4]의 오른쪽) clustering index의 구조를 가져야지만, pointer를 이용해 같은 search-key의 값을 가지는 다른 record block에 접근할 수 있다.
Sparse index
- Search-key로 선정된 table의 attribute의 값이 일부만 index file에 나타났을 때의 type
- Data file(table)의 record(row)들이 fragmentation 되지 않게끔 record 단위로 block에 저장되는 index type
- Index file의 각 entry가 가리키는 pointer는 record들이 저장된 disk block의 시작주소를 가리킨다.([그림5])
- Dense index보다 공간에 대한 효율성이 좋고 insertion/deletion에 대한 오버헤드가 적다.
- 일반적으로 dense index보다 데이터에 대한 접근 속도가 느리다.
Multi-level index
- Primary index가 너무 커져서 main memory에 모두 loading 할 수가 없을 경우 사용하는 index
- Primary index는 sequential file로 disk에 두고 그 위에 sparse index를 구성하여 memory에 올려 사용한다.
- Inner index는 primary index이고, outer index는 primary index에 대한 sparse index가 된다.
- 만일 outer index도 크기가 너무 커져 memory에 loading 할 수 없을 경우 같은 방법으로 outer index에 대한 outer index를 구성한다.
- 이 경우는 sparse index에 대한 sparse index가 만들어진다.
- 데이터에 접근하기까지 연속적으로 random I/O operaion이 수행된다. 때문에 실제 데이터는 정렬되어 있을지라도 데이터 접근속도는 느려진다.
- 데이터(record)에 대한 insertion 또는 deletion이 일어났을 경우, 모든 level에서 수정이 일어나게 된다.
Ordered index의 수정
데이터베이스는 table에 삽입 또는 삭제될 record의 search-key의 값을 활용하여 index를 탐색한다. 그 후에 행동은 index의 type이 dense 혹은 sparse인지에 따라 나눠지게 된다.
Insertion
- Dense index:
- 만일 search-key의 값이 index에서 처음 등장하는 것이라면, 데이터베이스는 index entry를 적절한 위치에 삽입한다.
- 중복된 search-key 값을 가지는 경우 다시 두 가지의 경우로 나눠진다.
a. Index가 같은 search-key 값을 가진 record에 대해서도 pointer를 저장한다면, index file에 새로운 entry를 추가한다.
b. Index가 search-key의 값이 처음 등장하는 record에 대해서만 pointer를 저장한다면, 같은 search-key 값을 가지는 가장 마지막 줄에 entry를 추가한다.
- Sparse index:
- 데이터베이스에서 새로운 block을 만들었을 경우, 첫번째 search-key 값을 가지는 entry로 삽입 후 pointer로 해당 block을 가리키게 한다.
- 만일 table에 삽입된 record가 해당 block에서 가장 작을 경우, index entry의 search-key 값을 수정한다.
- 위의 경우가 아니라면, index에는 아무런 수정도 일어나지 않는다.
Deletion
- Dense index:
- 만일 삭제된 record가 특정한 search-key 값을 가진 유일하다면 데이터베이스는 index에서 해당 index entry를 삭제한다.
- 중복된 search-key 값을 가지고 있는 경우 다시 두 가지로 나눠진다.
a. Index file이 모든 중복된 search-key 값을 가지는 record에 대한 pointer를 저장한다면, 해당 index entry를 삭제한다.
b. Index가 search-key의 값이 처음 등장하는 record에 대하서만 pointer를 저장하고, 삭제되는 record가 첫 번째 record 라면,다음 record를 pointer로 가리키게끔 수정한다.
- Sparse index:
- 만일 index가 삭제된 record에 대한 index entry를 가지고 있지 않다면, 수정되지 않는다.
- Index가 삭제된 record에 대한 index entry를 가지고 있다면, 두 가지의 경우로 나눠진다.
a. 삭제된 record가 search-key 값을 가지는 유일한 record라면, 데이터베이스는 index entry가 다음 search-key 값을 가지는 record를 가리키게끔 pointer를 수정한다. 만일, 다음 search-key 값이 이미 index file에 저장되어 있다면, index entry는 대체되지 않고 그대로 삭제된다.
b. 삭제된 record와 같은 search-key값을 가지는 다음 record를 가리키게끔 entry의 pointer를 수정한다.
참고
Database system concepts 7th edition written by Avi Silberschatz, Henry F. Korth, S. Sudarshan
Database index - wikipedia
ECS 165A Winter 2011 - Introduction to Database Systems
joosjuliet.github.io