Quiz 2 - Indexing

Question 1

table scan

Answer 1

• 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

Question 2

Advantages of indexing

Answer 2

• index is alphabetically sorted, therefore faster
• index is much smaller than table
• only load needed pages, instead of all of them

Question 3

index

Answer 3

• 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

Question 4

search key

Answer 4

• value of an attribute in the column being indexed

* part of an index entry

Question 5

pointer

Answer 5

• physical memory location where a record is stored

* part of an index entry

Question 6

ordered index

Answer 6

• 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

Question 7

hash index

Answer 7

• 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

Question 8

primary index

Answer 8

another name for ordered index

Question 9

clustered index

Answer 9

another name for ordered index

Question 10

secondary index

Answer 10

another name for hash index

Question 11

non-clustered index

Answer 11

another name for hash index

Question 12

types of ordered indices

Answer 12

• dense

* sparse

Question 13

dense index

Answer 13

• table sorted by indexed column
• each search key key MUST have one and only one index record
• a type of ordered or hash index

Question 14

sparse index

Answer 14

• 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

Question 15

impact to ordered index: INSERT

Answer 15

• update location values in index
• if new search key value inserted, then new record inserted to index
•

Question 16

impact to ordered index: UPDATE

Answer 16

• equivalent to INSERT+DELETE if indexed column value is changed
• INSERT record with updated/new value
• DELETE record with old value

Question 17

impact to ordered index: DELETE

Answer 17

• 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

Question 18

impact to hash index: INSERT / UPDATE / DELETE

Answer 18

• only requirement is to update index

Question 19

ordered index vs. hash index

Answer 19

• 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

Question 20

multilevel indexing

Answer 20

• 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

Question 21

multilevel index structure

Answer 21

• root node index – ordered sparse
• intermediate level index – ordered or hash
• leaf nodes / data pages – table data

Question 22

What should be indexed?

Answer 22

• 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

Question 23

composite index

Answer 23

• index using more than one column
• determined using analysis of queries
• allows location of records using a single index instead of two

Question 24

indexing factors to consider

Answer 24

• 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

Question 25

effective table indexing

Answer 25

• 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