5.3 Single-level indexes // 5.4 Multi-level indexes

table scan

• A table scan 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 table scan. If hit ratio is low, the query needs only a few table blocks, performs index scan.

index scan

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

Hit ratio / filter factor / selectivity

• Hit ratio, also called filter factor or selectivity, 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 binary search, 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 dense index contains an entry for every table row

sparse index

• A sparse index contains an entry for every table block

multi-level index

• A multi-level 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 multi-level index.

• multi-level index is the most commonly used index type.

fan-out

• The number of index entries per block is called the fan-out of a multi-level index.