Reference - Fundamentals of Database Systems 7th edition
Indexing structures for Files and Physical Database Design
indexing을 보기에 앞서 file structure를 먼저 살펴보겠다.
database는 주로 secondary storage(disk)에 저장된다. 일반적으로 저용량의 경우 SSD, 고용량의 경우 Magnetic Disk를 사용한다. 그중에서 hard disk drive의 구조를 살펴보면, 아래의 동그란 판을 디스크라 하고 이를 묶은 것을 실린더, 이 전체를 디스크 팩이라 한다. 디스크는 회전하면서 물리적으로 데이터가 저장된 위치로 움직이며, Arm이 track을 탐색한다. ssd는 전자적으로 움직여서 소음이 적은 반면, 하드디스크는 arm이 물리적으로 움직이므로 소음이 심하다. 하지만 확장성(디스크를 쌓으면 됨)과 비용(ssd에 비해) 측면에서 보다 효율적이다.
파일은 각 분할된 데이터가 있는 주소 값으로 구성된다. 이때 데이터를 효율적으로 찾기 위해 파일 시스템을 설계해야한다.
Indexing
Index는 레코드를 검색할 때 어떻게해야 빠르게 access할 수 있을지 path를 찾는 방법을 제공한다. (called secondary access path) attribute(=column=field)는 index로 생성할 수 있다.
- single-level indexes
한 값으로 인덱스를 생성할 때의 인덱스의 종류는 primary index, clustering index, secondary index가 있다.
primary index는 key 간 중복이 없고, clustering index는 중복이 가능하다.
예시로, 학생에서 학번은 중복이 없지만, 학과 단위로 검색을 하면 중복된 학생이 있을 것이다.
이때 학번을 primary index, 학과를 clustering index라 할 수 있다.
primary index는 primary key K(i)와 pointer to disk block P(i)로 구성된다. 이때 데이터베이스를 primary key값으로 정렬해서 저장한다. disk block의 시작 위치 주소를 P(i)라 한다. 이때 P(i)는 물리적 주소 혹은 논리적 주소로 사용될 수 있다.
primary index는 insertion이나 deletion 시 문제가 있는데, 저장할 수 있는 record수를 넘겼을 때 insert를 수행하면 overflow가 발생할 수 있다. overflow가 되면 다른 block으로 포인터를 가리키는 linked list 등을 사용할 수 있다.
deletion시에도 문제가 있는데, 삭제가 되면 다음 index의 데이터를 한칸 땡겨와야 한다.
clustering key도 마찬가지로 두 field로 key와 pointer가 있는데, key는 중복이 가능하며 정렬이 되어있다. 마찬가지로 overflow가 발생하면 다른 block을 가리키게 만들어 block을 확장시킬 수 있다. 마찬가지로 deletion 문제가 있다.
secondary index도 key, pointer를 가지고 있는데, 순서가 없다. 정렬하지 않고 순서가 없는 attribute를 대상으로 사용한다.
논리 주소에 physical 주소와 offset 정보가 나오게끔 한다면 효과적으로 secondary index를 관리할 수 있다.
이때 key의 index는 자주 조회되는 정보를 사용한다. 예시로 학번을 primay index, 이름을 secondary index로 사용할 수 있다.
- multi-level indexes
순차 검색보다 빠르게 linked list처럼 구성된 index다. 이때 Tree data structure를 사용한다.
Tree는 연산 시간을 획기적으로 줄여주는데, tree의 balance를 맞추기 어려워 completion time을 보장하기 어렵다는 단점이 있다. 이를 해결하기 위해 multilevel index는 B-tree와 B+tree를 사용하여 구현한다. 자세한 내용은 아래 글에서 확인할 수 있다.
https://yeongjaekong.tistory.com/38
[자료구조] B-tree란? / B-tree의 연산 / B*tree, B+tree / B+tree 구현
B-tree란? B-tree는 Self-balanced Tree 중 가장 유명한 자료구조입니다. Balanced-tree를 의미하며, 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조입니다. 즉,
yeongjaekong.tistory.com
- Indexes on Multiple Keys : Composite keys, Partitioned hashing, etc.
Multiple key는 Grid file 형태로 Bucket안에 데이터가 저장된다.
Hash index의 경우 Hash value가 같은 값을 하나의 block에 저장해서 indexing한다.
산술 연산만 하면 돼서 굉장히 빠르다. (O(1)) 문제는 Hash collision 및 overflow 처리에 대한 이슈가 있다.
Bitmap Index의 경우 특정 column을 bitmap index로 해서, bitmap으로 표기한다.
이 방법도 데이터 양이 작기에 굉장히 빠르다. 하지만 제한된 환경에서만 사용할 수 있을 것이다. (ex. B+ tree의 leaf node 표현)
pointer가 실제 데이터가 저장하는 위치를 가리키는데, 이게 변경되면 메타데이터와 디스크를 모두 변경해주어야 하기 때문에 overhead가 크므로 logical index를 사용하기도 한다.
- Tuning indexes
performance requirement를 만족시켜주기 위해 튜닝을 하는데, index reorganize, 테이블 설계, query optimizing 등을 쓴다. index를 tuning하는 것은 안쓰는 인덱스를 삭제하거나, 변경이 잦은 정보는 사용하지 않거나 등의 방법을 사용할 수 있다.
