Indexing

What are the two basic kinds of indices?

When a node in an order-5 B-tree overflows during insertion (a 5th key arrives), which key moves up to the parent?

Secondary indices must be:

In a multilevel index, the outer index is:

A key advantage of B+-tree index files over indexed-sequential files is that they:

In a B+-tree, all paths from the root to a leaf are:

With 1 million keys and n = 100, roughly how many B+-tree nodes are accessed per lookup?

In static hashing, the bucket of a record is obtained from:

Overflow chaining, where overflow buckets form a linked list, is called:

Which is generally preferred for range queries?

An index file is typically much smaller than the original file.

A sparse index generally locates records faster than a dense index.

A sequential scan using a secondary index is expensive.

A block fetch is far slower than a memory access (milliseconds vs nanoseconds).

In a B+-tree leaf, the last pointer Pₙ points to the next leaf in search-key order.

An ideal hash function is uniform and random.

Open hashing uses overflow buckets and is well suited to databases.

Hash indices are always secondary indices.

Static hashing handles a growing or shrinking database gracefully with a fixed number of buckets.

Bitmap indices are especially useful for queries on multiple attributes.

Match each index type with its description.

Match each B+-tree fact.

Match each hashing term.

Match each choice with the better structure.

Match each SQL/bitmap term.