Indexing

Question 1

Index

Answer 1

A data structure to speed up retrieval of information.

Question 2

Clustering

Answer 2

Data is rearranged to speed up searching. Not a true index.

Good for ranges.

Only one table allowed. Requires constant re-arranges.

Question 3

Hash

Answer 3

Associate a key with a hash function.

Worst-case perf is constant time

Good for equality tests

Not good for ranged tests

Question 4

Tree

Answer 4

Stores the key in a tree

Good for range tests

Bad for equality tests

Question 5

B-Tree

Answer 5

A type of self-balancing tree. Left to right increasing order

Question 6

Costs of indices

Answer 6

Larger space.
Time to create index.
Time to update index