Overview of Storage and Indexing
저장장치와 인덱싱 개론 (8장)
- 다양한 종류의 Seleciton을 효율적으로 지원하게 하고,
다양한 방식으로 레코드들의 집합에 접근할 때 인덱스를 사용한다.
- DBMS Components
- Storage Manager
- Query Processor (Query Optimizer, Query Engine)
- Transaction Manager
- Data Analysis
- 분산, 병렬 처리
- Data Mining
External Storage
Disk
- 고정비용으로 Page에 대해 직접 접근이 가능하다.
Tape
- 순차접근만 허용하기 때문에 직접 접근이 불가능하다.
(즉, 느리다.)
Internal Storage (Main Memory)
File (파일)
- Record의 집합이다.
- DBMS에서 데이터에 대한 가장 기본적인 Abstraction이다.
File Organization (파일 구성)
- 디스크에 파일을 저장할 때 파일 내의 레코드들을 배열하는 방법이다.
- RID와 Index 메커니즘이 사용된다.
RID (Record-ID)
- 각 레코드들은 RID라 불리는 Unique Identifier를 갖고 있으며,
RID는 해당 레코드가 포함된 Page의 디스크 주소를 식별할 수 있다.
- RID를 통해 레코드에 직접 접근하여 빠른 처리를 가능하게 한다.
Index (인덱스)
- Index Search Key를 통해 RID를 보다 빠르게 찾을 수 있게하는 자료구조이다.
Page (페이지)
- 데이터는 디스크에 Page 단위로 Read/Write되며,
이 Page는 보통 4KB 혹은 8KB의 크기를 가진다.
(Page의 크기는 DBMS Parameter 중 하나이다.)
- Page I/O Operation(Main Memory와 Disk간 I/O)은 DB Operation Cost의 대부분을 차지하기 때문에
DBMS는 이 비용을 최소화하도록 최적화되어 있다.
Storage Manager = File Manager + Buffer Manager
8.1 Data on External Storage (외부 저장장치상의 데이터)
- 데이터는 프로그램 실행 과정에 있어 지속되어야 하는데,
데이터의 양이 커질수록 모두를 Main Memory에 저장할 수 없기 때문에
우선순위가 떨어지는 데이터들을 Secondary Storage(Disk, Tape 등)에 저장한다.
- Secondary Storage에 저장된 데이터들은 필요할 때 Main Memory로 Load되는데,
이 때 데이터는 Page 단위로 Load되며, 한 Page는 일반적으로 4KB 혹은 8KB이다.
(Page의 크기는 DBMS의 Parameter 중 하나이다.)
- Main Memory와 Storage 사이의 Page I/O는 DB Operation에서 발생하는 Cost의 대부분을 차지하기 때문에
DBMS는 Page I/O를 최소화하도록 설계되어 있다.
- Buffer Manager는 Main Memory와 Storage 사이를 오가는 데이터의 Load/Store를 관리하는 DBMS Component이다.
- Disk Space Manager는 Disk 공간을 관리하는 DBMS Component이다.
Points of Secondary Storage (Storage의 요점)
- Disk는 거의 고정된 Cost로 임의의 Page를 검색할 수 있으며,
순서대로 여러 Page를 읽는것이 랜덤하게 여러 Page를 읽는 것보다 Cost가 더 적을 수 있다. - Tape은 Sequential Access Device이며, 대개 중요도가 떨어지는 데이터들이 저장된다.
- RID(Record-ID)는 File에 저장된 각 Record들을 유일하게 식별할 수 있게 해주는 Unique Indentifier이다.
또한, RID를 통해 해당 Record가 포함된 Page의 Disk Address를 식별할 수 있다.
8.2 File Organizations and Indexing (파일 구성과 인덱싱)
Scan Operation (스캔 연산)
- File의 모든 Record들을 살펴보는 연산이다.
File Layer
- File에 저장된 Record들을 여러 Disk Page에 나누어 저장한다.
- 각 File에 할당된 Page들을 기록하고, Record가 삽입/삭제되는 과정에서 Page 내부의 공간을 관리한다.
- File의 구조는 아래와 같이 크게 3가지로 구성된다.
- Heap File (Unordered File)
- 데이터 파일 구조 중 하나로, Recode들이 File에 저장될 때, 랜덤하게 저장되는 파일 구조이다. - Sorted File
- 데이터 파일 구조 중 하나로, Recode들을 정렬하여 File에 저장하는 파일 구조이다. - Index (인덱스)
- Retrieval Operation(검색 연산)을 최적화하기 위해 Disk상에서 레코드들을 구성하는 데이터 구조이다.
- 찾고자하는 Data File의 RID를 빠르게 찾아내는 것을 목표로 한다.
- Record의 Search Key Field를 기준으로 검색 연산을 수행하고,
연산 속도를 향상시키기 위해 추가적인 Search Key를 삽입할 수도 있다.
- B+ Tree나 Hash 구조로 구현되는 Data Structure이다.
Index Entry
- 검색 과정을 돕는 Entry로, B+ Tree의 Non-Leaf Page를 구성한다.
- Pointer Field로 구성되어 Leaf Page(Data Entry)로 향할 때 사용되는 이정표 역할을 한다.
- 인덱스 엔트리는 <k, Pointer>로 구성된다.
(k는 Search Key이다.)
Data Entry (\(k^*\))
- Search Key k를 갖는 하나 이상의 Data Record들이 저장된 Index File을 의미한다.
(즉, Index File을 구성하는 Record이다.)
- 아래는 Index에 Data Entry로 저장하는 방법들이다.
- Alternative 1
Search Key \(k\)를 포함하는 Data Entry \(k^*\)에 실제 Data Record가 저장되고, Index는 Data Record의 파일이다.
(Clustered Index, Primary Index)
※ 여기서 Primary Index는 Primary Key를 포함하는 인덱스라는 의미가 아니다. - Alternative 2
Data Entry는 <k, RID> Pair로 구성된다. RID는 해당 레코드의 Record-ID이고, \(k\)는 해당 레코드의 Search Key이다.
(Data Record를 정렬하여 유지하지 않는 한, Unclustered Index, Secondary Index)
- Search Key k를 가진 Data Record가 하나만 존재하는 경우이다.
(즉, k가 Primary Key인 경우이다.) - Alternative 3
Data Entry는 <k, RID-List> Pair로 구성된다. RID-List는 Search Key \(k\)를 갖는 Data Entry들의 ID가 저장된 리스트다.
(Data Entry의 크기가 Variable Sized이다.)
(Data Record를 정렬하여 유지하지 않는 한, Unclustered Index, Secondary Index)
- Search Key k를 가진 Data Record가 여러개 존재하는 경우이다.
(즉, k가 Primary Key가 아닌 경우이다.)
※ 여기서 Secondary Index는 Primary Key를 포함하지 않는 인덱스라는 의미가 아니다.
Index Classification
Primary Index (기본 인덱스)
- Primary Key(기본 키)를 포함하는 Field에 대한 Index를 의미한다.
Secondary Index (보조 인덱스)
- Primary Index 외의 모든 인덱스를 의미한다.
Unique Index (유일 인덱스)
- Search Key가 어떤 Candidate Key(후보키)를 포함하고 있는 인덱스를 지칭하는 용어이다.
Clustered Index (군집 인덱스)
- Sorted File에 저장된 Data Record의 순서와 Index의 Data Entry의 순서가 동일하도록 구성한 Index File이다.
(즉, Data Entry를 정렬하여 유지하면 Clustered라 표현한다.)
- Range Selection(범위 탐색 질의)에 유리하다.
- 한 데이터베이스에 군집 인덱스는 단 하나만 존재할 수 있다.
(정렬 기준은 두 개 이상일 수 없기 때문이다.)
Unclustered Index (비군집 인덱스)
- Heap File의 Data Record의 순서와 Index의 Data Entry의 순서가 일치하지 않는 Index File이다.
(즉, Data Entry를 정렬하지 않은채로 유지하는 Index File 구조이다.)
- Range Selection(범위 탐색 질의)에 불리하다.
(범위에 해당되는 Data Record들이 여러 Page에 걸쳐 산개되어 있기 때문이다.)
Duplicate (중복)
- 두 Data Entry가 Index와 관련된 Search Key Field에 대해 동일한 값을 가지는 경우를 의미한다.
- Primary Index는 Duplicate가 발생하지 않음이 보장되지만,
다른 Field들에 대한 Index에서는 Duplicate이 발생할 수 있다.
8.3 Index Data Structures (인덱스 자료 구조)
Hash-Based Indexing (해시 기반 인덱싱)
- h( Search_Key ) = Bucket_Address 구조의 인덱싱 방법을 의미한다. (여기서 h는 Hash Function이다.)
(Bucket_Address를 얻은 후, 해당 Bucket의 모든 Page를 살펴 Search_Key에 해당하는 Record를 찾아낸다.)
- 해시 기반 인덱싱에서 File내의 Record들은 Bucket으로 분류된다.
- Tree-Based Indexing과 달리, Index Entry(Non-Leaf Node)를 필요로 하지 않는다.
(검색에 중간과정이 없기 때문에 Equality Search에 유리하다.)
Bucket (버켓)
- 해시 기반 인덱싱에서 Record들이 저장되는 단위이다.
- Primary Page(기본 페이지)로 구성되며, 경우에 따라 Chain으로 연결된 Additional Page들로 구성될 수 있다.
- Tree-Based Indexing과 달리, 각각의 Bucket들끼리는 연결되어 있지 않으며, 정렬 또한 되어있지 않다.
- Tree-Based Indexing에서의 Leaf Node와 비슷한 개념이다.
Tree-Based Indexing (트리 기반 인덱싱)
- Data Entry들이 Search Key를 기준으로 정렬되어 저장된 Sorted File 구조로 저장되어 있다.
(이 때문에 Range Search에 유리하다.)
- Tree를 구성하는 각각의 Node들은 Physical Page들이다.
(즉, 각 Node에 접근할 때 마다 Disk I/O가 발생한다.)
- Leaf Node는 Data Entry로 구성되며, Leaf Node들 간에는 Doubly-Linked List 형태로 연결되어 있다.
- Non-Leaf Node는 Node Pointer(Index Entry)를 저장하고 있어 중간 경로 역할을 한다.
- 모든 검색은 Root Node에서 시작하며, Root Node는 빈번히 접근되므로 Disk가 아닌, Buffer Pool에 저장되어 있다.
(즉, Root Node에 접근할 때는 Disk I/O가 발생되지 않는다.)
- Fan-Out은 Non-Leaf의 평균 Child수를 의미한다.
(즉, 트리 기반 인덱싱에서 Leaf Page의 개수는 \(F^h\)이다. \(F\)는 평균 Fan-Out 수, \(h\)는 Tree의 Height이다.)
- Search시 발생하는 I/O Cost = Root에서 Leaf까지의 경로의 길이 + 검색 대상 Data Entry를 가진 Leaf Page의 수
- 트리 기반 인덱싱에서는 Search 성능이 Binary Search보다도 우수한데,
그 이유는 Non-Leaf Node들이 매우 많은 Node Pointer들을 갖고 있어
실제 Tree의 Height가 3~4에 불과하기 때문이다.
8.4 Comparison of File Organization (파일 구성의 비교)
* Operations (연산의 종류)
| Operation | Description |
| Scan | - File의 모든 Record를 Fatch한다. - Page를 Disk에서 Buffer Pool로 Load하고, 가져온 Page에서 Record를 탐색한다. |
| Search with Equality Selection | - 어떠한 값에 정확히 일치하는 모든 Record를 가져온다. - 해당 Record를 포함한 Page를 Fatch하고 Page 내에서 Record 위치를 특정한다. |
| Search with Range Selection | - 범위에 해당되는 값을 가진 모든 Record를 가져온다. - 해당 Record를 포함한 Page를 Fatch하고 Page 내에서 Record 위치를 특정한다. |
| Insert Record | - 새 Record가 삽입될 Page를 식별하고 Record를 삽입한 Page를 다시 Disk에 저장한다. |
| Delete Record | - RID를 통해 삭제할 Record가 저장된 Page를 식별하고 Page에서 Record를 삭제한 후 Page를 다시 Disk에 저장한다. - 이때, 삭제로 인해 생긴 Page 내의 빈 공간을 Compact하는 연산이 수행될 수 있다. |
* Legend (범례)
| Cost | Description |
| B | - Page 개수 (낭비되는 공간이 없다고 가정) |
| R | - Page 당 Record 개수 |
| D | - Page 당 평균 I/O 시간 |
| C | - 메모리에서 한 Record를 처리하는데 걸리는 시간 |
| H | - 한 Record를 Hashing하는데 걸리는 시간 (Hash-Based Indexing) |
| F | - Fan-Out (Tree-Based Indexing) |
Heap File with No Index (힙 파일)
| Operation | Cost | Description |
| Scan | BD + BRC | - B개의 Page 검색 후 BR개의 Record들을 C 시간씩 처리한다. |
| Search with Equality Selection |
{1 \over 2}BD + {1 \over 2}BRC | - Primary Key에 대한 Equality Search라 가정한다. (즉, 정확히 하나의 Record만 Match된다.) - 평균적으로 파일 절반을 Scan한 후, 검색된 Page에서 해당 Record를 탐색 - 검색에 부합하는 Record가 없는 경우, File 전체를 Scan하게 된다. - Candidate Key가 아닌 Field에 대한 Selection인 경우, File 전체를 Scan하게 된다. |
| Search with Range Selection |
BD + BRC | - 조건에 맞는 Record가 어디있을지 모르기 때문에 File 전체를 Scan한다. |
| Insert Record | 2D + C | - 마지막 Page를 Fetch하여 새로운 Record를 추가한 후 다시 Store한다. |
| Delete Record | Search + D | - 제거할 Record가 속한 Page를 RID를 통해 찾아 Fetch한 후 Page에서 Record를 제거하고 수정된 Page를 다시 Store한다. - 빈 공간에 대한 Compaction도 수행될 수 있다. |
Sorted File with No Index (정렬 파일)
| Operation | Cost | Description |
| Scan | BD + BRC | - 모든 Page를 검사한다. |
| Search with Equality Selection |
\(D\log_2 B + C\log_2 R\) | - Binary Search로 원하는 Record가 저장된 Page를 검색한다. - Binary Search로 Page내에서 Record를 검색한다. |
| Search with Range Selection |
\(D\log_2 B + C\log_2 R\) | - Binary Search로 원하는 Record가 저장된 Page를 검색한다. - Binary Search로 Page내에서 Record를 검색한다. - Sequential Search로 조건의 범위를 넘어서는 Record가 발견될 때 까지 검색한다. |
| Insert Record | Search + BD + BRC | - 삽입할 Page를 검색하고 삽입한 다음 후속 Page를 전부 수정한다. (기존 Record들을 한 Slot씩 모두 뒤로 미룬다.) |
| Delete Record | Search + BD + BRC | - 삭제할 Record를 검색하고 수정된 Page를 다시 Store한다. - Compaction을 위해 삭제된 Record 이후의 모든 Record를 앞으로 당긴다. |
Clustered File (군집 파일)
- 통계적으로, Clustered File의 Page의 Occupancy는 67%이다.
즉, 실제적인 Data Page의 수는 1.5B가 된다.
| Operation | Cost | Description |
| Scan | 1.5BD + 1.5BRC | - 모든 Page를 검색한다. |
| Search with Equality Selection |
D\log_F 1.5B + C\log_2 R | - Binary Search로 조건을 만족하는 Record가 포함된 Page를 검색한다. - Binary Search로 해당 Record를 검색한다. |
| Search with Range Selection |
D\log_F 1.5B + C\log_2 R | - Binary Search로 조건을 만족하는 Record가 포함된 Page를 검색한다. - Binary Search로 해당 Record를 검색한다. - Sequential Search로 조건의 범위를 넘어서는 Record가 발견될 때 까지 검색한다. |
| Insert Record | D\log_F 1.5B + C\log_2 R + D | - 대부분의 Page들은 새로운 Record를 삽입하기에 충분한 공간을 갖고 있어, 새 Record를 삽입하기 위해 특정 Page를 검색해야 하는 일은 거의 발생되지 않는다. - 즉, Root에서 Leaf Node(= Page)까지 도달한 다음 Record를 추가하기만 하면 된다. |
| Delete Record | D\log_F 1.5B + C\log_2 R + D | - 삭제할 Record를 검색하고, Page에서 해당 Record를 삭제한 후 수정된 Page를 Store한다. |
Heap File with Unclustered Tree Index (비군집 트리 인덱스를 가지는 힙 파일)
- 일반적으로, Index에서의 Data Entry의 크기가 Record의 크기의 10%이고
Index Page의 Occupancy Rate이 67% 이므로
Index의 Leaf Page의 개수는 0.1 * 1.5B = 0.15B 이고,
한 Page에서 Data Entry의 개수는 10 * 0.67R = 6.7R 이다.
- Index Page를 꽉 채우지 않음으로써 B+ Tree의 Split-Merge Overhead를 줄일 수 있다.
| Operation | Cost | Description |
| Scan | 0.15B(D + 6.7RC) | - 인덱스의 단말 레벨을 스캔하고 각 데이터 엔트리에 대해 파일로부터 해당 데이터 레코드를 가져온다. |
| Search with Equality Selection |
D\log_F 0.15B + C\log_2 6.7R + D | - 원하는 엔트리를 포함하는 첫 Page를 찾아낸 후 그 Page에서 검색 조건에 부합되는 첫 데이터 엔트리를 Binary Search로 찾은 다음 첫 Data Record를 I/O하여 가져온다. |
| Search with Range Selection |
D\log_F 0.15B | - 원하는 엔트리를 포함하는 첫 Page를 찾아낸 후 그 Page에서 검색 조건에 부합되는 첫 데이터 엔트리를 Binary Search로 찾은 검색 범위를 벗어난 엔트리가 나올때까지 Sequential Search로 찾아낸다 - 검색 범위에 부합되는 Record의 수가 증가함에 따라 비용은 빠르게 증가한다. - 경험적으로, 조건 범위를 만족하는 Record가 10%이상이라면 모든 Record를 검색하여 정렬한 다음 조건에 부합하는 Record만 뽑아내는게 더 낫다. |
| Insert Record | D\log_F 0.15B + C\log_2 6.7R + D | - Heap File에 Record를 삽입하고, Index에 해당 Data Entry를 삽입하고 이를 Disk에 Store한다. |
| Delete Record | D\log_F 0.15B + C\log_2 6.7R + D + 2D | - Index와 Heap File에서 각각 Data Entry와 Record를 찾아 제거한다. - Index와 Heap File에서 수정된 Page를 다시 Disk에 Store한다. |
Heap File with Unclustered Hash Index (비군집 해시 인덱스를 가지는 힙 파일)
- 각 Data Entry의 크기는 Data Record의 10%라 가정
- Hash File의 Page들의 Occupancy Rate는 80%라 가정
- 즉 필요한 Page는 1.25 * 0.1B = 0.125B 이고,
한 Page의 Data Entry의 수는 10 * 0.8R = 8R 이다.
- 정적 해싱이라 가정
- Overflow Chain이 없다 가정
| Operation | Cost | Description |
| Scan | BR(D + C) | - Record간 순서가 없기 때문에 비싼 비용을 치른다. |
| Search with Equality Selection |
H + 2D + 4RC | - 검색 조건을 Hashing하여 해당 Data Entry를 가진 Page를 식별하고 해당 Page 내에서 해당 Record를 찾는데 평균적으로 절반을 검색해야 한다. - Record를 찾았으면 해당 Record를 가져온다. |
| Search with Range Selection |
B(D + RC) | - Heap File 전체를 Scan해야 한다. |
| Insert Record | H + 4D + 2C | - Heap File에 Record를 삽입하는 것과 동일하며 추가적으로 Index File에서 적절한 Page를 찾아 새 Data Entry를 삽입한다. |
| Delete Record | H + 4D + 4RC | - Index File과 Heap File에서 삭제 대상 Record를 검색하고, 삭제한 다음 수정된 Page를 다시 Store한다. |
Performance Summary
| File Type | Scan | Equality Search | Range Search | Insert | Delete |
| Heap with No Index |
BD (Best) |
0.5BD | BD | 2D (Best) |
Search + D (Best) |
| Sorted with No Index |
BD + Sorting | D\log_2 B | D\log_2B + # of Matching Pages | Search + BD | Search + BD |
| Clustered | 1.5BD | D\log_F 1.5B | D\log_F 1.5B + # of Matching Pages | Search + D | Search + D |
| Unclustered Tree Index |
BD(R + 0.15) | D(1 + \log_F 0.15B) | D(\log_F 0.15B + # of Matching Pages) | Search + 2D | Search + 2D |
| Unclustered Hash Index |
BD(R + 0.125) | 2D | BD | Search + 2D | Search + 2D |
Heap: 저장 효율 우수, 빠른 스캔, 빠른 레코드 삽입, 느린 탐색, 느린 삭제
Sorted: 저장 효율 우수, Heap보다 빠른 탐색, 느린 삽입, 느린 삭제
Clustered: 저장 효율 우수, Sorted보다 빠른 탐색, 효율적 삽입, 효율적 삭제
Unclustered Tree Index: 빠른 탐색, 빠른 삽입, 빠른 삭제, 느린 스캔, 느린 범위 탐색
Unclustered Hash Index: 약간 빠른 탐색, 빠른 삽입, 빠른 삭제, 범위 탐색 지원 X
8.5 Indexes and Performance Tuning (인덱스와 성능 튜닝)
- 파일구조와 인덱스에 따라 효과적인 연산이 제각기 다르다.
Clustered Index (군집 인덱스)
- 완전 정렬파일보다는 Cost가 적지만, 그럼에도 불구하고 유지비용이 많이 드는 형태이다.
Index-Only Evaluation (인덱스 한정 평가)
- 데이터 레코드에 접근하지 않고, 인덱스에 있는 데이터 엔트리만을 사용하여
데이터에 접근하는 것을 의미한다.
- 파일의 데이터 레코드를 검색할 필요가 없으며, 파일 상의 인덱스만을 이용하여 질의를 완전히 처리할 수 있다.
- Unclustered Index에 해당되는 개념이며, Clustered Index에는 사용할 수 없다.
(Clustered Index에는 데이터의 값이 저장되지 않고 데이터에 대한 포인터만 저장되기 때문이다.)
Composite Search Key (Concatenated Key; 복합 탐색 키, 연결키)
- 여러 필드를 포함하고 있는 인덱스의 탐색키를 의미한다.
- 넓은 범위의 질의를 수용할 수 있다.
- Index-Only Evaluation을 수행할 기회가 많아진다.
- 삽입, 삭제, 업데이트 연산이 발생될 때 마다 복합 탐색 키도 업데이트 되어야 한다.
- 각각의 엔트리의 크기가 일반적인 인덱스의 엔트리의 크기보다 크다.
(커지는 엔트리의 크기 때문에 키 압축 메커니즘을 사용하기도 한다.)
- WHERE절에 명시된 조건이 복합 인덱스에 대해 Selective하면 검색이 빠르게 이루어진다.
- Aggregate Query에 유용하다.
Reference: Database Management Systems 3E (Raghu Ramakrishnan, Johannes Gehrke 저, McGrawHill, 2003)
