Quiz 2 - Indexing Flashcards
table scan
- a sequential scan of the table
- each row is examined for inclusion in result
- it is the simplest and slowest for of search
- performance is benchmarked against table scan
Advantages of indexing
- index is alphabetically sorted, therefore faster
- index is much smaller than table
- only load needed pages, instead of all of them
index
- index is built for a column in a table
- a table can have more than one index
- each index entry has a search key and a pointer
- all indexes are sorted
search key
- value of an attribute in the column being indexed
* part of an index entry
pointer
- physical memory location where a record is stored
* part of an index entry
ordered index
- table is sorted according to value in the indexed column
- each search key can have only one occurrence in the index
- index points to the first occurrence in the table
- also known as a primary or clustered index
hash index
- index is sorted, but table is not
- one index record for EVERY table record
- each search key may have multiple occurences in the index
- a hash index is always dense
- also known as a secondary or non-clustered index
primary index
another name for ordered index
clustered index
another name for ordered index
secondary index
another name for hash index
non-clustered index
another name for hash index
types of ordered indices
- dense
* sparse
dense index
- table sorted by indexed column
- each search key key MUST have one and only one index record
- a type of ordered or hash index
sparse index
- table is sorted by indexed column
- there is an index record for only SOME of the search keys
- each search key can have, at most, one index record
- a type of ordered index only
impact to ordered index: INSERT
• update location values in index
• if new search key value inserted, then new record inserted to index
•
impact to ordered index: UPDATE
- equivalent to INSERT+DELETE if indexed column value is changed
- INSERT record with updated/new value
- DELETE record with old value
impact to ordered index: DELETE
- remove record from page
- move up following records on that page
- if required, delete entry from index and update locations of records moved up on that page
impact to hash index: INSERT / UPDATE / DELETE
• only requirement is to update index
ordered index vs. hash index
- hash index has same number of rows as the table indexed—index search takes longer
- same values may not be in adjacent locations in a hash index
multilevel indexing
- done when an index is too large for efficient processing
- an index is built for an index
- outer index is always an ordered sparse index
multilevel index structure
- root node index – ordered sparse
- intermediate level index – ordered or hash
- leaf nodes / data pages – table data
What should be indexed?
- attribute most frequently used to search for records usually determines the primary index
- DBMS default sets PK as ordered index, but DBA / designer may change
- one column must be a primary index
- other attributes very frequently used for searching determine secondary indexes
composite index
- index using more than one column
- determined using analysis of queries
- allows location of records using a single index instead of two
indexing factors to consider
- access type - specific values vs. a range of values
- access time - time to search and find
- insertion time - to insert new data + update index
- deletion time - to delete data + update index
effective table indexing
- create effective clustered index
- keep index keys small
- only index selective columns
- make sure left-most column is selective
- verify results and monitor performance over time
