COSI 127b Lecture Notes - Lecture 7: Binary Search Algorithm, Tuple, Linear Search
26 Apr 2020
School
Department
Course
Professor
Document Summary
Tuple ordering uses either the heap technique or the ordered technique. The heap technique works well with insert/delete, but it is not good for queries, since it uses linear search. The ordered technique is good for queries since it uses binary search, but it is bad for insertions/deletions. Indexes are good for queries, but have bad insert/delete overhead. An index is a table with a schema. Primary indexes are faster than secondary, but there can only be one per relation. Sparse indexes have higher cpu cost than dense indexes, but potentially lower io cost. Multilevel indexes are better than single level indexes. A primary index has an index search key (an attribute on which the relation is physically ordered). Unlike primary indexes, a relation can have several secondary indexes. Pointer buckets are needed when the attribute is not unique/not a key. In a dense index, there are values in the index for every search key value.
