Operations to ConsiderCosts to MeasureIndexesProperties of IndexesOperations to ConsiderScan: fetch all records in a certain relation.Search with equality selection: find all the tuples with age=5Search range selection: find all tuples with age between 5 and 50Insert: put a new record into the file.Delete: a record from the file.Costs to MeasureB data pages, R records per page.Average time to read or write a disk page: D (typically 15msec)Average time to process a record: C (typically 1 to 10 microsec)Time to apply hash function: H (typically 1 to 10 microsec)So, we count mostly I/O costs.IndexesAuxiliary structure that speeds up operations that are not supportedby the basic file organization.Formally: a set of data entries with an efficient way of locating all the entries with search key k.Questions: how are the data entries organized to support the efficient access? What is a data entry exactly?Options for data entry: 1. An actual data record (whose value is k) 2. A pair (k, rid) - pointer to the real record. 3. A pair (k, list-of-rid)Properties of Indexes- clustered vs. unclustered (how many clustered indexes can we have on a file?)- Dense vs. sparse indexes- Primary and secondary indexes (is the key entry a superkey?)Picture slides missing
View Full Document