Basic Concept
- Indexing mechanism은 원하는 data에 접근하는 시간을 단축시키기 위해 사용된다. ex. 도서관에 저자 catalog
- Search Key : a set of attributes used to look up records in a file
- Index file은 records(index entries)를 포함하고,
각 record는 다음과 같은 형태를 가진다.
- pointer : search key에 대한 주소
- Index file은 보통 original file보다 size가 매우 작다
- Two basic kinds
- Ordered Indices : search keys are stored in sorted order
- Hash Indices : search keys are distributed uniformly across "buckets" using a hash function
- Index evaluation metrics
- access time, insertion time, deletion time, space overhead
Ordered Indices
- index entries가 search key에 대해 정렬되어 있다.
- Clustering index : the index whose search key specifies the sequential order of the file
- also called primary index
- 주로 primary key를 사용하지만, 꼭 primary key일 필요는 없다.
- 위 예시에서는 ID가 clustering index가 된다.
- Secondary index : an index whose search key specifies an order different from the sequential order of the file(??)
- also called nonclustering index
- 얘의 search key는 저장 순서를 따르지 않는다.
- Index-sequential file : sequential file ordered on a search key, with a clustering index on the search key
Dense Index file
- Dense index : index record appears for every search-key value in the file
- 모든 search key에 대해 entry가 존재한다
Clustering vs Nonclustering Indices
clustering index를 쓰면,
- 특정 tuple을 검색하거나 sequential scan을 할 때에는 efficient하다
- 하지만 record 삽입/삭제될 때마다 모든 index가 update되어야 한다.
nonclustering index를 쓰면 반대로
- scan하는 데 불필요한 I/O가 많이 발생하기 때문에 매우 expensive
- 하지만 수정될 때는 수정된 속성에 대한 index만 update하면 된다.
Sparse Index file
- Sparse index : 몇몇 search key value에 대한 index record를 가진다.
- search key로 sequentially 정렬된 record에 적합하다.
즉, clustering index에 대해서만 가능하다
- Search key value가 K인 record를 위치시키기 위해서는
- K보다 작은 것중에 가장 큰 search key value를 갖는 index record를 찾는다
- Search file sequentially starting at the record to which the index record points.
즉, 다음꺼 하나씩 비교해가면서 위치를 파악한다
Secondary Indices
- 추가적인 bucket(일종의 disk block)을 만들어서 여기에 주소를 저장하도록 한다.
- disk I/O가 2번 발생한다
- (설명) Index record points to a bucket that contains pointers to all the actual records with that particular search-key value
- 반드시 dense해야 한다
- 그런데 위의 그림처럼 block 하나에다가 data 하나씩만 저장하고 있으면
block에 대한 활용도가 낮다
하나의 block에는 여러 data를 저장할 수 있다.
Dense vs. Sparse
sparse 기준
장점
- index size가 작아서 storage overhead(space overhead)가 적다.
- index에 없는 걸 삭제하거나 삽입해도 할 게 없어서, update에 대한 overhead가 적다
단점
- record 위치를 찾기 위해서 검색할 때 속도나 느리다 (검색 시간이 오래걸린다)
Good trade-off
- for clustered index,
sparse index with an index entry for every block in file, corresponding to least search-key value in the block
- 일종의 sparse index라고 할 수 있다. block의 맨 처음 tuple을 가리키게 한다
- for unclustered index,
sparse index on top of dense index (multilevel index)
- dense한 index 위에 이거에 대한 index를 하나 더 빌드한다.
Multilevel Index
- 만약 index가 너무 커서 memory에 다 안 올라가게 되면, access도 become expensive
- 해결 방법 : treat index kept on disk as a sequential file
and construct a sparse index on it
(index 자체를 sequential로 간주하고, sparse index를 build한다)
- outer index : sparse index of the basic index
- inner index : the basic index file
- 오른쪽에 있는거
- 만약에 outer index가 아직도 너무 크면, 또 새로운 level을 만들면 된다
- Indices at all levels must be updated on insertion or deletion from the file
- 맨 outer에 있는 index만 memory에 있다고 본다.
(충분히 작게 만들고 memory에 올려)
- 애초에 outer를 만든 이유가 memory에 들어가지 못할 만큼 커서.
- 메모리에서 scan하는 건 I/O로 취급하지 않는다.
- 위 그림에서 I/O = 1
Index Update
Deletion
(ppt 같이 보면서 공부하기)
- 삭제해야 하는 record가 걔의 search-key value의 유일한 record였으면,
그 search key도 index에서 삭제되어야 한다.
-
Dense : deletion of search-key is similar to file record
-
Sparse : 일단 index에 걔가 있으면 지워주고, 지운 그 자리는
걔의 다음 애의 다음으로 대체시킨다. 만약에 그 다음의 다음이 이미 있으면 따로 대체시키지 않고 그냥 없앤다.
Insertion
- 삽입해야 할 record의 search key value를 이용해서 위치를 잡는다
- Dense : 그 search key가 없으면, 삽입해라
- sequential하게 유지시켜줘야 함
- overflow block이 아마 필요할거야
- Sparse : 각 block의 첫 번째 tuple 가리키고 있다고 치자.
- 그럼 기존에 있는 block에다가 record 삽입하는 건 Index 입장에서 할 게 없다.
- 다만, 새로운 block을 생성할 거면 그 block의 first search key를 Index에 넣어줘야 한다.
Multilevel일 때 algorithms are simple extensions
Indices on Multiple Keys
Composite search key
-
사전 순서대로 정렬해라
(John, 12121) < (Johm, 13514)
(John, 13514) < (Peter, 11223)
-
name으로 검색하나 (name, ID)로 검색하나 동일하다.
-
ID로 검색하는 건 불가능