5.3 Single-level indexes // 5.4 Multi-level indexes // 5.5 Other indexes // 5.6 Tablespaces and partitions

table scan

• A (blank) is a database operation that reads table blocks directly, without accessing an index.

• When a SELECT query is executed, the database examines the WHERE clause and estimates hit ratio. If hit ratio is high, the database performs a (blank). If hit ratio is low, the query needs only a few table blocks, performs index scan.

index scan

• An (blank) is a database operation that reads index blocks sequentially, in order to locate the needed table blocks.

Hit ratio / filter factor / selectivity

• (blank), also called (blank) or (blank), is the percentage of table rows selected by a query.

• When a SELECT query is executed, the database examines the WHERE clause and estimates hit ratio. If hit ratio is high, the database performs a table scan. If hit ratio is low, the query needs only a few table blocks, performs index scan.

binary search

• Index must be sorted!

• In a (blank), the database repeatedly splits the index in two until it finds the entry containing the search value.

  • The database first compares the search value to an entry in the middle of the index.

  • If the search value is less than the entry value, the search value is in the first half of the index. If not, the search value is in the second half.

dense index

• A (blank) contains an entry for every table row

sparse index

• A (blank) contains an entry for every table block

multi-level index

• A (blank) index stores column values and row pointers in a hierarchy.

• Each level above the bottom is a sparse sorted index to the level below.

• The number of index entries per block is called the fan-out of a (blank) index.

• (blank) index is the most commonly used index type.

fan-out

• The number of index entries per block is called the (blank) of an index).

hash index

• In a (blank), index entries are assigned to buckets.

• As an index grows, some buckets eventually fill up, and additional blocks are allocated and linked to the initial block.

bitmap index

• A (blank) is a grid of bits.

• (blank) indexes contain ones and zeros.

• enable fast reads.

tablespace

• A (blank) is a database object that maps one or more tables to a single file.

• not specified in the SQL standard.

• Database administrators can manually create (blank) and assign one or multiple tables to each (blank). Database administrators can improve query performance by assigning frequently accessed tables to tablespaces stored on fast storage media.