Indexing and Hashingالفهرسة والتجزئة

• Indexing mechanisms are used to speed up access to desired data (e.g., author catalog in a library), minimizing the number of disc visits required to fulfill a query.
• Index files are typically much smaller than the original file.

• Secondary index example: file stored by ID, but we search all instructors of a department, or with a salary (range). An index record points to a bucket of pointers to all records with that value.
• Updating indices imposes overhead on database modification: every index on the file must be updated.
• Sequential scan using a primary index is efficient; using a secondary index is expensive — each record access may fetch a new block: 5 to 10 milliseconds per block fetch versus about 100 nanoseconds for memory access.

• Good tradeoff: a sparse index with an index entry for every block in the file, corresponding to the least search-key value in the block.

• If the primary index does not fit in memory, access becomes expensive.
• Solution: keep the primary index on disk as a sequential file and construct a sparse index on it.
• If even the outer index is too large to fit in main memory, yet another level of index can be created, and so on.

• A search key is deleted from the index only if the deleted record was the only record with that search-key value.
• Multilevel insertion and deletion are simple extensions of the single-level algorithms.

A B+-tree with order m (slide 26)

• All paths from root to leaf are of the same length.
• Each node that is not a root or a leaf has between ⌈m/2⌉ and m children.
• A leaf node has between ⌈m/2⌉ and (m−1) values.
• If the root is not a leaf, it has at least 2 children; if the root is a leaf, it can have between 0 and (m−1) values.

• A node is generally the same size as a disk block, typically 4 kilobytes; m is typically around 100 (40 bytes per index entry).
• Insertions and deletions can be handled efficiently: the index can be restructured in logarithmic time.

• A fifth value makes a node overflow: it splits and its middle value moves to the parent (G after H; M; then T after Z).
• E, K, Q and F, W, L, T are added without any split.

Exercise (slide 44)

• Consider the below set of values and create a B+-Tree with order M=5: 5, 2, 7, 15, 45, 13, 29, 11, 21, 9, 6, 30, 25. (The slide gives no answer.)

• Bucket overflow (collision) causes: insufficient buckets; skew (many records with the same key; non-uniform hash function). It can be reduced but not eliminated: handled by overflow buckets.
• Overflow chaining (overflow buckets in a linked list) is closed hashing; open hashing (no overflow buckets) is not suitable for database applications.
• A hash index organizes search keys with their record pointers into a hash file structure; hash indices are always secondary indices.

Deficiencies of static hashing (slide 59)

• Too few buckets + growing file → performance degrades due to too much overflows.
• Space allocated for anticipated growth → significant space wasted initially; a shrinking database wastes space again.
• Periodic re-organization with a new hash function is expensive and disrupts normal operations.
• Better solution: allow the number of buckets to be modified dynamically.

• In practice: PostgreSQL supports hash indices; Oracle supports static hash organization, but not hash indices; SQLServer supports only B+-trees.

• Useful for queries on multiple attributes; not particularly useful for single attribute queries.
• Counting the number of matching tuples is even faster.
• Bitmap indices are generally very small compared with relation size.

• Most database systems allow specification of the type of index, and clustering.