Indexing

Alternatives for Data Entry k*

k* has three alternatives:

k* are sorted by k for sorted index, or hashed by k for hased index

Alternative 1: <k, data record>

Index itself is a file organization for data records- index is as large as the file

At most one index on a given file can use Alternative 1. Why?
-> Alternative 1 stores copy of the data, so if more than one index means duplicated key

Alternatives 2 and 3: <k, rid> or <k, list of rids>

Data entries much smaller than data records, so index is much smaller than file

Alternative 3 more compact than Alternaitve 2, but leads to variable sized data entries

At most one index can use Alternative 1; rest must use Alternatives 2 or 3

Index Classification

Unique index: Search key contains a candidate key.

How many records will be returned for an equality search using a unique index?
-> 0 or 1

Clustered vs. unclustered: For sorted index, data entries k* are sorted by search key k.

If data records are also sorted by k, clustered index, otherwise, unclustered index.

A file has at most one clustered index

Alternative 1 leads to clustered index

Be sure understand this page!

Example

Clustered Index

Data Recordでは、数字は年齢を表します.これらは各年齢層の異なる記録である.
A 1)最初に上のデータ項目にアクセスする.2つの4があることを確認し、次のデータレコードの最初の4つに直接アクセスします.datarecordsは整列しているので、7が終わるまで横に移動します.したがって,最初にアクセスしたページは(1,2,3,3,4,4),次いで(3,3,4),(4,5,5),(5,6,7),(7,7,8)である.要するに、1 IOはデータ項目の読み出しに用いられ、4 IOはデータ記録の読み出しに用いられる.後でデータ・アイテムにアクセス方法が表示されます.

Unclustered Index

データ・アイテムはソートされましたが、データ・レコードはソートされていません.
幸いなことに、メモリ内のページは再読み込みする必要はありません.そうしないと、各データボックスのk*を読み込む必要があります.

4*, 4*, 5*, 5*, 5*, 6*, 7*, 7*, 7*

IOもそれに伴って発生します.最悪の場合、9個のIOはデータレコードから、3個のIOはデータ項目から来る.(3人の原因は、データエントリの2回目の読み取りで、右側にも7がある可能性があるので、必ず読み取らなければなりません)