What does indexing do for database performance?
It speeds up access to desired data by minimizing the number of disc visits required to fulfill a query.
Search key vs pointer in an index entry.
Search key: the attribute(s) used to look up records in a file. Pointer: the address of the disk block where the instance corresponding to the key can be found.
Indices fall into two basic families. Which, and how is each organised?
Ordered indices (sorted) and hash indices (search keys distributed uniformly across "buckets" using a "hash function").
List the five index evaluation metrics.
Access types supported efficiently; access time; insertion time; deletion time; space overhead.
Primary index vs secondary index.
Primary (clustering): its search key specifies the sequential order of the file (usually, not necessarily, the primary key). Secondary (non-clustering): its search key specifies an order different from the sequential order of the file.
What is an index-sequential file?
An ordered sequential file with a primary index.
Dense index vs sparse index.
Dense: an index record for every search-key value in the file. Sparse: index records for only some search-key values (records must be sequentially ordered on the search key).
How do you locate search-key value K with a sparse index?
Find the index record with the largest search-key value < K, then search the file sequentially starting at the record it points to.
What is the "good tradeoff" for sparse indices?
A sparse index with an index entry for every block in the file, corresponding to the least search-key value in the block.
Primary vs secondary index for a sequential scan: which is costly, and why?
Scanning with a secondary index is costly: each record access may fetch a new block from disk; a block fetch requires about 5 to 10 milliseconds versus about 100 nanoseconds for memory access.
What is the cost of having many indices?
Updating indices imposes overhead on database modification: when a file is modified, every index on the file must be updated.
When the primary index is too big for memory, what are the outer and inner index?
Outer index: a sparse index of the primary index. Inner index: the primary index file (kept on disk as a sequential file).
Three strategies for dept_name = "Finance" and salary = 80000 with single-attribute indices.
1. dept_name index, then test salary; 2. salary index, then test dept_name; 3. use both indices and take the intersection of both sets of pointers.
What is lexicographic ordering of composite keys?
(a1, a2) < (b1, b2) if either a1 < b1, or a1 = b1 and a2 < b2.
Which condition can an index on (dept_name, salary) NOT handle efficiently?
dept_name < "Finance" and salary (balance) = 80000 — it may fetch many records that satisfy the first but not the second condition. The order of the attributes matters.
Sparse index deletion: what happens to the entry of the deleted key?
It is replaced with the next search-key value in the file (in search-key order); if that next value already has an index entry, the entry is deleted instead of being replaced.
Sparse index insertion (entry per block): when does the index change?
Only when a new block is created: the first search-key value appearing in the new block is inserted into the index.
Disadvantage of indexed-sequential files vs advantage of B+-trees.
Indexed-sequential: performance degrades as the file grows (overflow blocks) and periodic reorganization of the entire file is required. B+-tree: automatically reorganizes itself with small, local changes.
B+-tree of order m: path lengths, children of internal nodes, values in a leaf, and the root.
All paths from root to leaf are of the same length; each node that is not a root or leaf has between ⌈m/2⌉ and m children; a leaf node has between ⌈m/2⌉ and (m−1) values; a non-leaf root has at least 2 children.
In a B+-tree node, what are K_i and P_i?
K_i are the search-key values (ordered K_1 < K_2 < …). P_i are pointers to children (non-leaf nodes) or to records or buckets of records (leaf nodes).
Where does P_m of a leaf node point?
To the next leaf node in search-key order.
What do the non-leaf nodes of a B+-tree form?
A multi-level sparse index on the leaf nodes.
Maximum B+-tree height for K search-key values, and the 1-million example.
No more than ⌈log_⌈m/2⌉(K)⌉. With 1 million keys and m = 100: at most log_50(1,000,000) = 4 nodes accessed, versus around 20 for a balanced binary tree.
How big is a B+-tree node typically, and what is a typical m?
Generally the same size as a disk block, typically 4 kilobytes; m is typically around 100 (40 bytes per index entry).
Order M = 5: maximum values and children per node, and what happens with a fifth value?
Maximum 5 children and 4 values (M−1). A fifth value overflows the node: it splits and the middle value moves to the parent.
Inserting C N G A then H into an order-5 tree: which value moves up?
G — the node would be (A, C, G, H, N), so the middle data G moves to the parent.
What is hashing, and what is a bucket?
Hashing is a technique to quickly locate a data record irrespective of the size of the database. A bucket is a unit of storage containing one or more records (typically a disk block).
Why must an entire bucket be searched sequentially?
Because records with different search-key values may be mapped to the same bucket.
Static hashing: what stays constant, and what is H(107) % 5?
The number of buckets remains constant (good for known size). H(107) % 5 = 2.
Worst vs ideal hash function.
Worst: maps all search-key values to the same bucket. Ideal: uniform (each bucket gets the same number of values) and random (same number of records per bucket irrespective of the actual distribution).
What causes bucket overflow?
Insufficient buckets, or skew in the distribution of records (multiple records with the same search-key value; a hash function giving a non-uniform distribution). It can be reduced but not eliminated.
Closed hashing vs open hashing.
Closed hashing: overflow chaining — overflow buckets of a bucket are chained in a linked list. Open hashing: no overflow buckets; not suitable for database applications.
What is a hash index, and is it primary or secondary?
It organizes the search keys, with their associated record pointers, into a hash file structure. Strictly speaking, hash indices are always secondary indices.
Deficiencies of static hashing.
Fixed bucket addresses while databases grow or shrink: too few buckets → too many overflows; space for anticipated growth → wasted space; shrinking → wasted space; periodic re-organization is expensive and disruptive.
What is dynamic hashing, and what are its components?
Also known as extendible hashing: buckets are added and removed on demand; good for databases that grow and shrink frequently. Components: data bucket, flexible hash function, and directories (which store pointers to buckets).
What is the global depth in dynamic hashing?
The number of bits in each directory id; the more records, the more bits.
When is hashing better, and when are ordered indices preferred?
Hashing is generally better at retrieving records having a specified value of the key; if range queries are common, ordered indices are preferred.
Hash indices and B+-trees: which does each system (PostgreSQL, Oracle, SQLServer) support?
PostgreSQL supports hash indices; Oracle supports static hash organization, but not hash indices; SQLServer supports only B+-trees.
Describe a bitmap index on an attribute.
A bitmap for each value of the attribute; each bitmap has as many bits as records; the bit is 1 if the record has that value, otherwise 0.
When are bitmap indices useful, and how are queries answered?
For queries on multiple attributes (not single-attribute queries); answered with bitmap operations: intersection (and), union (or), complementation (not).
What does create unique index do?
It indirectly specifies and enforces the condition that the search key is a candidate key.