Section 5 Flashcards
Databases commonly support four alternative table structures
-Heap table
-Sorted table
-Hash table
-Table cluster
Heap tables
Optimize insert operations. — Are particularly fast for bulk load of many rows since rows are stored in load order.
In a —— no order is imposed on rows.
Hash table
Bucket
In a —- rows are assigned to buckets. A —- is a block or group of blocks containing rows
What is a simple hash function with four steps?
Modulo function
Table scan
Is a database operation that reads table blocks directly, without accessing an index
Index scan
Is a database operation that reads index blocks sequentially, in order to locate the needed table blocks
Hit ratio, also called filter factor or selectivity
Is the percentage of table rows selected by a query.
Binary search
The database repeatedly splits the index in two until it finds the entry containing the search value
Indexes may also be?
Dense or sparse
Dense index
Contains an entry for every table row
Sparse index
Contains an entry for every table block
Multi-level index
Stores column values and row pointers in a hierarchy
The number of index entries per block is called the —- of a multi-level index
Fan-out
Several additional index types are used less often but supported but many databases:
-Hash index
-Bitmap index
-Logical index
-Function index
Bitmap index
Is a grid of bits, contain ones and zeroes
